Three Drawers of Chips

Question

Three desk drawers hold 5, 8, and 12 poker chips. Two players alternate turns; a turn means choosing one drawer and removing any positive number of chips from it. Whoever takes the last chip in the room wins. You move first. Find every winning first move, and the principle that generates them.

Accepted Answer

Unique winning move: take 1 chip from the 5-drawer, leaving (4, 8, 12). The invariant (Bouton's theorem). Call a position balanced if the bitwise XOR of the heap sizes is 0. Two facts make balanced = lost-for-the-mover: 1. Every move unbalances a balanced position. A move changes exactly one heap, so it flips at least one bit of that heap's contribution; the XOR, previously 0, becomes nonzero. 2. Some move rebalances any unbalanced position. Let s ne 0 be the XOR and pick a heap h whose binary expansion contains the highest set bit of s. Then h oplus s < h (that top bit flips off), so reducing h to h oplus s is legal, and the new XOR is s oplus h oplus (h oplus s) = 0. By induction down the (strictly shrinking) total, balanced positions are exactly the losses: the terminal position (0,0,0) is balanced and lost (the previous player just took the last chip). This position. 5 = 0101, 8 = 1000, 12 = 1100: the XOR is s = 0001 = 1. Only a heap with the 1-bit set can absorb s: 5 oplus 1 = 4 works (4 < 5), while 8 oplus 1 = 9 and 12 oplus 1 = 13 would require adding chips. So the only rebalancing move is 5 to 4. From (4,8,12) you answer every opponent move by re-zeroing the XOR; the chip t

Three Drawers of Chips

Problem

Your answer

Hints

More Brainteasers & Logic to train on