You have four pointlike frogs on an infinite two-dimensional plane. The frogs begin situated at the corners of a square, and at any time a legal move for the frogs is to jump over another frog to exactly the opposite side, such that the other frog was exactly in the middle of the jump. Show whether it is possible to ever have a configuration such that three frogs lie in a single straight line.I probably don't need to clarify much, but just in case I'll give an example; a frog located at (1,1) jumping over a frog located at (3,4) would jump to (5,7), since (3,4) is exactly in the middle of (1,1) and (5,7).
Frogs On A Plane
New puzzle time, I first found this one in the math club room on KGS:
Subscribe to:
Post Comments (Atom)
6 comments:
Here is a related puzzle: if the frogs start on the corners of a square like in the original puzzle, is it ever possible for them to configure themselves in a larger square?
Yeah, the kgs math club had that extension as well, but I never found a proof of it that I was happy with, and the proof they gave only managed to convince me that you counldn't get a larger square that was in the same orientation as the original square. I susect its still the case that you can't get them into a larger square, but since I hadn't proved it to myself I didn't want to post it.
How about this proof:
The key is to notice that the process is reversible. If you can get from configuration A to configuration B, then you can also go from B to A by reversing the jumps.
This solves both the original puzzle and the extension. If you start with frogs in a line, after every jump the frogs will still be in a line, so you can never get to a square. Thus you also can't go the other way, from a square to a line.
Similarly, if you start with a square, after each jump you will still be on the grid* defined by the original square. Therefore you can't get to a smaller square, because the original square is the smallest possible for the grid. So it's also impossible to go from a smaller to a larger square.
*(Form the grid by extending lines along each side of the square, then adding an infinite number of equally spaced lines parallel to the original lines. After each jump the frogs will always be on the intersections of these lines.)
ed, as far as the "frogs on a line" puzzle goes, I'm not convinced.
Your reasoning does show that you can't go from a square to having all four frogs on a line. But I don't see how it follows that you can never get THREE frogs on a line.
Eds reasoning was to prove his extension problem, not the inital posted problem, I'll post my solution to it someday soon, I think.
Oops, you're right. I misread the original puzzle. I guess I need a new approach...
Post a Comment