Consider the game Cram from Exercise 1.4, played on a \(1 \times n\) board for \(n \geq 2\). Let \(D_{n}\) be the Nim value of that game, so that the starting position of the \(1 \times n\) board is equivalent to a Nim heap of size \(D_{n}\). For example, \(D_{2}=1\) because the \(1 \times 2\) board is equivalent to \(* 1\).

(a) How is \(D_{n}\) computed from smaller values \(D_{k}\) for \(k

(b) Give the values of \(D_{n}\) up to \(n=10\) (or more, if you are ambitious - higher values come at \(n=16\), and at some point they even repeat, but before you detect that you will probably have run out of patience). For which values of \(n\) in \(\{1, \ldots, 10\}\) is Cram on a \(1 \times n\) board a losing game?

Exercise 1.4

The impartial game Cram is played on a board of \(m \times n\) squares, where players alternately place a domino on the board which covers two adjacent squares that are free (not yet occupied by a domino), vertically or horizontally. The first player who cannot place a domino any more loses. Example play for a \(2 \times 3\) board:

<>

Transcribed Image Text:

I I loses