is it beginning or begging?

ridgers wrote: Two people play a game as follows: At the begging both of them have one point and in every move, one of them can double it's points, or when the other have more point than him, subtract to him his points. Can the two competitors have 2009 and 2002 points respectively? What about 2009 and 2003? Generally which couples of points can they have? what do you mean by "when the other have more points than him subtract to him his points"? is it like when the first fellow completes his chance.if the second fellow leads him,then the points which he is leading by are given to the first fellow or something else?

I mean this: If fellow A has 20 point and fellow B 12, and it's fellow B's turn, than fellow B can subtract 12 points from the 20 points that fellow A has. So as a result fellow A will have 8 points and fellow B 12.

let the two people be A and B with 1 point each.A got the chance and doubled his points i.e he will have 2 points .now, it will be B's chance.here are some cases if he doubles his points,he will have the same points as A. if he removes 1 point from A ,then also,they will have equal points. even if we continue if they double or subtract points,they will have same points. so, $(2009,2002)$ and $(2003,2009)$ are not possible.the general way is that they will have same points every time after both A and B play their chance and they will bw of the form($2^{x}$,$2^{x}$). suppose if A in his first move, subtracts 1 point from B.then,the pair will always will be $(2^{x},0)$

i feel that my solution is somewhere wrong because the IMO TST questions cannot be so easy to do.they will be of some level.

vaibhav2903 wrote: i feel that my solution is somewhere wrong because the IMO TST questions cannot be so easy to do.they will be of some level. I don't know what to say, I could not find any mistake in your solution, but I am not better(but worse ) than you, so we need an advice from somebody else!

dont say that.you participated in IMO last year so, I expected that you would know the answer but you dont know. that doesnt mean you are worse than me.sometimes it happens,the easiest problems we wont be able to do but difficult problems we do it easily.

Denote by $a$ and $b$ the points player $A$ and $B$ have, respectively. Initially, we have $\gcd (a,b)=1$ In every moves, $(a,b)$ becomes $(2a,b)$, $(a,2b)$, $(a,b-a)$, or $(a-b,b)$. Every move leaves the $\gcd (a,b)$ invariant or double it. So, the reachable points is all points $(a,b)$ iff there exists $n\in \mathbb{N}_0$ such that $\gcd(a,b)=2^n$ Since $(2009,2002)=7$, this configuration is not possible to be approached But $2009$ and $2003$ is possible since $(2009,2003)=1$. It can be constructed easily.

Ronald Widjojo wrote: Denote by $a$ and $b$ the points player $A$ and $B$ have, respectively. Initially, we have $\gcd (a,b)=1$ In every moves, $(a,b)$ becomes $(2a,b)$, $(a,2b)$, $(a,b-a)$, or $(a-b,b)$. Every move leaves the $\gcd (a,b)$ invariant or double it. So, the reachable points is all points $(a,b)$ iff there exists $n\in \mathbb{N}_0$ such that $\gcd(a,b)=2^n$ Since $(2009,2002)=7$, this configuration is not possible to be approached But $2009$ and $2003$ is possible since $(2009,2003)=1$. It can be constructed easily. hey, there is nothing given that the gcd is equal to 1 and it is clearly given that they have 1 points each initially.so, read the question properly and answer.

vaibhav2903's solution is correct if the players alternate turns. Ronald Widjojo's solution is correct if the players can play in any order (e.g., if player A can play three times, then player B can play twice, etc.). The first interpretation is suggested by the use of the word "game"; the second interpretation makes for a more interesting problem.

vaibhav2903 wrote: Ronald Widjojo wrote: Denote by $a$ and $b$ the points player $A$ and $B$ have, respectively. Initially, we have $\gcd (a,b)=1$ In every moves, $(a,b)$ becomes $(2a,b)$, $(a,2b)$, $(a,b-a)$, or $(a-b,b)$. Every move leaves the $\gcd (a,b)$ invariant or double it. So, the reachable points is all points $(a,b)$ iff there exists $n\in \mathbb{N}_0$ such that $\gcd(a,b)=2^n$ Since $(2009,2002)=7$, this configuration is not possible to be approached But $2009$ and $2003$ is possible since $(2009,2003)=1$. It can be constructed easily. hey, there is nothing given that the gcd is equal to 1 and it is clearly given that they have 1 points each initially.so, read the question properly and answer. Sorry, i don't understand. But initially two players have $1$ coin, right? So initially $\gcd(a,b)=1$. I don't understand where is the wrong part.

Suppose that the players alternate turns; I want to prove that the only attainable couples are those of the form $(2^n, 2^{n-1})$ and $(2^n, 2^n)$. We use extended induction: suppose that after the $2k$-th move the couples can be only those of the first kind mentioned and after the $2k+1$-th those of the second kind. Then at the $2k+2$-th we can have only those of the first kind and at the $2k+3$-th only those of the second, as it is easily checked (draw a tree!), so the claim holds. If they can play in any order, then the first couple is not attainable while the second is; the right invariant is the $\gcd$ of the two numbers as shown by Ronald Widjojo. It may be that the attainable couples are all those such that the $\gcd$ of the two numbers is a power of $2$ (as it is suggested by the fact that if $(a, b)$ can be realized so can $(2a, 2b)$), and maybe it is also done by extended induction.

ridgers wrote: Two people play a game as follows: At the beginning both of them have one point and in every move, one of them can double it's points, or when the other have more point than him, subtract to him his points. Can the two competitors have 2009 and 2002 points respectively? What about 2009 and 2003? Generally which couples of points can they have? The coordinate pair $(x,y)$ represents that the first player has $x$ points and the second player has $y$ points It is easy to notice that after each move the $gcd$ doubles or remains the same, also the scores always remain positive $\gcd(x,y)=2^t, t\in \mathbb{Z}^{+}_0$ We will prove that all pairs of positive integers $(x,y)$ satisfy such that $\gcd(x,y)=2^t, t\in \mathbb{Z}^{+}_0$ We will go backwards through the following process: If $x$ is even and/or $y$ is even: We divide by $2$ until they are odd coprime numbers (coprime because their $gcd$ is a power of $2$), note that this can be done since the score can be doubled. Then the two scores are odd $(x,y)$. If $x\neq y:$ WLOG $x>y$ $(x,y)\rightarrow (x+y,y)$ Since $x+y$ is even $(x+y,y)\rightarrow (\frac{x+y}{2},y)$ Since $\frac{x+y}{2}<x$, then we have decreased the sum of coordinates If $x=y:$ $gcd(x,y)=2^t\Rightarrow x=2^t$ Notice that we then divide by $2$ (as in the first case) and arrive at $(1,1)$ Note that through this process the sum of coordinates decreases to $(1,1)$ We can only arrive at any pair $(x,y)$ such that $gcd(x,y)=2^t, t\in \mathbb{Z}^{+}_0$ $_\blacksquare$(This is the answer to the third question) Answers to the first and second question respectively: Since $gcd(2009,2002)=7$ then we cannot get there$_\blacksquare$ Since $gcd(2009,2003)=1$ then we can get there$_\blacksquare$