Welcome to the staging ground for new communities! Each proposal has a description in the "Descriptions" category and a body of questions and answers in "Incubator Q&A". You can ask questions (and get answers, we hope!) right away, and start new proposals.
Are you here to participate in a specific proposal? Click on the proposal tag (with the dark outline) to see only posts about that proposal and not all of the others that are in progress. Tags are at the bottom of each post.
Delta and Epsilon play a game with marbles Question
There are $146$ marbles in a bucket.
Delta and Epsilon play a game in which they take turns removing marbles from the bucket with Delta going first.
At each turn the player can choose to remove either $1, \ 4 \ or \ 6$ marbles from the bucket.
Whoever empties the bucket wins the game.
Could either player have a winning strategy that would ensure that they win no matter how their opponent plays?
See also:
I posted a related puzzle here:
https://proposals.codidact.com/posts/296179
Attribution:
A puzzle like this was used in the Hanoi team training for the International Math Tournament of the Towns in approximately 2016.
2 answers
And the winner is … Click here to reveal
Delta can win the game no matter how Epsilon plays.
The winning strategy is … Click here to reveal
Delta begins by removing $1$ marble leaving $145$ marbles.
Note that $145$ is a multiple of $5.$
If the bucket has a multiple of $5$ marbles when it is Epsilon’s turn to remove marbles, it is impossible for Epsilon to win on that turn because Epsilon can only remove $1, \ 4 \ or \ 6$ marbles none of which is a multiple of $5$ marbles.
If Epsilon removes $1$ marble, Delta responds by removing $4$ marbles which in total removes $5$ marbles so the bucket will again have a multiple of $5$ marbles when it is Epsilon’s turn to play.
Similarly if Epsilon removes $4$ marbles, Delta responds by removing $1$ marble.
Lastly if Epsilon removes $6$ marbles, Delta responds by removing $4$ marbles.
In all three cases, Epsilon will be left with a decreasing multiple of $5$ marbles in the bucket when it is Epsilon’s turn to remove marbles.
Eventually Delta empties the bucket ($0$ marbles which a multiple of $5$ marbles) and wins the game.
0 comment threads
Solution
Yes, by Sprague-Grundy. The same comment as I made on the related question applies.Answer to what I suppose to be the intended question
$146$ is an N-position (the next player to move wins), so Delta can win.Details
The P-positions (previous player wins) are $5k$ and $5k+2$, and the N-positions are $5k+1$, $5k+3$, $5k+4$, where we assume throughout that $k$ is an integer.From $5k$ marbles either $k=0$ and the previous player has won, or we go to one of $5k'+1$ or $5k'+4$. From $5k+2$ marbles we go to $5k'+1$ or $5k'+3$.
From $5k+1$ or $5k+4$ we can choose to go to $5k$, and from $5k+3$ we can choose to go to $5k+2$.
For those who are not familiar with this style of argument, the key points are:
- The possible game states are partitioned into two: those where the remainder after dividing the number of marbles by $5$ is $0$ or $2$, and those where the remainer is $1$, $3$, or $4$. Every game state is in exactly one of these groups.
- The game state where the game has terminated and the next player has no move ($0$ marbles left, with remainder $0$) is in the first group.
- From the first group, every legal move goes to the second group.
- From the second group, there is always a legal move to the first group.
- Therefore when it is your turn, if the game state is in the second group you should force it to the first group, and then your next turn will also be from the second group. Since you never play a state from the first group, you will never be the player to (fail to) move from the $0$ marble state.
0 comment threads