Discrete Mathematics: Activities and Exercises

1.

We use the terms \(\cN\)-position (next player win) and \(\cP\)-position (previous player win) to describe a winning position and a losing position, respectively. In other words,

• An \(\cN\)-position has at least one winning move.

• A \(\cP\)-position has no winning moves.

Keep in mind, that after a player's turn, the "next" and "previous" roles switch! On Alice's turn, Alice is the next player (that is, she is about to move). On Bob's turn, Alice is the previous player, (that is, she just moved). Finally, note that we are partitioning the set \(\cX\) of game positions into two sets named \(\cN\) and \(\cP\text{.}\)

1. Rule #1 says that "an \(\cN\)-position must have at least one follower that is a \(\cP\)-position." Restate this rule incorporating "for all" and/or "there exists" quantifiers. Then prove Rule #1 by contradiction. Solution.

   \begin{equation*} X \in \cN \Longleftrightarrow \exists Y \in \cF(X) \mbox{ such that } Y \in \cP. \end{equation*}

   AFSOC that \(X\) does not have a follower \(Y\) such that \(Y \in \cP\text{.}\) Let Alice be the "next player" and Bob be the "previous player." Since every follower is an \(\cN\)-position, Alice must move to a \(\cN\)-position. However, now Bob becomes is the "next player" and therefore Bob has a winning strategy, no matter what Alice's first move was. Therefore Alice does not have a winning strategy, a contradiction.

2. Rule #2 says that "every follower of a \(\cP\)-position must be an \(\cN\)-position." Restate this rule incorporating "for all" and/or "there exists" quantifiers. Then prove Rule # 2 by contradiction. Solution.

   We have

   \begin{equation*} X \in \cP \Longleftrightarrow \forall Y \in \cF(X), \mbox{ we have } Y \in \cN, \end{equation*}

   or equivalently

   \begin{equation*} X \in \cP \Longleftrightarrow \cF(X) \subset \cN. \end{equation*}

   ASFOC that \(X\) has a follower \(Y\) that is a \(\cP\) position. Let Alice be the "next player" and Bob be the "previous player." Then Alice can move from \(X\) to \(Y\text{.}\) It is now Bob's turn, so he becomes the "next" player, and he is a losing postion. So this move from \(X\) to \(Y\) was a winning move for Alice, a contradiction.

2.

If we can partition the set \(\cX\) of game positions into sets \(\cA\) and \(\cB\) such that

• If \(Y \in \cB\) then \(\exists Z \in \cF(Y)\) such that \(Z \in \cA\text{.}\)

• If \(Z \in \cA\) then \(\cF(Z) \subset \cB\)

then \(\cA\) is the set of \(\cP\)-positions and \(\cB\) is the set of \(\cN\)-positions. Consider a one coin game of nimble, where you are only allowed to move an odd number of squares. For example, \(\cF(\{3 \}) = \{ \emptyset, \{2\} \}\) and \(\cF(\{6 \}) = \{ \{1\}, \{3\}, \{5\} \}\) Find sets \(\cA\) and \(\cB\) that satisfy the properties above. Solution.

3.

Play these games of Nim, and decide whether each is an \(\cN\)-position or a \(\cP\)-position. Write \(\cN\) or \(\cP\) next to each game, as appropriate.

4.

There is an exact correspondence between games of Nim and games of Nimble (the game we played last time). Can you figure out what the relationship is? Draw the corresponding Nimble games for each of the size Nim games above. Solution.