How fast can you win this (very stupid) game?

Question

You and I get together to play the following (dumb) game:

Two positive integers N and K are fixed from the outset. We both start the game with N coins and proceed to play some number of rounds like this: Every round, I start by placing any number of my remaining coins on the table (zero is fine) and you respond likewise by also placing some amount of your current stash. Whoever placed more coins wins that round, and in a tie, nobody wins. In any case, the coins from that round are discarded and we go on to the next round. This continues until someone is the first to win a total of K rounds, in which case they win the game. If that never happens, the game is declared a tie. Just to emphasize: We do not alternate in the rounds, I always play first.

As a consequence, I can clearly never have a winning strategy (as you may just copy my play each time). But it is very possible that you could have a winning strategy for some choice of parameters. Hence, the question:

For which choices of N and K do you have a winning strategy? In these cases, what is the least number of turns in which you can guarantee to win?

Please provide your reasoning in your answer. Have fun! :)

Answer 1

Here is a table of how many turns it takes for player 2 to win (-1 if player 1 can draw):

N/K 1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  
1   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
2   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
3   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
4   -1  3   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
5   -1  3   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
6   -1  3   5   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
7   -1  3   5   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
8   -1  3   5   6   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
9   -1  3   4   6   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
10  -1  3   4   6   8   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
11  -1  3   4   6   8   -1  -1  -1  -1  -1  -1  -1  -1  -1  -1  
12  -1  3   4   6   8   9   -1  -1  -1  -1  -1  -1  -1  -1  -1  
13  -1  3   4   6   8   9   -1  -1  -1  -1  -1  -1  -1  -1  -1  
14  -1  3   4   6   8   9   11  -1  -1  -1  -1  -1  -1  -1  -1  
15  -1  3   4   6   7   9   11  -1  -1  -1  -1  -1  -1  -1  -1  
16  -1  3   4   5   7   9   11  12  -1  -1  -1  -1  -1  -1  -1  
17  -1  3   4   5   7   9   11  12  -1  -1  -1  -1  -1  -1  -1  
18  -1  3   4   5   7   8   11  12  14  -1  -1  -1  -1  -1  -1  
19  -1  3   4   5   7   8   11  12  14  -1  -1  -1  -1  -1  -1  
20  -1  3   4   5   7   8   11  12  14  15  -1  -1  -1  -1  -1  
21  -1  3   4   5   7   8   10  12  14  15  -1  -1  -1  -1  -1  
22  -1  3   4   5   7   8   10  12  14  15  17  -1  -1  -1  -1  
23  -1  3   4   5   7   8   10  12  14  15  17  -1  -1  -1  -1  
24  -1  3   4   5   7   8   10  11  14  15  17  18  -1  -1  -1  
25  -1  3   4   5   6   8   10  11  14  15  17  18  -1  -1  -1  
26  -1  3   4   5   6   8   10  11  14  15  17  18  20  -1  -1  
27  -1  3   4   5   6   8   10  11  12  15  17  18  20  -1  -1  
28  -1  3   4   5   6   8   9   11  12  15  17  18  20  21  -1  
29  -1  3   4   5   6   8   9   11  12  15  17  18  20  21  -1  
30  -1  3   4   5   6   8   9   11  12  14  17  18  20  21  23  

Some patterns can be observed. Player 2 wins if N >= 2K, and K != 1. The number of turns required for N=2K seems to increment alternately by 1 and 2 with each additional K. Going down the columns by N, the pattern is less clear, but @GentlePurpleRain came up with:

$$\left \lceil { K \left(\frac{1}{\left \lfloor{N/K} \right \rfloor} + 1 \right) } \right \rceil$$

which numerically matches.

Code here. Also includes an optimal play simulator. From sample games it looks like the game has 3 phases. First player 2 chooses to win each round until player 2 is about to win the whole game. Then player 1 prevents player 2 from winning until they no longer can do so. Then player 2 wins.

I'm sure there's some nim strategy involved here, but my brain is too tired.

Answer 2

Lets start the ball rolling with some examples.

• k=1, N <= 1 : P1 can draw.

P1 can draw by playing m1 = N. P2 has to match that to avoid instant loss. Both have run out of money so game is a draw.

• k=2, N = 0,1 : P1 draws.

There are insufficient coins to win two rounds.

• k=2, N = 2 : P1 draws.

P1 plays 1 on each of the first two rounds. If P2 wins with a play of 2 on the first round, then he loses the second. No coins left so a draw. If P2 ducks the first round then he has to play 1 or 2 on the next round to avoid an immediate loss. Either way, P2 cannot win two rounds, so the game ends in a draw.

• k=2, N = 3 : P1 can draw

P1 plays 1 in each of the first 3 rounds. If P2 wins the first, then P2 must play their remaining coin in either the second or third round to avoid an imediate loss. But now no coins left for either player, so a draw. If P2 ducks the first round, they have to play at least 1 coin in each of the second two rounds to avoid immediate loss. If they play 2 in one of the rounds, then neither players has any coins left so a draw, if they play 1 in each of rounds 2 and 3, then they can win teh 4-th round, but final score is 1 win each and 2 draws so an overall draw.

• k=2, N=4 : P1 loses

If P1 plays 0, P2 responds with 1. If P1 continues with 1 or 2 then P2 wins immediately, but if P1 continues wih 3 or 4 then P2 ducks the second round and has a coin majority to win the third round.

Similarly if P1 plays 1, P2 responds with 2. If P2 now plays 0 or 1 then P2 wins immediately, but if P1 continues wih 2, or 3 then P2 ducks but has more coins so can win the third round.

If P1 plays 2, P2 ducks. On the second round if P1 plays 0 or 1, p2 wins by 1 and has a coin majority to win the third round, but if P1 plays 2 then P2 matches for a draw, but can now win thr next 2 rounds as P1 has exhausted their coins and P2 still has 2 remaining.

If P1 plays 3 or 4 coins, then P2 ducks, but can win the next two rounds by playing 2 coins each time, for a win.

• k=2, N >= 5 : P1 loses.

If P1 plays m1 <= N/2 then P2 responds with m1 + 1 to win the first round. P1 next plays m2. If m2 < N - m1 - 1 then P2 plays m2 + 1 and wins immediately on the second round. If m2 >= N - m1 - 1 then P2 plays 0 to lose the second round. But now P1 has fewer coins remaining than P2, so P2 can beat any play and win on the third round.

If instead, P1 plays m1 > N/2 then P2 plays 0 to lose the first round. But now P2 has sufficient coins to beat P1 in each of the next two rounds, for a win after the third round.

Answer 3

Thank you to @causative for the code and @GentlePurpleRain's comment.

I will prove that (for $K\ge 2$)

• $N\ge 2K$ wins
• $N\le 2K-1$ draws
• The number of moves for the fastest win for $N=2K$ is $\ge \lceil3K/2\rceil$.

What remains to be proven is the full empirical formula in @GentlePurpleRain's comment on @causative's answer.

$K=1$ draws

because P1 can just play $N$ on its first move, forcing P2 to play $N$.

Assume $K\ge 2$ from now

$N=2K$ wins

First let us illustrate with the strategy in terms of cases (notation: P1 $\implies$ P2): $$ \begin{align} 0 \implies& 1\\ 1 \implies& 2\\ \ge 2 \implies& 0\ast\\ \end{align} $$ $\ast$: unless P1 is about to win, in which case exceed its play by $1$.

Why does this win? First of all, clearly P2 will always have enough coins to win by case 0 or 1. The only complication is if P1 tries to win with case "$\ge 2$": let's say $2\implies 0$ has happened for $K-1$ rounds and P1 tries to play $2$ again. In this case, P2 plays $3$. Then P1 has no coins left while P2 has $2K-3$ coins which will easily win.

$N=2K$ requires $\lceil3K/2\rceil$ moves (proof incomplete)

Consider following sequence with notation explained in the first line (where $R$ = rounds won after those plays, $C$ = coins left after those plays) $$ \begin{align} (\text{repeats})\times(\text{move})\rightarrow & R\ast P1 : P2,& C\ast P1 : P2 \\ (K-1)\times (1 \implies 2)\rightarrow & R\ast 0 : K-1,& C\ast K+1 : 2 \\ \lceil K/2\rceil\times (2\implies 0)\rightarrow & R\ast \lceil K/2\rceil : K-1,& C\ast 0 \text{ or } 1 : 2 \\ (\le 1\implies 2)\rightarrow & R\ast \lceil K/2\rceil : K, & \end{align} $$ which is a P2 win in $\lceil3K/2\rceil$ moves, which proves a lower bound for the number of moves needed to win.

It is not immediately clear that this is also an upper bound, as according to this strategy, P1 can waste $K$ moves by playing $2$, which, along with an additional $K$ moves required for P2 to win, is $2K$ moves in total. The idea to optimise this is to sometimes exceed a $\ge2$ move because P1 is so low on coins.

$N\le 2K-1$ draws

Clearly $N < K$ is a draw because there isn't enough coins to win $K$ rounds.

Assume $K\le N\le 2K-1$. Then P1 can force a draw by playing $1$ always. It threatens to win like this. P2 cannot exceed it (by playing $2$) and expect to win because $N<2K$. P2 cannot match it (by playing $1$) because this reduces to a lower $N$ and we can proceed by induction. P2 cannot play $0$ consistently and hope to get enough coins to overtake because after (the maximal) $K-1$ rounds of $1\implies 0$, $$ \begin{align} (K-1)\times (1 \implies 0)\rightarrow & R\ast K-1 : 0,& C\ast K : 2K-1 \\ \end{align} $$ which is not enough for P2 to overtake.

$N\ge 2K$ wins

Let $N=qK+r$ where $0\le r < K$. Then the strategy $$ \begin{align} 0 \implies& 1\\ 1 \implies& 2\\ \vdots&\\ q-1 \implies& q\\ \ge q \implies& 0\ast\\ \end{align} $$ wins for similar reasons to the $N=2K$ case. (Note: this may not be optimal in terms of moves) The complication to check is after $K-1$ rounds of $q\implies 0$: $$ \begin{align} (K-1)\times (q \implies 0)\rightarrow & R\ast K-1 : 0,& C\ast K+r : qK+r \\ \end{align} $$ Since $q\ge 2$, we have that $qK+r\ge \color{blue}{K} + (K+r)$, so $P2$ can win by playing one more than P1 in the next $\color{blue}{K}$ rounds.

Answer 4

Let's assume $K>0$

If you play $0$ coins for your $1st$ round, the game situation effectively has been mirrored from original and now you can force a tie if I play more than $0$ coins for my $1st$ round (by you now always copying my play).

So there is no winning strategy because we can both continue to play $0$ coins, and, because the first player who plays more than $0$ coins offers the next player the chance to force a tie.

Since: if indeed there would exist a strategy for me (second player) to win from you (first player), then, if you play $0$ coins for your $1st$ round, that gives you a strategy to win from me.

But that is impossible because we both can avoid such strategy to ever be exercised by our opponent by always playing $0$ coins.

in short: if there is a winning strategy for me, then there is a winning strategy for you, which cannot both be the case. Basically the 'copy opponent play' always works to end up in a tie.

If $K=0$

One can perhaps debate who wins, perhaps you win as first player.

Answer 5

*** This answer is invalid; it was made to answer an incorrect interpretation of the question (where $K$ is the maximum number of rounds, not the number of rounds required to win). ***

---

If $N \leq K$, the first player can always force a win or a tie by playing a single coin every round.

For any $K \ge 3$, if $N > K$, the second player can win with this strategy:

Let $n_1$ be the number of coins played by the first player this round.
Let $n_2$ be the number of coins remaining for the second player.
Let $k$ be the number of rounds remaining in the game, including the current round (assuming the coins don't run out prematurely -- that is, the total number of rounds minus the rounds already played).

For each round,

• if $n_2 - n_1 + 1 > k$, the second player should play one more coin than the first player.
• otherwise, if $n_1 = n_2 = 1$, the second player should match the first player (tie).
• otherwise, the second player should play 0 coins.

I believe you can only ever guarantee a win in one fewer than the maximum number of rounds, but I don't have a proof for that.