Two players play the game: There are two bowls, each of which can be fitted by some number of coins.
In the beginning the first player puts in the first bowl some natural number of coins of his choice. Then the second player, knowing how many coins the first put, puts in the second bowl some natural number of coins of his choice. Then, starting with the first player, each player makes one of the three possible moves:
- Take any number of coins from the first bowl
- Take any number of coins from the second bowl
- Take the same number of coins from both bowls
Both players know how many coins lying in bowls at a time. The winner is the player, after which there will be no progress in the two bowls of coins.
The first player has put in the first bowl 100 coins. How many coins you need to put as the second player in the second bowl to win the game with the right playing of both players?
$(0,0)$ is a lost position.
$(0,x)$ and $(x,x)$, $x\ge1$, are won positions as we can move to $(0,0)$.
Therefore $(1,2)$ is lost.
Then $(1,x)$ and $(2,x)$, $x\ge 3$ are won (we can move to $(1,2)$ or equivalently $(2,1)$). Also, $(x,x+1)$, $x\ge 3$, are won.
In fact we have
Lemma 1. Let $d\ge0$ then there exists at most one $n$ such that $(n,n+d)$ is lost.
Proof. Assume $(n,n+d)$ and $(m,m+d)$ are lost positions with $0\le n<m$. As we can move from $(m,m+d)$ to $(n,n+d)$, we arrive at a contradiction. $\square$
Lemma 2. Let $n\ge0$ then there exists at most one $m$ such that $(n,m)$ is lost.
Proof. Same argument. $\square$
An algorithm to list all lost positions is as follows: Assume we have found lost pairs $(a_0,b_0),\ldots, (a_{d-1},b_{d-1})$, where $b_k=a_k+k$. Let $a_d=\min\Bbb N_0\setminus\{a_0,b_0,\ldots, a_{d-1},b_{d-1}\}$ and $b_d=a_d+d$. I claim that $(a_d,b_d)$ is lost. Indeed, $(a_d,x)$ is won for $0\le x<a_d$ per lemma 2, but also for $a_d\le x<b_d$ per lemma 1; likewise, $(x,b_d)$ and $(x,x+d)$ are won for $0\le x<a_d$ per lemma 2.
We thus find: $$ (0,0),(1,2), (3,5), (4,7), (6,10), (8,13), (9,15), (11,18), (12,20), (14,23), (16,26), (17,28), (19,31), (21,34), (22,36), (24,39), (25,41), (27,44), (29,47), (30,49), (32,52), (33,54), (35,57), (37,60), (38,62), (40,65), (42,68), (43,70), (45,73), (46,75), (48,78), (50,81), (51,83), (53,86), (55,89), (56,91), (58,94), (59,96), (61,99), (63,102), (64,104), (66,107), (67,109), (69,112), (71,115), (72,117), (74,120), (76,123), (77,125), (79,128), (80,130), (82,133), (84,136), (85,138), (87,141), (88,143), (90,146), (92,149), (93,151), (95,154), (97,157), (98,159), (100,162),\ldots$$
So, the second player, who wants to present a lost position to the first player, must put 162 coins into the second bowl.