Nim Winning Strategy: Use XOR in the 3–5–7 Game

Check which last-token rule you are playing

The Nim winning strategy in this guide applies to normal play: remove one or more tokens from exactly one pile, and take the final token to win. ProjectGAMR starts its local two-player game with piles of 3, 5 and 7. Both players use the same device. You cannot remove tokens from two piles in a single turn.

Check that final rule before borrowing a strategy from another source. NRICH’s linked Nim activity makes the last person to take a counter lose. That is a different version. Our examples below use the site’s last-token-wins rule throughout, including when only one token remains.

Calculate the nim-sum without carrying

Write the pile sizes in binary, lining up the columns: 3 is 011, 5 is 101 and 7 is 111. Count the ones in each column. An even count contributes zero; an odd count contributes one. The result is 001, or 1 in ordinary decimal notation. This calculation is called bitwise exclusive OR, usually shortened to XOR. Applying it to all piles gives the nim-sum.

Unlike ordinary addition, there is no carrying into the next column. You are tracking parity, not counting all fifteen tokens. The position [2, 5, 7] has binary rows 010, 101 and 111; every column contains an even number of ones, so its nim-sum is zero.

Leave zero for the other player

With accurate play in this normal-play game, a nonzero nim-sum lets the player to move force a win. A zero nim-sum is losing for the player to move against an opponent who always finds the correct reply. From [3, 5, 7], take one token from the first pile to leave [2, 5, 7]. That is one winning opening, not the only one.

You can also take one from the second pile to leave [3, 4, 7], or one from the third to leave [3, 5, 6]. Each has nim-sum zero. Removing the most tokens is not the objective; passing a zero position to your opponent is. Recalculate after their move rather than repeating your opening choice automatically.

Work through a reply you can verify

Suppose you leave [2, 5, 7] and your opponent removes two from the last pile, producing [2, 5, 5]. Its nim-sum is 2 because the identical fives cancel under XOR. Remove both tokens from the first pile to leave [0, 5, 5]. The nim-sum is zero again.

Now the two remaining piles are equal. If your opponent takes three from one, take three from the other. Keep mirroring their removal in the other pile. Eventually they empty one pile and you empty its matching pile, taking the final token. This is a complete continuation for that particular reply, not a claim that every opening immediately creates two equal piles.

Why a correct reply remains available

Changing exactly one pile in a zero position changes its binary pattern, so the new nim-sum cannot remain zero. Conversely, a nonzero nim-sum has a highest column containing an odd number of ones. Choose a pile with a one in that column. XOR that pile’s size with the total nim-sum to get its target size. The target is smaller, making the reduction legal.

That reduction restores a zero nim-sum. Because every turn removes at least one token, play cannot continue forever. The empty position has nim-sum zero and no available move, which connects this calculation to the normal-play winning condition. The argument depends on those exact rules; changing the ending requires a separate analysis.

Practice the calculation before choosing a pile

Start with [3, 5, 7] and explain your first reduction aloud. Ask your partner to choose any legal reply, then count the remaining tokens before calculating again. On the browser game, set the number of tokens to take and choose one pile. Verify the displayed counts before handing over the device.

If your turn begins at zero, no move can preserve a forced win against perfect replies. You can still play on and recognise a later mistake. For review, find the earliest turn where a nonzero position was followed by another nonzero position. That identifies a missed opportunity more precisely than saying the wrong pile simply felt unlucky.

Keep exploring

FOLLOW THE SOURCE

Sources & further reading

Have a correction? Tell our editorial team.

✦ NICE. YOU LEARNED SOMETHING.