Question 1044811: Three grasshoppers play leapfrog along a line. At each turn, one grasshopper leaps over another, but not over two others. Can the grasshoppers return to their initial positions after 1991 leaps?
Found 2 solutions by ikleyn, robertb: Answer by ikleyn(52803) (Show Source):
You can put this solution on YOUR website! .
Three grasshoppers play leapfrog along a line. At each turn, one grasshopper leaps over another, but not over two others.
Can the grasshoppers return to their initial positions after 1991 leaps?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The initial configuration is like this:
-----0--------A------B-------------C----------
Three grasshoppers, named A, B and C, were sitting on the straight line (number line !).
Let's consider the function
f =
where , , are coordinates of the grasshoppers A, B and C at each current turn of the game.
The function f takes the values +1 or -1 depending on the position of A, B and C at each current moment.
In the initial position the value of the function f is +1.
Notice that f changes the sign to the opposite at each and every turn of the play.
Then after 1991-th turn f will have the opposite (negative) sign to that "+1" it had initially.
It means that the grasshoppers can not return to (can not be at) their initial positions after 1991-th turn.
Solved.
===================================
I'd like to make a comment regarding a Robertb' solution to this problem.
Robertb starts his solution saying
"The sequence of the first eight leaps (or 9 arrangements) are as follows:
ABC --> BAC --> ABC --> ACB --->" . . .
He assumes that the sequence of leaps is strictly pre-assigned.
It leads directly to cycling of the sequence . . .
But the condition does not require it. The condition does not require strictly pre-assigned sequence.
The sequence can be
ABC --> BAC --> BCA --> CBA --->" . . .
It is not prohibited by the condition. It is allowed.
So, Robertb solves, actually, another problem . . .
Or, if you want, we solved different problems.
In my solution, much more wide class of leaps is considered.
And the resulting statement was proved for much wider class of leaps - for all the leaps allowed by the condition.
It was proved disregarding if there is OR there is no cycling in the sequence.
Answer by robertb(5830) (Show Source):
You can put this solution on YOUR website! The sequence of the first 13 leaps (or 14 arrangements) are as follows:
ABC --> BAC ( B leaps to form the next arrangement)
ABC --> ACB --> CAB --> CBA --> BCA --> BAC (C leaps to form next arrangement)
ABC --> ACB --> CAB --> CBA --> BCA --> BAC (C leaps to form next arrangement)
...........................
(cycle repeats itself after 6 arrangements after the first two arrangements)
For any k leaps, there are k+1 arrangements.
For 1991 leaps there are 1992 arrangements. Subtract the first two arrangements to start the count for the other arrangements,
to get 1992 - 2 = 1990.
1990/6 = 331 + 4/6 (leaving a remainder of 4), meaning the last leap arrangement is CBA, which is not the initial position ABC.
|
|
|