## Lesson 11

In this lesson, we will cover more on canonical forms. First recall that for m↑ + (*n) with m > 0, this game is positive except when (m, n) = (1, 1). Let’s consider the canonical forms of these games.

First, we know that ↑ = {0 | *}.

What about ↑* = ↑ + * ? By definition, we get:

$\uparrow * = \{0\ |\ *\} + \{0\ |\ 0\} = \{*, \uparrow\ |\ *+*, \uparrow\} = \{*, \uparrow\ |\ 0\}$

since * + * = 0 < ↑. Now let’s consider the Left option ↑. This has a Right option *. Now is it true that * ≤ ↑*. Of course! So we can replace the Left option ↑ by all the Left options of *. This gives:

$\uparrow * = \{0, *\ |\ 0\}.$

We’ll leave it to the reader to check that further simplification is impossible. So we have the canonical form of ↑*.

Next, what about 2↑ = ↑ + ↑? Again, by definition,

$2\uparrow = \{\uparrow\ |\ \uparrow*\}.$

Let’s see if move reversal takes place. Left‘s option to ↑ has the Right option *. Now is it true that * ≤ 2↑ ? Yup! So we can replace Left‘s option ↑ by all Left options of *. This gives $2\uparrow = \{0\ |\ \uparrow*\}$

Now let’s consider the Right option to ↑*. Since we already saw that ↑* = {0, * | 0}, this has Left options 0 and *. Now is it true that 0 (or *) ≥ 2↑ ? Nope to both cases! So we obtain the following canonical form:

$2\uparrow = \{0\ |\ \uparrow*\}$.

We’ll leave it to the reader to calculate the canonical forms of the following and find a pattern among them (see exercise 2).

• 2↑ + *
• 3↑
• 3↑ + *
• 4↑
• 4↑ + *

Next, let’s consider G = ↑ + *2. By definition, we have:

$G = \{*2, \uparrow, \uparrow*\ |\ *3, \uparrow, \uparrow*\}$.

Since ↑ > *2 we can erase the Left option *2. Likewise, since *3 < ↑ and *3 < ↑* we can erase the Right options ↑ and ↑*. This leaves:

$G = \{\uparrow, \uparrow*\ |\ *3\}.$

Any move reversals possible? Let’s consider the Left option ↑, which has Right option *. Since * < G, move reversal happens and we replace ↑ by the Left options of *, thus giving $G = \{0, \uparrow*\ |\ *3\}$. By the same token, the Left option ↑* has Right option 0 < G, so we shall replace ↑* by the Left options of 0, i.e. nothing! This gives us:

$\uparrow + *2 = \{0\ |\ *3\}$.

Next, calculate the canonical forms of the following and find a pattern among them (see exercise 3).

• ↑ + *3
• ↑ + *4
• ↑ + *5

### More Domineering

It turns out for small m and n, the m-by-n Domineering board has rather nice canonical forms. The following can be calculated on a computer using cgsuite:

 1 2 3 4 5 6 1 0 2 1 ±1 3 1 {1/2 | -2} ±1 4 2 +2 3/2 G 5 2 1/2 1 -1 0 6 3 {1 | -1+(+2)} {7/2 | 1} #&!?* 3/2 Out of mem 7 3 {1/2 | -3/2} {3 | 3/4} -1

where

• 2 = {{2 | 0} | 0},
• +2 = – (-2) = {0 | {0 | -2}},
• G = {0, H | 0, –H}, and H = {{2|0}, 2+(+2) | {2|0}, –2}.

There are also many sequences of Domineering configurations which admit a general formula. E.g.:

### More on Toppling Dominoes

Recall the game of Toppling Dominoes in lesson 9. We already know the following games:

• Contiguous row of n Light dominoes : n.
• Contiguous row of n Light dominoes, followed by m dominoes : {n-1 | -(m-1)}.

As a special case, a Light domino placed beside a daRk domino forms the game {0 | 0} = *. Now we can calculate the following games:

See if you can find a pattern for this game (see exercise 1).

### Exercises

1. Guess the canonical forms of the following games (the first game has n+1 Light and n daRk dominoes; the second game has n Light and n daRk dominoes). Can you prove it?

1. Write down the canonical forms of n↑ and n↑ + *. Prove it. [ For this and the next two problems, take note of the fact that ↑* is fuzzy.  ]
2. Write down the canonical form of ↑ + *m. Prove it.
3. Even more generally, write down the canonical form of n↑ + *m. Prove it.
4. Given the following two Domineering games:

simplify the following into canonical form:

1. Given the following Toads-and-Frogs games:

simplify the following games into canonical forms:

This entry was posted in Notes and tagged , , , , , , , , . Bookmark the permalink.