In this section, we introduce two variants of Nim, and explain what a bogus nim heap is.
Let's play a variant of Nim called Poker Nim. Like regular Nim, the game position consists of a set of nim heaps of sizes \(\{ n_1, n_2, \ldots , n_k \}\text{.}\) In addition, the players have their own cache of beans, of sizes \(\ell\) and \(r\) (for "left" and "right"). So there are \(r+\ell + n_1 + n_2 + \cdots + n_k\) beans in total. On your turn, you now have two possible moves: (1) you can make a regular nim move as before, taking some beans from one of the nim heaps and placing them into your personal cache, or (2) you can add some of your own beans to one of the existing heaps.
Exploration2.4.1.Poker Nim.
Play some games of Poker Nim. Start with two heaps along with the private player caches. What effect do the caches have on the game? After you have mastered two-heap Poker Nim, try some larger games.
So who wins Poker Nim? It turns out that the winner is determined in the same way as regular nim: take the nim sum \(n_1 \oplus n_2 \oplus \cdots \oplus n_k\) of the \(k\) heaps (but do not include the player caches). You are asked to prove this in the exercises. The key observation is that the type (2) move is a reversible move. If Left adds 5 beans to a heap, then Right can immediately remove those 5 beans as a response. This brings the game back into its previous position.
A nim heap with some extra, reversible moves is called a bogus nim heap. We allow bogus nim heaps in our games, provided that there is always a winner. This means that one player does have a winning strategy, and that winning player can prevent the game from going on forever. (This is why the players in Poker Nim have a limited supply of beans.) So Poker Nim is equivalent to Nim, but with bogus nim heaps.
Our second variant of Nim is called Northcott's Game. This game is played on a standard \(8 \times 8\) checkerboard. Each row of the checkerboard contains one Blue checker and one Red checker. The bLue checker must be to the left of the Red checker, but other than that, the checkers can be anywhere on that row. On her move, Left is allowed to slide one of her Blue checkers in its row (left or right), but she is not allowed to jump over the Red checker in that row. The checker must remain in the row that it started in, and cannot move off the board. Right is allowed to slide his Red checkers, again with no jumping. The winner is the player to make the last move.
Figure2.4.1.A position in Northcott's Game.
At this point, you should be a bit puzzled by this game: it is not impartial! Left can only move Blue checkers, and Right can only move Red checkers! In fact, Northcott's game is a clever disguise for Nim with bogus nim heaps. You will unmask the game in the exercises below.
Exploration2.4.2.Northcott's Game.
Play the Northcott's Game position shown in Figure Figure 2.4.1. Can you see how this game is related to Nim? Under optimal play, is this an \(\cN\)-position or a \(\cP\)-position?
