This is a two-player game called \"three piles of stones\". The game goes like t

Question

This is a two-player game called "three piles of stones". The game goes like this. There are three piles of stones initially. Both players take turn. During her(his) turn, (s)he can choose any non-empty pile of stones and (s)he can take as many stones as (s)he wants. The minimal number of stones (s)he can take is 1, and the maximal number of stones (s)he can take is the amount of stones of that pile. But (s)he cannot take stones from more than one pile. For example, if a player chooses a pile of seven stone, (s)he can take 1,2,3,4,5,6,or 7 stones in that turn. The game concludes when there are no stones at all, i.e. all three piles of stones are gone. The player with the last stone(s) is the winner. Now, suppose the three piles contain 3, 4, 9 stones respectively. If you are the first-mover, please design a strategy that guarantees a win no matter what your opponent will react.

Explanation / Answer

Suppose after some nth turn there are x stones in first, y stones in second and z stones in third pile. We shall denote this state by (x,y,z).

We shall win if at the end of one of our turns the game reaches (0,0,0). And the initial state of the game is (3,4,9).

Let us write down the state of the game in binary then winning position is (0,0,0) and initial position is
(0011,0100,1001). Notice that if we count the number of ones in the place of 1,2,4 and 8 in the winning state, it is 0+0+0 in each place. Thus if we can make sure that at the end of each of our turn the total number of 1s in each places in binary expansion of the game state is even then we shall win.

The key idea here is that if there are even number of ones in each place, then it is impossible to get to a state in next turn where there is also even number of ones in each place. (This is because we are removing stones from only one pile, thus the chances are that the number of ones in a given place will either get added by one or subtracted by one or remain unchanged. Since at least one stone has to be removed the total number of ones in at least one place will change. But since this number was even to begin with after the turn it will become odd). Also it is always possible to get to a state with even number of ones in each place from any other state.

Thus our first move shall be to remove 2 from 3rd pile to get to
(0011,0100,0111). In this state clearly there are even number of ones in each place; 1+1= 2 in one's place; 1+1=2 in 2's places, 1+1 =2 is fours place and 0 in all other places.

Now the opponent can remove stones from only one pile. Irrespective of whatever opponent does they will end up not having even number of ones in all place. But in very next turn making adjustment accordingly we can get to such a state. And keep on staying at such a state, eventually winning.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.