Three grasshoppers jumping on a line

Question

The following problem appears on pp. 86 Terrence Tao's "Solving Mathematical Problems: a personal perspective".

Three grasshoppers are on a line. Each second, one (and only one) grasshopper hops over another. Prove that after 1985 s, the grasshoppers cannot be in their starting positions.

I think the problem has to do with parity and invariance, but I was unsuccessful in finding an invariant. If we knew a grasshopper could only jump over one of its neighbors, we would be able to show that an odd number of moves can never yield the identity arrangement (considering only the relative positions of the grasshoppers). For a variant of the problem that restricts the grasshoppers to only jumping over neighbors, see this post.

However, since a grasshopper may jump over two grasshoppers at once (as I understand it), it is possible to have for example: ABC -> ACB -> BAC -> ABC, which happens in three moves.

Also, I have no idea how to take into account their actual (non-relative) positions on the line. I have tried imagining them starting on the points -1, 0, and 1, but am stuck.

Any hints/advice is appreciated, thank you!

Answer 1

As long as grasshoppers can hop over both of their neighbors, and can hop any distance past their neighbor(s), then the problem is indeed incorrect. Suppose that A, B, and C are initially at positions $0,1,$ and $2$. Consider this sequence of moves, for any number $t\ge 3$.

• A hops to $t$, hopping over B and C.

• B hops to $t+1$, hopping over A and C.

• C hops to $t+2$, hopping over A and B.

Using three moves, we have translated the entire arrangement by exactly $t$ places. Therefore, there exists a sequence of $9$ moves which brings the grasshoppers back to their starting places; they translate themselves $6$ places right, then $3$ places left, then $3$ places left once more. To extend this to a sequence of $1985$ moves which does nothing, fill the remaining $1976$ moves with pairs of hops where A hops over B twice, returning to where A started.

I agree the problem is unclear, and that Tao should have stated you can only hop over one grasshopper each time.

Answer 2

I am going to assume that in one second a grasshopper can only jump over an adjacent grasshopper and can not jump over two grasshoppers. Assume the starting position of the grasshoppers is ABC (see diagram).

There are six possible arrangements of the grasshoppers as shown in the diagram. Every possible jump from one arrangement to another is indicated by a line in the diagram. Each jump switches from an arrangement with a red dot to an arrangement with a blue dot or vice versa.

The grasshoppers start in an arrangement with a red dot and after two or any even number of seconds they will be in an arrangement with a red dot. So after 1985 (odd) seconds they will be at an arrangement with a blue dot which is not their starting arrangement.