Alice and Bob play a game taking turns. There is one pile of $n\geq2$ identical coins on a table.
Alice starts and with her first move she takes away at least one coin from the pile, but not all of them. After that move the next player takes at least one coin but not more than the amount of coins, which was taken away on the preceding move. The person who takes the last coin, wins.
Who has a winning strategy?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ I am curious if you invented this Puzzle (if so: RESPECT) or if you spotted it, or crafted it from existing one (and, still: RESPECT). $\endgroup$– FirstName LastNameNov 22, 2021 at 2:39
-
1$\begingroup$ I didn't invent it, a friend asked me about this. $\endgroup$– ThomasLNov 23, 2021 at 20:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
18
I think that
Alice wins unless $n$ is a power of $2$.
Proof
Clearly Alice wins all odd numbers, by removing one coin at the beginning, and it's trivial to show that Bob wins when $n$ is $2$ or $4$ so we just need to prove the statement for even numbers greater than $4$, which we'll do by induction.
We already have the base step. Suppose the premise is true for all even numbers less than $n$. We will prove it for $n$.
Suppose $n$ is a power of $2$, firstly.
If Alice removes at least half the coins then Bob can remove the rest to win the game. Suppose Alice removes some number of coins $k$ less than $n/2$. Then Bob finds the smallest power of $2$ strictly greater than $k$ ($2^m$, say) and removes $2^m-k$ coins. Note that $2^m - k \leq k$ which allows Bob to make this move. Bob can apply this general strategy after each of Alice's moves to win the game because it guarantees that it will be Alice's move whenever they land on a number of coins that is a power of 2.
To see why this is true, imagine we represent the total number of coins in binary and suppose that a move by Alice has $m$ digits in binary. Then Bob's next move guarantees that the binary representation of the remaining number of coins ends with $m$ zeroes while each of Alice's subsequent moves can have at most $m$ digits in its binary representation. This allows Bob to continue the strategy on each subsequent step and because each power of $2$ is represented as a $1$ followed by all $0$s, only Bob may arrive at these after the first move.
Now suppose $n$ is not a power of $2$.
Alice just finds the largest power of $2$ less than $n$ ($2^p$, say) and removes $n-2^p$ coins. This leaves a losing position for Bob, since $n-2^p < 2^p$ and Alice can just copy Bob's strategy from the previous paragraph.
answered Nov 14, 2021 at 22:16
-
2$\begingroup$ @FirstNameLastName n=6 is winning for Alice since 6 is not a power of 2. $\endgroup$– hexominoNov 14, 2021 at 23:09
-
1$\begingroup$ I don't think this proof is valid because the state is dependent on more than just the number of coins in the pile. "This leaves a losing position for Bob" and "... is a losing position for Alice by the assumption" are actually skipping over some important steps. $\endgroup$ Nov 15, 2021 at 16:06
-
1$\begingroup$ The losing position for Bob is actually easy to explain - leaving Bob with 2^m coins isn't the same as starting with 2^m coins, but because it only leaves Bob with fewer options it's still a losing position. However for Alice it's not so easy - for example if n=16, Alice can take two and leave Bob with n=14 but only able to take max 2. So you need to show that leaving Bob with fewer options can't prevent it from being a winning position. $\endgroup$ Nov 15, 2021 at 16:16
-
1$\begingroup$ I guess my argument would be maybe along the lines: rot13(Nsgre Nyvpr unf pubfra x naq Obo unf pubfra 2^z-x, vs Obo pbagvahrf gur tvira fgengrtl, gur tnzr jvyy orunir yvxr n frevrf bs tnzrf bs fvmr 2^z (cbffvoyl jvgu zber erfgevpgvbaf ba Nyvpr), naq gur erznvavat ahzore bs pbvaf vf vaqrrq qvivfvoyr ol 2^z naq Obo jvyy vaqrrq jva rnpu fznyyre tnzr.). $\endgroup$– tehtmiNov 18, 2021 at 5:52
-
1$\begingroup$ I am not able to understand why it is guaranteed that Bob will always win . The explanation is not very clear still. Also, not able to understand why this strategy works only when the number of coins is a power of 2 . Because, if the starting number of coins is 64 and Alice picks 5 coins then Bob will pick 3 coins. This will leave a total of 56 coins. Shouldn't Alice win now because 56 is not a power of 2 ? $\endgroup$ Nov 18, 2021 at 12:08