For positive integers $t,a,b,$a $(t,a,b)$-game is a two player game defined by the following rules. Initially, the number $t$ is written on a blackboard. At his first move, the 1st player replaces $t$ with either $t-a$ or $t-b$. Then, the 2nd player subtracts either $a$ or $b$ from this number, and writes the result on the blackboard, erasing the old number. After this, the first player once again erases either $a$ or $b$ from the number written on the blackboard, and so on. The player who first reaches a negative number loses the game. Prove that there exist infinitely many values of $t$ for which the first player has a winning strategy for all pairs $(a,b)$ with $a+b=2005$.
Problem
Source: BMO Problem 5
Tags: combinatorics proposed, combinatorics
15.05.2005 23:14
I just found that if for $x$ Player 1 wins, then he wins for $x+2005k$. To prove it suppose Player 1 wins for $x$ between $1$ and $2005$, and call $P_1$ his sequence of moves. Now if they start from $2005k+x$ let Player 1 start with the firs step of $P_1$ and then if Player 2 substracts $a$, he substracts $b$ or backwards until they reach $x-$first step of $P_1$, from here, the game is analogus to the one started with $x$, becuase it is player 2 turn and player 1 can do $P_1$ from step two on! Finally $x=2004$ works, because player 1 plays $max[a,b]$ and clearly he wins!
16.05.2005 19:23
Pascual2005 wrote: I just found that if for $x$ Player 1 wins, then he wins for $x+2005k$. To prove it suppose Player 1 wins for $x$ between $1$ and $2005$, and call $P_1$ his sequence of moves. Now if they start from $2005k+x$ let Player 1 start with the firs step of $P_1$ and then if Player 2 substracts $a$, he substracts $b$ or backwards until they reach $x-$first step of $P_1$, from here, the game is analogus to the one started with $x$, becuase it is player 2 turn and player 1 can do $P_1$ from step two on! all seems fine except for a small point which is not clear from the post: if for $x+(a+b)k$ it is a player 1 win then if he plays $x+(a+b)k\rightarrow x+(a+b)(k-1)+b$,say(i.e.he removes $a$) then inductively it is not clear that it reduces to $x$ since the second player could again remove $a$ instead of $b$ which will inductively reduce the problem. but that is not a very major problem because we can induct on $k$ and all it suffices to show is that for $k=1$ the problem is reducible,i.e., if $f(x)$ denotes the winner of the game starting with $x$($f$ takes values $1$ or $2$) then $f(t+a+b)=f(t)$.if $f(t)=2$ then Pascual2005 's argument works fine so that case is easy.Now $f(t)=1$ iff either $f(t-a)=2$ or $f(t-b)=2$. suppose then that $f(t)=1$ but that both $f(t+a)=f(t+b)=1$(so that $f(t+a+b)=2$) then clearly we have $f(t+a-b)=f(t+b-a)=2$. but that means $f(t-b)=f(t-a)=1$ and that contradicts $f(t)=1$ and that finishes the proof.
16.05.2005 19:46
If $A$ wins with $t$, then he wins with $t+a+b$ as follows: he makes the first move that he would make in order to win with $t$, say, he removes $a$. If $B$ removes $a$ as well, then $A$ removes $b$, and they are in the position $t-a$, with $B$ to move, i.e. just as if we had a game with $t$, and $A$ has just removed $a$, which is a winning strategy. Isn't it as simple as this?
16.05.2005 20:50
well,i guess you are right... and i think that's what Pascual was saying as well.i just didn't understand it properly..
17.05.2005 00:57
yes thats what i was saying, easy problem right?
02.12.2005 19:25
Is the problem really that easy? Or is the problem trying to say that there are infinite values of t such that all (t, a, b) games with a+b=2005 are simultaneously good for player 1?
03.09.2012 11:11
too late, but another solution: for a sake of contradiction assume for some finite values of $t$ player $1$ has the winning strategy. so for some infinte values of $t$ player $2$ has the winning strategy.let $t=t_{0}$ be one of the values that player $2$ has the winning strategy. so player $1$ has the winning strategy for both $t_{0} +a,t_{0}+b$ as he can subtracts $a,b$ from the initial number and then continue as player $2$ continue for the initial value $t_{0}$. by our assumption, we get that player $1$ also has winning strategy for some infinite values of initial numbers $t$. a contradiction.
03.09.2012 12:20
You are required to prove that infinitely many such $t$ exist, where each $t$ wins for all $(a,b)$. You have only proven that for all $(a,b)$, infinitely many such $t$ exists; you haven't proven that each such $t$ works for all $(a,b)$.