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:

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:

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,

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 . 

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:

.

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:

.

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

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 . 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:

.

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:

where

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

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?

2. 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.  ]
3. Write down the canonical form of ↑ + *m. Prove it.
4. Even more generally, write down the canonical form of n↑ + *m. Prove it.
5. Given the following two Domineering games:

simplify the following into canonical form:

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

simplify the following games into canonical forms: