SOLUTION: 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 aft

Algebra ->  Test -> SOLUTION: 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 aft      Log On


   



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) About Me  (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 X%5BA%5D, X%5BA%5D, X%5BC%5D 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) About Me  (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.