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 turn. Prove or disprove that Calvin can prevent Hobbes from winning. Note: A move in the horizontal direction by a positive quantity will be towards the right, and by a negative quantity will be towards the left (and similar directions in the vertical case as well).
Problem
Source: Indian IMOTC 2013, Practice Test 2, Problem 3
Tags: vector, analytic geometry, combinatorics proposed, combinatorics
13.05.2013 19:14
Sorry, wrong solution.
14.05.2013 10:14
What if bi=−ai?
14.05.2013 14:06
What if Calvin in his first move chooses (a,b) and then Hobbes plays (−a,−b)?
14.05.2013 16:01
Well, that's why Calvin's first move must be something in the form of (a,−a).
14.05.2013 16:04
Or (a,0) (or (0,b)), since then 0 cannot be used anymore ...
14.05.2013 17:38
Proof that Calvin can always prevent Hobbes from reaching (0,0): Let's say that Calvin is about to move now. Let A be the set containing all earlier chosen numbers and (x,y) - current position of the marker. Set t=3⋅max. Then translate the marker by a vector [t,\ -x-t] so that the new position is (x+t,\ y-x-t). It's easy to show that the absolute values of the vector coordinates are strictly bigger than the absolute values of every element of A - for every a \in A we have |t| > |a| and |-x-t| \geq |t|-|x| \geq \frac{2}{3}|t| > |a|. It follows that this move is possible. Of course x+t>0, so Calvin will never return to (0,0) this way. Assume Hobbes got back to the origin after described Calvin's move. Then he would have to move the marker horizontally by -x-t points. However, after last Calvin's move this number became forbidden - contradiction.
18.05.2018 21:03
Idea only since I am in hurry ! Suppose Hobbes arrives at some point (m,n) . Then Calvin chooses a point (d,-d) such that absolute value of d > max{ absolute values of x,y } . Such d easily exists . Since absolute value is increasing it never turns out to be 0 .Again Hobbes can not send it directly to 0 for the condition that none of (a,b) can be repeated . So done ! But note that I have not fixed d for describing only a strategy ! But this strategy is useful for a lattice plain .There are many flaws if this game is played in the real plane !
19.05.2018 06:13
semisimplicity wrote: 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 turn. Prove or disprove that Calvin can prevent Hobbes from winning. Note: A move in the horizontal direction by a positive quantity will be towards the right, and by a negative quantity will be towards the left (and similar directions in the vertical case as well). Can u tell whete to find india imotc 2017 problems????
19.05.2018 09:05
@above https://artofproblemsolving.com/community/c3176_india_contests
21.08.2023 04:22
Yes. First, Calvin moves (a,0). Then after Hobbes's nth move, let the y-coordinate be Y_n. Cleary, Y_1=\not=0. Let A= \{\textit{the numbers have been used}\}.After hobbes nth move, we consider the following set number of number S=\{-(Y_n+t): t\in A\}. Clearly, there exists an x_{n+1}\in A, but -(Y_n+x_{n+1})\not\in A. Let Calvin choose b=-(Y_n+x_{n+1}). So the y-coordinate of the marker becomes -x_{n+1}. Therefore Hoobes cant make it back to origin on the next turn.