Our discussion of numbers is not quite over. We have already seen that
there are games of integer values, and fractional values of the form 2-n. From these skeletal values, we may easily obtain games of any arbitrary
value of the form m / 2p, where p is a non-negative
integer. For instance, the games below are of values 3/4, 11/16 and -5/8 respectively.
A Simple Claim
Instead of expressing each fraction as a sum, we shall prove the
following claim, hence providing us a compact way of expressing
fractions:
If p is an integer and m is a non-negative integer,
then {
p
2m
|
p+1 2m
} =
2p+1
2m+1
The proof is easy: by definition { 0 |
2-m } =
2-m-1. Thus, we may expand the right hand term
as a sum of (2p+1) terms, each of which is {
0 | 2-m
}. The player Left has no choice but
to leave 0 in one of the summands, leaving 2p
(2-m-1) = p / 2m. Same
goes for Right: he has to leave behind 2p
(2-m-1) + (2-m) =
(p+1) / 2m. This completes our proof.
Simplifying { a |
b }
It is always easy to simplify the game G = {
a | b
}, where a < b are numbers. However, in
general it is incorrect to simply take the average {
a | b } =
(a+b)/2. For instance, consider the game
G = {-19 |
+2}. If Left starts, he is forced to leave a negative
number for Right to win. Similarly, if Right starts, Left wins. Hence,
the 2nd player wins regardless of who starts, and the
game is a zero game (i.e. {-19 | +2} = 0)!
As another example, we shall show {1/4 |
1} + (-1/2) = 0. Expanding
the sum gives us {1/4 |
1} + {-1 |
0}. Suppose player Left starts. If
he takes 1/4 in the first summand, he'll leave 1/4 - 1/2 = -1/2 < 0
and lose. On the other hand, if he takes -1 in the second summand,
Right can respond by taking 1 in the first summand, thereby leaving
-1 + 1 = 0 (hence Right wins). Now suppose Right starts. If he takes
1 in the first summand, he'll leave 1 + (-1/2) = 1/2 > 0 and lose.
If he takes 0 in the second summand, Left responds by taking 1/4,
leaving 1/4 + 0 = 1/4 and wins. Hence, {1/4 | 1}
= 1/2.
Generally, we have the Simplicity Rule.
The game G = { x |
y}, where x < y,
is the simplest number which lies strictly between x and
y. In other words, G = z, where z is a
number strictly between x and y such that no option of
z lies within this range.
For example, to simplify { 3/4 |
5/2 }, note that the number 1
lies strictly between 3/4 and 5/2. Also, 1 = { 0
| }, and no option of 1 lies within this range. Hence {
3/4 | 5/2 } = 1.
As another example, consider {-5 |
1}. Since 0 lies between -5
and 1, and 0 has no options at all, we must have 0 = {-5
| 1}.
The following numbers are arranged according to increasing
order of simplicity:
Among non-integer values, a number r is simpler
than s if r has a smaller denominator than s.
Among non-zero integer values, a simpler integer is one
which is closer to 0.
Zero (0).
Proof for Simplicity Rule
We shall first prove the existence of such a number. This
is quite easy. Suppose z' is any number between x
and y. If no options of z' lie within this range,
we are done. Otherwise, pick any option of z within it
and continue the analysis, replacing z with this option.
Since the game is finite, this process must eventually end and
we then have a game z with our desired properties.
Next we need to show that {x | y} + (-z)
is a win for the 2nd player. Suppose Left starts.
If he chooses from the first summand, the resultant sum would
be x - z < 0 (i.e. a win for Right). If he chooses
from -z, the resultant value -z' must satisfy
z' > y since it does not lie strictly between x
and y. Now Right responds with a move in the
first summand, giving y - z' < 0 (Right wins).
Similar reasoning holds when Right starts.
This completes the proof (we do not even need to show uniqueness
of the value z).
Simple Examples
You may now use the simplicity rule to
verify / evaluate the values of the following Hackenbush games:
Cutting the Cake
Given a nice almond cake, which is divided into m-by-n
unit squares, players Left and Right alternately take cuts. Each cut must
divide a piece of cake into two. Player Left may only take horizontal cuts,
while player Right can only take vertical cuts. A typical game for a 2-by-3
rectangle might proceed as follows (in which case Right wins).
It is clear that a 1-by-n rectangle has a value of +(n-1) (since
Left has n-1 free moves, while Right has none). Similarly, an n-by-1
rectangle has a value of -(n-1). It is easy to see that for the cases 2-by-2,
2-by-3, 3-by-2 or 3-by-3, the second player wins, so that the game is a zero game.
What about 2-by-4? If Right starts, he leaves two 1-by-4 rectangles which are worth
(-3) + (-3) = -6. If Left starts, he may leave either two 2-by-2 rectangles or a
2-by-1 and a 2-by-3 rectangle. The former case is worth 0, while the latter case
is worth (-1) + 0 = -1. Hence, the game may be written as {-1,0 | 6} = {0 | 6}.
By the Simplicity Rule, this is equal to +1.
Exercise : Find the values for rectangles of other sizes.
Back to the main page...