A grasshopper that only jumps diagonally

Question

A grasshopper sits at the origin (0,0) of an infinite square grid. In one hop it always moves diagonally: its horizontal coordinate changes by +1 or -1, and at the same time its vertical coordinate changes by +1 or -1. So the four possible hops take it to (1,1), (1,-1), (-1,1), or (-1,-1), and similarly from wherever it stands. The grasshopper wants to land exactly on (0,1), the square directly north of where it started. Can it get there in some number of hops? If not, why is it impossible no matter how long it hops around?

Accepted Answer

It is impossible, and the reason is a one-line invariant. Watch the sum of the coordinates. Look at the quantity x + y. At the start it is 0 + 0 = 0, which is even. Every hop changes x by \pm 1 and y by \pm 1, so it changes x + y by (\pm 1) + (\pm 1) \in \{-2,\ 0,\ +2\}. In every case the change is an even number. Adding an even number to an even number keeps it even, so x + y stays even forever, no matter how the grasshopper zig-zags. Now check the target. At (0,1) we have x + y = 0 + 1 = 1, which is odd. Since the grasshopper's position always has an even coordinate-sum, it can never sit on…

A grasshopper that only jumps diagonally

Your answer

More Brainteasers questions