Library / /19 of 91

, 2013

Combinatorics Difficulty 5.4 AIME, harder Prove it India

A marker is placed at the origin of an integer lattice. Calvin and Hobbes play the following game. Calvin starts the game and each of them takes turns alternatively. At each turn, one can choose two (not necessarily distinct) integers $a$ , $b$ , neither of which was chosen earlier by any player and move the marker by $a$ units in the horizontal direction and $b$ units in the vertical direction. Hobbes wins if the marker is back at the origin any time after the first move. Prove that Calvin can prevent Hobbes from winning.

Solution

Let $A_n$ denote the set of chosen integers after $n$ turns. We claim (by induction) that after Calvin's move he can ensure that if $a \in A_n$ then $-a \in A_n$ , and that the marker is at $(r, -r)$ for some non-zero integer $r$ in $A_n$ .

Let Calvin move the marker to $(-1, 1)$ in his first turn. Suppose that, after $n$ turns, the marker is at $(r, -r)$ and that Hobbes then moves it to $(r+a, -r+b)$ . If $a \ne b$ then Calvin can move it back to $(r, -r)$ . If $a = -b$ then Calvin can move the marker to $(c, -c)$ or $(-c, c)$ where $c$ is the largest element of $A_{n+1}$ , so the claim follows. Hence Calvin can prevent Hobbes from winning. $\square$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.