## Lesson 8

In this lesson, we will further familiarise ourselves with games involving numbers. At the end of the lesson, we will encounter our first positive infinitesimal: the “up” ↑. Here, an **infinitesimal** is a value which is strictly between –*r* and *r* for any positive (dyadic) rational number *r*. We saw in the last lesson that **n* is an infinitesimal for any *n*, but these are *fuzzy* games. The game ↑ is positive, i.e. 0 < ↑ < *r* for any positive rational *r*.

### Toads-and-Frogs

Here’s an interesting game which can be analysed effectively using numbers. Without CGT, such a detailed analysis of the game would be difficult!

The game of **Toads-and-Frogs** is played on several rows of squares as above, where each square contains *at most* one creature. Each creature can only move in the direction it’s facing. E.g. in the first row, the toads in the first and third square can only go right, and the frog in the fourth square can only go left. By convention, player *Left* controls the *TOads* which go from Left to Right, while player *Right* controls the *FROgs* which go from Right to Left.

At each player’s turn, he may pick up one of his creatures and perform one and only one of the following moves:

- move one square in its direction and land on an empty square; or
- jump over an
*opponent*‘s creature and land onto an empty square.

Play proceeds until a player loses for having no available moves.

*Stop and think* : how do we get the negative of a Toads-and-Frogs game? [ Answer (highlight to read) : we reflect the row about a vertical axis, so that all the toads facing right become frogs facing left, and vice versa. ]

### Numbers in Toads-and-Frogs

In the case where there’s one toad and one frog in a row, the solution is usually a number or a * so analysis is quite easy. However, if there’s more than one frog / toad, the situation can become rather complicated.

For starters, consider the following configurations:

Instead of tracing through the whole game tree of each configuration, it is much more efficient to systematically consider a row with a single toad and a single frog. For a row in which the animals have already jumped past each other, it is easy to compute the value. Next, we start from the case where the frog and toad are side-by-side facing each other.

*Examples*

- For the first row, if
*Right*starts, he has no move available. On the other hand, if*Left*starts, the resulting configuration has 3 free moves for*Left*and 1 free move for*Right*. Thus, the first row = {3-1 | } = {2 | } = 3 by the Simplicity Rule. - For the second row, if
*Right*starts, the resulting configuration has 4 free moves for*Left*and no move for*Right*. On the other hand, if*Left*starts, the resulting configuration has 2 free moves for*Left*and 2 free moves for*Right*. Thus, the second row = {2-2 | 4} = {0 | 4} = 1 by Simplicity Rule.

Next consider the case where there’s an empty space between them.

E.g. let’s consider the first row. If *Left* starts, the resulting game is 1, as we saw above. If *Right* starts, the resulting game is 3. Thus the overall game is {1 | 3} = 2. Now we’ll leave it to the reader to fill in the remaining entries…

To check your answers, click here.

Next we consider the case where there are exactly two toads (going *Left* to right) and two frogs (going *Right* to left). There are altogether 30 such configurations. Compute and simplify them as much as you can. [ *Hint: recall that a game where the second player wins is a zero game*. ] For the answer, click here.

### A Positive Infinitesimal Game

The last 3 games are of particular interest to us. Let’s label

and .

The final game in the diagram is then equal to . In a later lesson, we will learn another simplification rule, which will enable us to show that this is equal to *.

For now, let’s look at ↑ = {0 | *}. The interesting thing is that this game is positive, yet it is less than any positive number. The first claim is easy; as for the second claim, let us use the following useful comparison tool.

Theorem: Consider two gamesand ,

where all options are identical except A and A’, where A ≥ A’. Then we must have G ≥ H.

Similarly, if we replace Right option X by X’ where X ≥ X’, then the resulting game H also satisfies G ≥ H.

* Proof*: We need to show that in

*G*–

*H*, if

*Right*starts then

*Left*wins. The strategy for

*Left*is simple: whatever his opponent does in one component, he just mirrors in the other. The only problem occurs when

*Right*tries moving (-

*H*) to (-

*A’*). To counter this,

*Left*just moves

*G*to

*A*, thus leaving

*A*–

*A’*for

*Right*. Since this game ≥ 0 and

*Right*goes next,

*Left*wins. ♦

** Warning** : If

*A*>

*A’*, it does not follow that

*G*>

*H*(see exercise 1).

Now we can show that:

For any n > 0, we have 0 < ↑ < 1/2

^{n}.

Indeed, recall that we have * < 1/2^{n} for any positive integer *n*. Hence, we have ↑ = {0 | *} ≤ {0 | 1/2^{n}} = 1/2^{n+1} < 1/2^{n}. In fact, it turns out that any finite number copies of ↑ is smaller than 1/2^{n} (see exercise 2).

Finally, we have the following result:

↑ is confused with *, i.e. ↑* is a first-player win.

For other Nim values however, we have:

↑ is larger than *2, *3, *4, … .

Also, for more copies of ↑, we have:

If m > 1 and n ≥ 0, then m↑ is larger than *n, where m↑ refers to the sum of m copies of ↑.

The proofs of all these results are in exercises 3 and 4. Finally since ↓ = -↑ , we also have the corresponding statements for the “down” game ↓.

- For any n > 0, we have 0 > ↓ > -1/2
^{n}. - On the other hand, ↓ is confused with *.
- But ↓ is smaller than *2, *3, *4, … .
- Finally, for each
*m*> 1 and*n*≥ 0,*m*↓ is smaller than **n*.

### Exercises

- Find games
*A*,*A’*,*B*, such that*A*<*A’*and {*A*|*B*} = {*A’*|*B*}. - We already know that 0 < ↑ < 1/2
^{n}for any positive*n*. Use this to prove that for any positive integer*m*and integer*n*≥ 0, we have*m*↑ + **n*< 1/2^{n}. - Prove that if
*n*= 1, then ↑ + **n*is a first-player win, and that if*n*> 1, then ↑ + **n*is positive. - Prove that ↑ + ↑ + *
*n*is positive for any*n*≥ 0. Hence, prove that for any*m*> 1, and non-negative integer*n*, the game*m*↑ + **n*is positive. - Compare the following: is the first expression greater than / less than / confused with / equal to the second expression?
- -1 + 3↑ and -5/4 + 100↑
- -2 + 100↓ + *2 and -1
- -1 + ↑ and -1 + *
- 2 + ↑ and 2 + ↓ + *
- 2 + ↓ + (*7) and 2 + ↑ + (*8)
- -1/2 + 10↑ + (*3) and -1/2 + 11↑ + (*2)
- -1/2 + 10↑ + (*8) and -1/2 + 11↑ + (*7)

- State a general method of determining whether a + b↑ + (*c) is positive, negative, fuzzy or zero.
- Decide the status of the following Toads-and-Frogs game. For each player, find his best move if he were to go first.