Hello maths fans! I am Dr. Tom Crawford from Tom Rocks Maths, and the University of Oxford.
And I am here to introduce this fantastic video from Trevor on the same topic as the
essay he submitted to the Teddy Rocks Maths Essay Competition. The competition is open
to anyone. All you have to do to enter is to write about your favorite mathematical
topic for a non-specialist audience. It will be running again in early 2021, so keep a
look out for any announcements, and in the meantime, enjoy Trevor's brilliant video.
Suppose there are two piles of arbitrary numbers of stones, and you are playing against an
opponent. You and your opponent can count the numbers of stones in each pile beforehand
to determine the winning strategy. You and your opponent take turns to remove some stones
from the piles, but you can only remove any number of stones from one pile, or remove
the same number of stones from both piles. You cannot skip your turn. The game continues
until no more stones left in both piles. There are two ways of determining who wins the game.
Method A: the person removing the last stone wins; method B: the person removing the last
stone loses. These are the two opposite games we will be talking about.
What would be the winning strategy in either method? Are the winning strategies for method
A different from method B? Does the strategy change depending on whether you are the first
one to play the game? Or should you “kindly invite” your opponent to play the game first?
If so, does that depend on the numbers of stones in either pile? We are going to answer
all these question, but I encourage you to pause the video and think of the answers first.
Let’s start small, and suppose that one pile has one stone, and the other has two.
If the game is run according to method A, then whoever goes first loses. Why? Whoever
goes first have four possible choices of moves, and whoever goes next could take the remaining
stones, because these are all allowed moves. So basically you want the remaining stones
to be left to you, which means you want to leave all these to your opponent, because
whatever your opponent does, you can take the remaining stones and win. So your goal
is to remove the stones so that it reaches this configuration. Then no matter what your
opponent does, you will win. For simplicity, we call this the (1,2) configuration, and
we call this a winning pair, because if you can make it to this configuration, then you
are guaranteed to win. But are there any other winning pairs? Also, this is only for method
A, and we would expect to have different winning pairs for the other method.
We will focus on Method A for now. The winning pairs will form a table, and to allow better
navigation for the table, we will index the winning pairs, starting from 0, for reasons
explained later. For each winning pair, we denote A_n to be the smaller number in the
pair, and B_n to be the larger number. It might seem redundant, but we will include
(0,0) as a winning pair, again for reasons explained later. This comes directly from
the method of determining who wins the game. If you can reach the (0,0) configuration in
your turn, you just won the game! For the first column, we will put (1,2) because we
have just shown that this is a winning pair.
From the rules of the game, we can infer some rules that this winning table needs to follow.
Firstly, there should be no repeats in different winning pairs. This means something like this,
or this, or this cannot happen. Let’s say these two are really winning pairs, then your
opponent can reach from one winning pair to another, making him/her win instead. So at
least one of them cannot be a winning pair. The second rule is the difference between
A_n and B_n should not repeat. This means something like these two pairs cannot happen.
Why? Again, your opponent can easily reach from one winning pair to another, making him/her
win instead. A subtle note is that rule number one says different winning pairs, so if the
repeat is in the same winning pair, like the 0th one, it is fine. But because of rule number
2, this can only occur in one winning pair. This means all natural numbers appear at most
once on this table, except for 0, if you count 0 as a natural number. The best-case scenario
is that every natural appears exactly once on the table so that more winning pairs are
available, and that all the differences appear exactly once. We can’t guarantee this happening
yet, but this is the hope.
So according to these rules, we construct a winning table. The number 3 hasn’t appeared
yet, and it has to be the smallest of what comes after, so we put it as A_2. A difference
of 2 hasn’t appeared yet, so we put a 5 here, so that the difference of 2 appears.
Then, the number 4 hasn’t appeared on the table yet, so we put it as A_3. And again,
a difference of 3 hasn’t appeared yet, so we put a 7 here, so that the difference of
3 appears. Applying this kind of reasoning over and over, we can construct the entire
winning table. But are these really winning pairs? Can we really be guaranteed to win
if, say, we remove the stones to this (8,13) configuration?
I won’t show the entire proof here, but the approach is that no matter what the opponents
do, you can always reach one of the previous winning pairs, including the 0th one to directly
win. So what can your opponents do after you attain this (8,13) configuration? Well, he/she
can remove stones only from the pile with 8 stones, only from the pile with 13 stones,
or remove the same number of stones from both piles. And the gist of the proof is to show
what you can do in each of the three cases. This proof is not really the focus of the
video, but feel free to treat this as a little exercise and leave a comment for the proof.
Now what about method B, where the person removing the last stone loses. An obvious
winning pair would be (0,1), because you will force the opponent to remove the last stone.
The next winning pair would be (2,2). Why is (2,2) a winning pair? Let’s suppose after
your turn, you leave (2,2) configuration to your opponent, then your opponent has these
6 possible moves, including the option to remove all stones. In all moves, you can always
either leave one stone behind for your opponents to lose, or directly win if your opponent
has removed all stones already. So back to the winning table for method B. Again, we
can use the rules below to deduce the rest of the winning table, and here we go.
These all look pretty suspicious. Why?
Compare the two winning tables from the different methods. Apart from the first two columns,
all the other winning pairs are the same for both games. The fascinating thing is that
they are supposed to be two opposite games! Yet they have largely the same winning pairs.
The fascination does not end there. What about the golden ratio in the title? Let’s revisit
the winning table again. The first row A_n is the integer part of n times phi, the golden
ratio, and the second row B_n is the integer part of n times phi^2. For example, according
to this formula, A_4 is the integer part of 4 times the golden ratio, which is really
6. And B_5 is the integer part of 5 times golden ratio squared, which is really 13.
But how and why is golden ratio involved?
First off, we need to revisit what the golden ratio is. It is the positive root of this
quadratic equation, so everything that you see here eventually relates to this quadratic
equation. Specifically, we want to see why these formulas for A_n and B_n fulfil these
rules. We first explain why all the differences appear exactly once. We consider the difference,
and using the formulas for A_n and B_n, we get this expression. Based on the defining
property of the golden ratio, we can replace phi^2 by 1+phi, which can be further manipulated
to be just n. So if we have different n’s, the differences in the same winning pair would
be different. So we have explained why all the differences would appear exactly once.
What about the other rule that every natural number, except for 0, appears exactly once?
We will prove they appear at most once first, then prove they appear at least once. Combining
these two will give the exactly once rule above. We go for the at most once part first.
We first need to rewrite this quadratic. So let’s suppose there is a natural
number p appearing twice on the winning table, which means it is A_m for some m and B_n for
some n. By definition of the integer part, we have m times phi and n time phi^2 to be
between p and p+1. We use the strict inequality sign here because phi and phi^2 are irrational,
so a multiple of it would not be an integer. Dividing the first inequality by phi, and
the second inequality by phi^2, then by adding these up, we get this kind of monstrous inequality.
Because of the rewritten quadratic equation, these brackets all sum up to 1, but then m+n
is an integer, so it cannot be between two consecutive integers p and p+1, which is a
contradiction. This means the original assumption that p can appear twice in the winning table
is not true.
What about the “at least once” part? Suppose a number p cannot be generated by A_n or B_n,
then on this number line, p sits between two consecutive A_m’s. So we have these two
inequalities about p. By changing up the number line a little bit, we can similarly write
down two inequalities. Then what we will do is very similar to what we did before, which
is to divide the inequalities by phi and phi^2. Adding this pair of inequalities, we have
this blue inequality, If we instead add another pair of inequalities, we will have this inequality
instead. Again, because of the rewritten quadratic at the top, these two brackets are both 1.
We can further subtract 1 from both sides of the inequality on the right to get this.
By simply combining the two inequalities, we have p to be trapped between two consecutive
integers, which is again impossible. So the original assumption that p cannot be generated
by A_n or B_n is wrong, which means all integers must appear in the winning table.
So we have explained why the golden ratio, seemingly unrelated to the discrete nature
of the game, is actually related to the game. This was very fascinating to me when I first
knew this, so leave a comment if you are also surprised by the connection with the golden
ratio.
If you enjoyed this video, give it a thumbs up and share it! Don’t forget to subscribe
with notifications on for more of these math videos. See you next time!