Games, graphs, and machines
MATH2301, Semester 2, 2024

I am using “reading” as a short form form “absorbing new mathematics”. It also applies to watching videos.

Read actively. Pause often to think about what you have just read. Reading maths is slow. It is closer to reading poetry than reading a novel. You need to think deeply about every sentence, and it is common for something to take a long time to sink in.

What to think while reading? If you have read a definition, pause and try to construct examples yourself. Also try to construct non-examples. After that, create even more examples and non-examples. Once you feel like you have a rich set of examples and non-examples, continue. If the text gives some examples and non-examples, read them. They will undoubtedly enrich your understanding. If you feel like you do not have a rich set of examples, ask me (or someone else).

If you have read a statement (a proposition or a theorem), pause and try to find situations where the statement applies. What does the statement say in this situation? Does it say anything surprising? Try to find other situations. Also try to find situations where the statement does not apply. Try to play devil’s advocate by finding situations where the statement is wrong. Assuming the statement is accurate, this will fail, but you will learn a lot from trying.

If you have read an explanation (a proof, for example), pause and try to find the key ideas in the explanation. Try to find a concrete example where the explanation applies, and understand it in that example. Then repeat with another example.

Use the problems you see in lectures, workshops, quizzes, and homework to test your understanding. After reading a problem, if

1. you understand what exactly is being asked, and
2. you can think of ways to get started,

then your understanding is good. It is not expected that you immediately see how to solve the problem. But if you are stumped, or unable to get started, then your understanding is incomplete. In this case, go back to the reading and revisit the related concepts.

Do not look at the solution to any problem without having spent sufficient time attempting it on your own. If you do so, you are wasting a problem (and problems are valuable!).

It is not uncommon to feel stumped after reading a problem. One reason is that you are not familiar with the relevant ideas. But even if you are, it can be difficult to get started. Here are some strategies to get started.

Your first attempt does not have to lead to a solution. So try something and see if it leads anywhere. A failed attempt will often generate new ideas.

The problem will often involve new terminology. Break it down until you have restated it in terms you are familiar with. As you get used to the new terminology, this process will get easier.

Experiment! If the problem talks about a number \(n\), experiment by taking small values of \(n\). If it talks about a graph, try with a some small examples of graphs. If it talks about a function, test with some functions you know. This is where it helps to have a handy collection of examples.

Try to find the corresponding simplest problem. If the problem talks about a big number, try the same problem for smaller numbers. If the problem talks about all graphs, try with some small graphs.

While solving your assignments, you will typically work in two phases.

1. The solving phase: this is when you are actually trying to find the answers to the questions.
   1. First, you should think about the problem on your own.
   2. Next, you are welcome and encouraged to collaborate with other students while you are in the solving phase. It is often by working productively with peers that you will learn the most. Collaboration means that all of you are thinking about the problem together and coming up with a solution together. You should move on to the next phase once you know more or less how to solve the problem.
   3. You are encouraged to go to office hour and to the MSI drop-in sessions to get clarifications.
2. The write-up phase: this consists of writing up your solutions for submission, once you know more or less how to solve the problems.
   1. You must do this entirely by yourself. Work alone when you are writing.
   2. If you collaborate with anyone else, copy (parts of) solutions from someone else, copy from pictures taken of the board, or ask someone else to write your solutions, you are violating the academic integrity policy.
   3. If you get stuck while writing, you can go back to the previous phase to collaborate/ask questions to your instructors, but once again when you are back to writing the solution, it must be done independently.

Additionally, keep in mind the following.

1. When you are writing up your solution, you must write down at the top of your solution sheet a list of your collaborators, as well as any external resources you used. It is a violation of the integrity policy if you do not acknowledge the sources from which you received help. However, you do not need to cite help received from office hour, demonstrators, or the MSI drop-in session.
2. Asking someone else to give you the solutions, or paying someone else to give you the solutions, is a violation of the integrity policy. Use of websites such as Chegg, CourseHero, etc for getting assignment solutions is a violation of the integrity policy.

If you are ever unsure about whether something is or is not allowed, ask the instructor for clarification. You will never get into trouble for asking for clarification about what is acceptable. However, you will face serious consequences if you fail to follow the academic integrity policy.

1. Consider the relation on \(\mathbb{Z}\) described by \[\{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid (a^2 - b^2)\text{ is an integer multiple of }5\}.\] Show that it is an equivalence relation, and find the equivalence classes.
2. Find the smallest non-negative integer \(b\) that satisfies the following equalities, or justify why it does not exist. The number \(d\) is the modulus.
   1. \([17] + [b] = [2]\) with \(d = 7\).
   2. \([3b] = [0]\) with \(d = 6\).
   3. \([3b] = [1]\) with \(d = 6\).
3. Find the last digit of \(3^{101}\) (written in decimal).
   Hint: In other words, identify \([3^{101}]\) among the classes \([0],[1],\dots,[9]\) modulo 10.
4. In class, we saw that modulo \(d\) it is possible to have \([a] [b] = 0\) but neither \([a] = 0\) nor \([b] = 0\). Prove that if \(d\) is a prime number, this does not happen. That is, if \([a] \cdot [b] = [0]\) modulo a prime number \(p\), then \([a] = [0]\) modulo \(p\) or \([b] = [0]\) modulo \(p\).

1. Find a non-zero \(5 \times 5\) matrix whose square is zero.
2. Let \(d = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11\). Let \(V\) be the set of positive divisors of \(d\).
   1. Put an edge \(v \to w\) if \(v \neq w\) and \(v\) divides \(w\). That is, if \(w\) is a successor of \(v\) in the divisor poset, and \(v \neq w\). Let \(A\) be the adjacency matrix of the resulting graph. What is the smallest \(n\) such that \(A^n = 0\)?
   2. Does your answer change if we only put an edge \(v \to w\) when \(w\) is an immediate successor of \(w\)?

3. Consider the following graph.

   Calculate for a few values of \(k\) the number of length \(k\) paths from \(a\) to itself. Can you find (and perhaps prove!) a pattern?

4. Consider the 3-petalled flower graph

   Let \(A\) be the adjacency matrix. Describe \(A^{100}\) and \(A^{101}\).

   What happens if you change the number of petals?

In all problems, “binary string” refers to any string or word on the alphabet \(\Sigma = \{0,1\}\). Unless otherwise specified, our alphabet is always \(\Sigma = \{0,1\}\).

For this worksheet, make sure to discuss actively with your groupmates! Coming up with regexes that match what you want them to match, as well as describing the languages of given regexes, takes a lot of practice. It is a creative process and there is a lot of room for error. But you will learn the tricks of the trade quicker if you discuss frequently with others.

In all the problems, the alphabet is \(\{0,1\}\).

1. Show that the following languages are not regular by (a) a pumping-lemma argument and (b) using the Myhill-Nerode theorem.

   It takes practice to be able to apply either of the two strategies. Do not be discouraged if you find it difficult. It is difficult!

   1. \(L = \{0^m 1^n \mid m \neq n\}\).
   2. \(L = \{0^{n} \mid n \text{ is a power of 2}\}\).

2. In this problem, we see how the process of going from an NFA to a DFA can produce exponential blow-up in size.

   Let \(L\) be the set of strings whose \(10\)-th position is \(1\) (so the string has to be at least 10 letters long).

   1. Construct a DFA/NFA for \(L\). It should have about 10 states.
   2. Using it, construct an NFA for \(L^{\rm rev}\). Describe \(L^{\rm rev}\) in words.
   3. Think about converting the NFA for \(L^{\rm rev}\) to a DFA. Convince yourself that the conversion process would produce a DFA with about \(2^{10}\) states.
   4. Prove that a DFA for \(L^{\rm rev}\) cannot have fewer than \(2^{10}\) states. To do so, show that all strings of length \(10\) are inequivalent under the Myhill-Nerode equivalence relation \(\sim\).
3. Choose your favourites among the games we discussed in class (subtraction game, chomp, hackenbush, nim), and play them in your group. Can you find winning strategies for certain cases? Once you have played a couple of rounds, try to draw some small game graphs and label them by N and P. Did you use the best strategy?

1. (Warm up) Remember the rules to label states as P or N.
   1. If a state is a sink state (no outgoing arrows), we label it \makebox[3em]{\hrulefill}.
   2. If a state has an outgoing arrow to a P state, we label it \makebox[3em]{\hrulefill}.
   3. If all outgoing arrows of a state are N, we label it \makebox[3em]{\hrulefill}.
2. (Warm up) Can there be an arrow \(N \to N\)? \(P \to P\)? \(P \to N\)? \(N \to P\)?
3. Draw the game graph of \(2 \times 3\) chomp and label it with N and P.
4. Remember what it means to add two games. Find two N games \(G_1\) and \(G_2\) such that \(G_1 + \operatorname{Nim}(2,3)\) and \(G_2 + \operatorname{Nim}(2,3)\) have different outcomes (N vs P).
5. The game of Wyt rooks is played as follows. We start with two rooks placed on two squares of a chessboard. A move consists of moving one of the rooks any positive number of squares downward or leftward (but not both). Rooks can occupy the same square and move past each other. As usual, the player who cannot make a move loses.
   1. Play this game with your group and determine some winning and losing positions.
   2. Try to convert this game into some form of nim.

6. (Open-ended) Euclid’s game is defined as follows. The starting position is a pair of positive integers \((a,b)\). A move consists of subtracting a non-zero multiple of the smaller number from the larger number, ending up again with a pair of positive integers. In particular, any position of the form \((n,n)\) is a P position.

   Play this game with your group and determine some other non-trivial P and N positions. Do you see a pattern? Bonus/challenge: Can you find a pattern, and who has a winning strategy?

The goal of this worksheet is to practice computing Grundy labels and using them to find winning moves.

1. Consider the \(1,2\)-subtraction game starting with the initial state \(10\). Find the Grundy labels of the game states.
2. Let \(G\) be the \(1,2\)-subtraction game with initial state \(10\).
   1. Find the Grundy label of \(G + \operatorname{Nim}(2,4,5)\), using that the Grundy label of \(G+H\) is the (xor) sum of the Grundy labels.
   2. Find all winning moves for the first player. Remember that a winning move puts the opponent in a \(P\)-position, which is a position with Grundy label \(0\).

3. Repeat (2) for combinations of games of your choice taken from all the games we have seen: nim, Chomp, poset chomp, nimble, Euclid’s game, Grundy’s game, subtraction game with different parameters, and so on.

   For the exam, you are not expected to know the rules of these more esoteric games. But you should know the rules of nim, chomp, and poset chomp.

While solving your assignments, you will typically work in two phases.

1. The solving phase: this is when you are actually trying to find the answers to the questions.
   1. First, you should think about the problem on your own.
   2. Next, you are welcome and encouraged to collaborate with other students while you are in the solving phase. It is often by working productively with peers that you will learn the most. Collaboration means that all of you are thinking about the problem together and coming up with a solution together. You should move on to the next phase once you know more or less how to solve the problem.
   3. You are encouraged to go to office hour and to the MSI drop-in sessions to get clarifications.
2. The write-up phase: this consists of writing up your solutions for submission, once you know more or less how to solve the problems.
   1. You must do this entirely by yourself. Work alone when you are writing.
   2. If you collaborate with anyone else, copy (parts of) solutions from someone else, copy from pictures taken of the board, or ask someone else to write your solutions, you are violating the academic integrity policy.
   3. If you get stuck while writing, you can go back to the previous phase to collaborate/ask questions to your instructors, but once again when you are back to writing the solution, it must be done independently.

Additionally, keep in mind the following.

1. When you are writing up your solution, you must write down at the top of your solution sheet a list of your collaborators, as well as any external resources you used. It is a violation of the integrity policy if you do not acknowledge the sources from which you received help. However, you do not need to cite help received from office hour, demonstrators, or the MSI drop-in session.
2. Asking someone else to give you the solutions, or paying someone else to give you the solutions, is a violation of the integrity policy. Use of websites such as Chegg, CourseHero, etc for getting assignment solutions is a violation of the integrity policy.

If you are ever unsure about whether something is or is not allowed, ask the instructor for clarification. You will never get into trouble for asking for clarification about what is acceptable. However, you will face serious consequences if you fail to follow the academic integrity policy.

1. Let \(S\) be the set of squares on a standard \(8 \times 8\) chessboard. Consider the following relations on \(S\).

   1. \(B = \{(s,t) \in S \times S \mid t \text{ is reachable from }s\text{ by a sequence of zero or more bishop moves.} \}\)
   2. \(R = \{(s,t) \in S \times S \mid t \text{ is reachable from }s\text{ by a sequence of zero or more rook moves.} \}\)
   3. \(K = \{(s,t) \in S \times S \mid t \text{ is reachable from }s\text{ by a sequence of zero or more knight moves.} \}\)

   It turns out that all of these are equivalence relations (you can check this privately, but you don’t have to justify it). In each case, determine how many equivalence classes there are.

2. Fix a modulus \(d\). Recall that \(\mathbf{Z}/d \mathbf{Z}\) is the set of equivalence classes of integers modulo \(d\). Let us try to define the operation of exponentiation on \(\mathbf{Z}/d \mathbf{Z}\) as follows. Given \(A, B \in \mathbf{Z} / d \mathbf{Z}\), we pick an \(a \in A\), a positive \(b \in B\), and declare \[ A^B = [a^b].\] Is this operation well-defined? Justify your answer.
3. Consider modular arithmetic with the modulus \(d = 10\). For each equivalence class \([x] \in \mathbf{Z}/d \mathbf{Z}\), determine whether or not \([x]\) has a multiplicative inverse, and if yes, find the inverse. That is, figure out whether there is some \([y]\) such that \([x]\cdot[y] = [1]\).
   Bonus (not to be turned in): Can you find a pattern here? When does \([x]\) have a multiplicative inverse? Does a number ever have more than one inverse?
4. Take the modulus to be \(d = 7\). Show that if \([3x] = [5]\) modulo \(7\), then \([x] = [4]\).

1. Consider a graph whose adjacency matrix is \[A = \begin{pmatrix}1&1&1\\0&1&1\\0&0&1\end{pmatrix}.\] Find the number of paths of length \(4\) from \(1\) to \(3\).
2. 1. Find (without explicit calculation) an example of a \(4 \times 4\) nonzero adjacency matrix such that all powers of this matrix beyond the 10th power are zero. Justify briefly.
   2. Is it true that the 8th power of any such matrix (not just your example!) must also be zero?
   3. Is it true that the cube of any such matrix (not just your example) must also be zero?

3. Let \(G\) be the directed pentagon

   

   Let \(A\) be the adjacency matrix of \(G\). Describe all positive powers of \(A\).

4. Let \(G\) be the directed snail

   

   Let \(A\) be the adjacency matrix of \(G\). Describe all positive powers of \(A\).

5. Let \((S, \preceq)\) be a finite poset. Let \(G\) be the directed graph of the relation \(\preceq\) and let \(A\) be the adjacency matrix of \(G\). Let \(I\) be the identity matrix of the same size as \(A\) (this is the matrix that has 1s on the diagonal and zeros elsewhere). True or false: some positive power of \(A-I\) must be zero. If true, justify it. Otherwise, give an example where no positive power of \(A-I\) is zero.

1. A directed graph is called strongly connected if for every \(i\) and \(j\), there is a path from vertex \(i\) to vertex \(j\).

   Select true or false.

   1. A graph with adjacency matrix \(A\) is strongly connected if and only if for some \(n\), the boolean power \(A^{*n}\) has all entries equal to \(1\).

   2. A graph with adjacency matrix \(A\) is strongly connected if and only if for some \(n\), the boolean sum \[A +A^{*2} + \cdots + A^{*n}\] has all entries equal to \(1\).

      (Corrected. Previously, the boolean sum started at \(I\).)

   If the statement is true, you should be able to justify it. Otherwise, you should be able to give a counter-example. But you need not turn in the justification or counter-examples.

2. Let \(G\) be a graph. The transitive closure of \(G\) is the graph \(G^+\) with the same vertices as \(G\), but in \(G^{+}\), we have an edge from \(v\) to \(w\) if there is a path in \(G\) from \(v\) to \(w\).

   Let \(G\) be the graph of the relation \(R = \{(a,b) \mid 0 \leq b - a \leq 2\}\) on the set \(S = \{1,2,3,4\}\). Draw \(G\) and \(G^+\). Write down the adjacency matrices of both graphs.

3. We say that \(G\) is transitive if \(G = G^+\). Let \(A\) be the boolean adjacency matrix of \(G\). Prove that \(G\) is transitive if and only if \(A = A + A^{*2}\) (boolean addition).

   \noindent Caution: There is no subtraction in boolean arithmetic. So if \(x+y = x+z\), then you cannot conclude that \(y = z\).

4. Using the criterion in the previous problem, determine if the following adjacency matrices define transitive graphs:
   1. \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\)
   2. \(\begin{pmatrix} 1&1&0 \\ 0&1&1 \\ 0&0&1\end{pmatrix}\)
   3. \(\begin{pmatrix} 0&1&1 \\ 0&0&1 \\ 0&0&0\end{pmatrix}\)

5. Find (using weighted adjacency matrices) the minimum cost of paths between any pair of vertices in the following graph. Assume that each vertex has loops of length 0 (not shown).

   

1. Consider the following Markov chain:

   

   1. What is the probability of transitioning from \(1\) to \(1\) after 2 steps?
   2. Let \(A\) be the transition matrix. Find \(\lim_{k \to\infty} A^k\).
2. Consider the Markov chain
   1. Does the Perron-Frobenius theorem apply?
   2. Is the graph strongly connected?

   3. Define a relation \(\sim\) on the set of vertices by saying \(v \sim w\) if

      1. \(v = w\) or
      2. there is a path from \(v\) to \(w\) and a path from \(w\) to \(v\).

      Convince yourself (but do not turn in) that this is an equivalence relation. Write down the equivalence classes.

3. Let \(S = \mathbf{Z}/5 \mathbf{Z} - \{\overline 0\}\). On the board, I have written the element \(\overline 1 \in S\). At every step, I consider the number \(a\) on the board. If \(a\) is a square modulo \(5\), I erase \(a\) and replace it with one of the two square roots (chosen at random with equal probability). If \(a\) is not a square modulo \(5\), I erase \(a\) and write \(\overline 2 \cdot a\).
   1. Draw a weighted directed graph that models the game.
   2. Let \(A\) be the transition matrix. Use the Perron-Frobenius theorem to find \(\lim_{k \to \infty} A^k\).

4. Consider the Markov chain of snakes and ladders where the game ends if we jump to the 100th square or beyond. There are no ladders or snakes. In a computer program of your choice, construct the trasition matrix of this game. Use it to answer the following questions.

   1. Starting at 0, what is the most likely position after \(20\) moves.
   2. After \(30\) moves, what is the probability that the game has ended?

   If you use sage, you may fill in the following snippet. You can copy/paste and evaluate the snippet at https://sagecell.sagemath.org/.

   import numpy
   A = matrix(QQ,100,100)
   for i in range(0,100):
       for j in range(0,6):
           jump = i+j+1
           if (jump < 100):
               A[i,jump] = 1/6
   
   # We manually fill the entries where jump goes beyond 99.
   A[99,99] = # Fill in
   A[98,99] = # Fill in
   A[97,99] = # Fill in
   A[96,99] = # Fill in
   A[95,99] = # Fill in
   A[94,99] = # Fill in
   
   # Fill in other statements depending on what you want to compute.
   

   You may find the following helpful.

   • M = A^(10) Computes the 10th power of A and stores it in M.
   • M[i,j] gives the \((i,j)\) entry of \(M\).
   • M[i,j].n(digits=2) gives the \((i,j)\)th entry in decimal with 2 digits of precision.
   • numpy.argmax(M[i]) gives the position of the maximum entry in M[i].

   We fill in the missing entries as follows.

   import numpy
   A = matrix(QQ,100,100)
   for i in range(0,100):
       for j in range(0,6):
           jump = i+j+1
           if (jump < 100):
               A[i,jump] = 1/6
   
   # We manually fill the entries where jump goes beyond 99.
   A[99,99] = 6*1/6
   A[98,99] = 6*1/6
   A[97,99] = 5*1/6
   A[96,99] = 4*1/6
   A[95,99] = 3*1/6
   A[94,99] = 2*1/6
   

   The most likely position after 20 moves is the largest entry is the first (zeroth) row of \(A^{20}\).

   print(numpy.argmax((A^20)[0]))
   

   The probability that the game has ended after 30 moves is the \((0,99)\) entry of \(A^{30}\).

   print((A^(30))[0,99].n(digits=2))
   

1. Let \(\Sigma = \{0,1\}\). For each language \(L\) described below, write down a regular expression \(r\) such that \(L(r) = L\). That is, the strings of \(\Sigma^*\) that match \(r\) are exactly the strings of \(L\). Be careful to make sure that nothing else matches the regular expression you write down! Justification is not required.
   1. \(L = \{w \in \Sigma^\ast \mid w \text{ starts with a }1\}\)
   2. \(L = \{w \in \Sigma^* \mid w \text{ all the ones in }w\text{ are next to each other in a single block}\}\)
   3. \(L = \{w \in \Sigma^\ast \mid w \text{ contains an even number of zeroes}\}\)
2. Let \(\Sigma = \{a,b,c\}\). For each regular expression \(r\) written below, describe in words the language \(L(r)\). Justification not required.
   1. \(r = (\epsilon|bc|c)(abc)^*(\epsilon|a|ab)\).
   2. \(r = ((b|c|\epsilon)^*a(b|c|\epsilon)^*a(b|c|\epsilon)^*a(b|c|\epsilon)^*)^*\)
3. Let \(\Sigma = \{0,1\}\) and \(L\) be the language \[ L = \{w \mid \text{ the number of occurencess of }01\text{ in } w\text{ is equal to the number of occurencess of } 10.\}\] For example, the word \(010\) is in \(L\) because it has one occurences of \(01\) and one of \(10\). The word \(01101\) is not in \(L\) because it has 2 occurences of \(01\) but only one of \(10\). Does there exist a regular expression \(r\) such that \(L = L(r)\)? If yes, find one. If not, explain why not.
4. Let \(L \subseteq \Sigma^\ast\) be a language. The complement of \(L\), denoted \(L^c\), is the complement of \(L\) in \(\Sigma^\ast\). That is, for every \(w \in \Sigma^\ast\), we have \(w \in L^c\) if and only if \(w \notin L\).
   1. Given a DFA \(M\) recognising a language \(L = L(M)\), explain in words how to construct a DFA \(M'\) such that \(L(M') = L^c\).
   2. Construct a DFA recognising the following language: \[L = \{w \in \Sigma^* \mid \text{every odd position of }w\text{ is }1\}.\] (Assume that we start indexing at 1, not 0.) Justification not required.
   3. Now use your method from the first part to draw a DFA for the complement of the language \(L\) above. Justification not required.

1. Construct an NFA recognising the following languages. Justifications not required.
   1. \(L = \{w \mid w\text{ ends with }00\}\).
   2. The language \(L = L(1^*0^*1^*)\).
2. Convert the following regular expressions to equivalent NFAs. (In each case, break down the given regex into manageable pieces such that you can directly construct a DFA/NFA for each “piece”. Then combine the pieces using the procedures we discussed in class.)
   1. \(r = (0|1)^*000(0|1)^*\)
   2. \(r = (((00)^*(11))|01)^*\)

3. 1. Convert the following NFA into an equivalent DFA.

      \begin{center} \begin{tikzpicture}[node distance=2cm] \node[state, initial, accepting] (q0) {$q_0$}; \node[state, accepting] (q1) [right of=q0]{$q_1$}; \path[->] (q0) edge node[above] {$0,1$} (q1) (q0) edge[loop above] node{$0$} () (q1) edge[loop above] node{$1$} () ; \end{tikzpicture} \end{center}
   2. Let \(L\) be the language of the DFA above. How many equivalence classes does \(\sim_L\) have? Justify your answer.

4. Let \(L\) be the language \[ L = \{w \mid \text{Read in binary, the number } w \text{ is divisible by 3}\}.\] Is \(L\) recognised by an automaton? If yes, draw an DFA/NFA for \(L\). Otherwise, justify why an automaton does not exist.

   We make the convention that leading \(0\)s do not affect the number. So the number \(00011\) is the same as the number \(11\), which is the number three.

1. Convert the following DFAs into equivalent regular expressions. Show your work, but you need not give full justification.
   1. \mbox{}
   2. \mbox{}
2. Show that the following languages are not regular using the pumping lemma and the Myhill-Nerode theorem (both). For the pumping lemma, assume (for contradiction) that there is a recognising DFA with \(n\) states. Clearly state the string you use for pumping. For the Myhill-Nerode theorem, clearly describe an infinite set of non-equivalent strings.
   1. \(L = \{0^k 1^l \mid k < l\}\).
   2. \(L = \{0^{n} \mid n \text{ is a square.}\}\)

3. Draw the game graph for the following version of the subtraction game. We start with \(12\) blueberries and are allowed to eat 1, or 2, or 3 at a time. The person to eat the last blueberry wins.

   Label the graph with \(N\) and \(P\) labels.

1. Grundy’s game is defined as follows. The starting position is some number of piles of berries. A move consists of taking one pile of berries, and dividing it into two non-empty piles of unequal sizes. For example, a pile of size \(4\) can only be split into \(1/3\), whereas a pile of size \(5\) can be split either as \(1/4\) or as \(2/3\). The person who can’t make a move loses: at this point, the game board will only have piles of sizes either 1 or 2.

   Draw the game graph starting at the position \(6\), labelling each position as either \(N\) or \(P\). Consider the piles to be unordered; that is, a position such as \((1,4)\) is considered to be the same as the position \((4,1)\).

   No justification is required.

2. Recall poset chomp. We start with a finite poset \(S\). A move consists of removing an \(a \in S\) together with all \(b \in S\) with \(a \preceq b\).

   Let \(S\) be the divisor poset of \(12\) except the integer \(1\). So \(S = \{2,3,4,6,12\}\) and \(a \preceq b\) if \(a\) divides \(b\). Using strategic labelling on the game graph, determine if the following positions are N or P:

   1. \(\{3\}\)
   2. \(\{2,4\}\)
   3. \(\{2,3,4\}\)
   4. \(\{2,3,4,6,12\}\)
3. Determine if the following nim games are P or N.
   1. \(\operatorname{Nim}(3,4,5)\)
   2. \(\operatorname{Nim}(m,m,n)\) where \(m, n > 0\).
   3. \(\operatorname{Nim}(m,m,m,m)\) where \(m > 0\).
   4. \(\operatorname{Nim}(m,n)\) where \(m \neq n\).
   5. \(\operatorname{Nim}(m,2m,4m,8m)\) where \(m > 0\).
4. The game of nimble is played on a line of squares labelled \(0, 1, 2, 3, \ldots\). There are \(n\) coins placed on the squares, with perhaps more than one coin on a single square. A move consists of taking one of the coins and moving it to any square on the left, possibly moving over some coins, and possibly onto a square already containing one or more coins. The players alternate moves and the games end when all coins are on the square labelled \(0\).
   1. Convince yourself (but do not turn in) that this game is just nim in disguise.
   2. Suppose the coins are initially placed on the squares \(4, 8, 11\). This is an N position. Find all possible winning moves. Express your answer as a triple \((a,b,c)\) denoting the positions of the coins. For example, \((3, 8, 11)\) is a valid move (first coin moved from 4 to 3). And so is \((4, 0, 11)\), but not \((3,0,11)\).

This is a short assignment because it is the final week, and you probably have many other things to do.

In the game \(\operatorname{Chomp-the-graph(G)}\), we start with a finite undirected graph \(G\). Two players take turns removing either a vertex or an edge of \(G\). When a vertex is removed, all edges adjacent to it are automatically removed. When an edge is removed, no other vertices (or edges) are removed. As usual, the player who cannot make a move loses.

Find the Grundy value of \(\operatorname{Chomp-the-graph}(G)\) for the following \(G\).

1. \mbox{}
   

   

2. \mbox{}
   

   

3. \mbox{}
   

   

   Using the Grundy values, find all the winning moves for the first player.

4. (Food for thouht; not to be turned in) Can you spot any patterns in \(\operatorname{Chomp-the-graph(G)}\) for various \(G\)? For example, if \(G\) is a chain of \(n\) vertices, what is the Grundy value? What about other kinds of graphs?
5. (Food for thouht; not to be turned in) Write a computer program that takes a graph \(G\) as input and computes the Grundy value of \(\operatorname{Chomp-the-graph}(G)\).