Tzaloa 2015 game problem (piles with $1,2,4 \dots 2^{19}$ coins each)

152 Views Asked by At

We have $20$ piles with $1,2,4,8\dots 2^{19}$ coins repectively and two players. In each turn a player must select five piles that have at least one coin and remove exactly one coin from each. Player $A$ begins and player $B$ follows. The first player who cannot select five non-empty piles loses and the other one wins.

Which player has the winning strategy and which is the strategy? I feel like there should be an easy strategy which comes from some invariant but every strategy I have tried runs into complications at the later stages of the game. One thing which may or may not help is that each pile has more coins than all of the smaller piles combined. I have tried recursion, and a strategy which relies on making sure the piles that are emptied are the $16$ smallest and always trying to keep a number of coins that is $0\bmod 6$ on the $16$ smallest piles, however this strategy fails at the end.

1

There are 1 best solutions below

4
On BEST ANSWER

Hint: By parity, Player B can guarantee that he can duplicate Player A's move.

The only concern is if Player A drew from the 1 pile. Deal with that.