News and Social Media

During CLC Maths Week, we had the exciting opportunity to visit Warwick University and attend a series of fascinating talks on how mathematics applies to everyday life. The sessions covered intriguing topics such as ‘How to Get Rich Easily’ using maths, ‘Numbers in the News’, and practical advice on revising for GCSE and A Level exams delivered by a top GCSE / A Level examiner.

One talk that particularly captured my interest was “Nim, Officers, and Other Games” by Colin Wright, a mathematician and juggler. This was my first encounter with NIM, a mathematical strategy game for two players. In NIM, players take turns removing (or "nimming") objects from heaps of tokens. The game begins with any number of heaps, each containing any number of tokens. Players can only remove tokens from one heap per turn, and they can take any number greater than zero. The player unable to make a move loses, meaning the player who reduces the final heap to zero wins.

How to Play NIM

You can try this game yourself using a piece of paper. Start by writing down, for example, 4, 6, 9, and 14 in a row to represent the number of tokens in four heaps. Then, take turns removing tokens from one heap. Cross out the old number and write the new total left after your move. For example:

Initial heaps:

After first player's move (removing tokens from the fourth heap):

Some of you might want to explore the strategy by beginning with one heap, then progressing to two, three, and more heaps:

• With one heap, the first player (let's call them F) can win by taking all the tokens.

• With two heaps, the situation depends on whether the heaps are "even" (same number of tokens) or "uneven" (different numbers). If they are uneven, F can make them even by taking enough tokens from the larger heap. Conversely, if the heaps are even, the second player (S) has the advantage and can make them uneven, ensuring a win.

When three or more heaps are involved, the strategy becomes more complex. At first glance, it might seem like there’s no consistent way for F or S to guarantee a win. However, there is a mathematical strategy behind this game, and it all revolves around something called the nim-sum.

Cracking the Winning Strategy: The Nim-Sum

To uncover the strategy, follow these steps:

1. Convert the number of tokens in each heap to binary (base-2) numbers. In binary, only the digits 1 and 0 are used, each representing powers of 2. For example:

2.       Calculate the nim-sum by adding up the 1s in each column. If the total is even, write 0; if odd, write 1. For the example above, the nim-sum is:

3.       Determine the winner:

1. If the nim-sum contains any 1s, the first player (F) can guarantee a win by making the right moves.

2. If the nim-sum is all 0s, the second player (S) will win if they play correctly.

The strategy hinges on ensuring that the opponent is always left with a nim-sum of 0 after your turn. The key is to manoeuvre the game so that the final move—removing the last token—falls to you.

A Simple Explanation

By forcing your opponent to play with a nim-sum of 0, you ensure that any move they make will leave a non-zero nim-sum for you, enabling you to reset it to 0 on your next turn. However, beware! If your opponent also knows this strategy, the tables can quickly turn against you.

Tips to Win Every Time

1. Start the game with heaps that produce a non-zero nim-sum and ensure you go first (be F).

2. Alternatively, let a fair computer generate random heaps, then use your move to create a nim-sum of 0 for your opponent.

3. Keep the nim-sum calculations in mind throughout the game, and watch your friends marvel at your unbeatable strategy!

In conclusion, mastering the nim-sum strategy can make you a NIM champion and the envy of your peers. Give it a try - happy nimming!

Ann, SFC1