Back to the origin

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

semisimplicity

141 posts

semisimplicity

#1 h May 10, 2013, 5:56 AM • 4 Y

Y by Smita, Purple_Planet, Adventure10, Mango247

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).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dibyo_99

487 posts

dibyo_99

#2 h May 13, 2013, 4:14 PM • 4 Y

Y by alet, Adventure10, Mango247, and 1 other user

Sorry, wrong solution.

This post has been edited 1 time. Last edited by dibyo_99, May 14, 2013, 8:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chaotic_iak

2932 posts

chaotic_iak

#3 h May 14, 2013, 7:14 AM • 2 Y

Y by Adventure10, Mango247

What if $b_i = -a_i$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alet

363 posts

alet

#4 h May 14, 2013, 11:06 AM • 1 Y

Y by Adventure10

What if Calvin in his first move chooses $(a,b)$ and then Hobbes plays $(-a,-b)$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chaotic_iak

2932 posts

chaotic_iak

#5 h May 14, 2013, 1:01 PM • 3 Y

Y by Purple_Planet, Adventure10, Mango247

Well, that's why Calvin's first move must be something in the form of $(a,-a)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mavropnevma

15142 posts

mavropnevma

#6 h May 14, 2013, 1:04 PM • 3 Y

Y by Purple_Planet, Adventure10, Mango247

Or $(a,0)$ (or $(0,b)$ ), since then $0$ cannot be used anymore ...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mnbvmar

7 posts

mnbvmar

#7 h May 14, 2013, 2:38 PM • 6 Y

Y by dibyo_99, siddigss, confusedhexagon, Purple_Planet, Adventure10, Stuffybear

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 \cdot \max\left(\max_{a \in A} |a|,\ |x|,\ 1\right)$ . 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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

neel02

66 posts

neel02

#8 h May 18, 2018, 6:03 PM • 2 Y

Y by Adventure10, Mango247

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 !

This post has been edited 1 time. Last edited by neel02, May 18, 2018, 6:06 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Smita

514 posts

Smita

#9 h May 19, 2018, 3:13 AM • 2 Y

Y by Adventure10, Mango247

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????

This post has been edited 1 time. Last edited by Smita, Jun 29, 2018, 10:39 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Wizard_32

1566 posts

Wizard_32

#10 h May 19, 2018, 6:05 AM • 1 Y

Y by Adventure10

@above https://artofproblemsolving.com/community/c3176_india_contests

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

KI_HG

157 posts

KI_HG

#11 h Aug 21, 2023, 1:22 AM • 1 Y

Y by winniep008hfi

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.

Z K Y