Description
Last Biscuit is a game that challenges you to use a systematic
approach to deduce a winning strategy. Can you find a strategy
that will beat the computer?
Solution:
You can beat your opponent if you leave the following number of
biscuits: 1, 2 3, 5 4, 7 6, 10 8, 13 9, 15 11, 18 12, 20 14, 23
16, 26 17, 28 19, 31 21, 34 22, 36 24, 39 25, 41 27, 44 29, 47
30, 49 32, 52 33, 54 35, 57 37, 60 38, 62 40, 65 42, 68 43, 70
45, 73 46, 75 48, 78 50, 81
I'm now convinced there's some interesting maths in this. It
looked like w1(i) and w2(i) [the biscuits lefts in the ith
winning position] were approximately linearly related to i, so I
charted them in Excel and read off the regression line: Using a
few 10s of results this gave: w1(i) is approximately 2.618i -
0.5026 w2(i) is approximately 1.618i - 0.5026 Interesting, since
1.618 is very close to the golden ratio phi, and 2.618 is (phi+1)
or phi^2. That -0.5026 looks like it's caused by rounding down to
an integer value. So, with phi = (\sqrt(5)+1)/2, I tried for 0
< = i < = 10000: w1(i) = floor(phi*i) w2(i) =
floor((phi+1)*i) Perfect match on all pairs! If phi is involved
there must be some Fibonacci sequences around. In fact there are
lots of them. The winning pairs are the even pairs of consecutive
numbers in a union of Fibonacci sequences. If F(1,2) is the
Fibonacci sequence that starts 1,2,3,5,8... and F(1,3) starts
1,3,4,7,11,.... you can use F(1,3) to fill in the gaps left by
F(1,2). F(2,4) fills in the gaps left by the previous 2, and so
on. This all makes a certain amount of sense since the ratio of
successive Fibonacci numbers is phi - and that was the gradient
of the regression line. It's still all just conjecture though - I
haven't been able to prove any of it so far. Assuming it's all
true, it's possible to write a slick algorithm that works for
very large numbers of biscuits - essentially by using the inverse
linear relationship to find the nearest winning pairs that can be
reached from any position. Unfortunately, the calculation is
still a bit much to do in one's head - but it avoids the need to
tabulate all pairs up to the one that works. I tried that and so
far as I can tell it works fine. An Excel spreadsheet so you can
see what I mean is saved in common > site content. See
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibrab.html#PhiPlot
This page is all relevant to the winning pairs in Last Biscuit.
It's talking about the same function I needed to calculate them -
floor(i*phi) - defining this as the spectrum of phi. There's an
interesting section on how the spectra of 2 numbers A and B can
partition the integers into 2 sets iff 1/A + 1/B = 1. The smaller
and larger numbers of the winning pairs form such a partition
with A = phi and B = phi^2. 1/phi + 1/phi^2 = 1 since phi + 1 =
phi^2. http://home.att.net/~numericana/answer/games.htm goes into
some detail linking this version other nim like games and the
grundy numbers. After that background, the following paper might
be more understandable
http://www.math.temple.edu/~xysun/wythoff/wythoff_2.pdf I think
it contains a proof that last biscuit winning pairs are a wythoff
sequence - but it ain't easy!
You can beat your opponent if you leave the following number of
biscuits:
1, 2
3, 5
4, 7
6, 10
8, 13
9, 15
11, 18
12, 20
14, 23
16, 26
17, 28
19, 31
21, 34
22, 36
24, 39
25, 41
27, 44
29, 47
30, 49
32, 52
33, 54
35, 57
37, 60
38, 62
40, 65
42, 68
43, 70
45, 73
46, 75
48, 78
50, 81
A strategy to find winning moves is to note that (0,0) is a winning pair and
then find the complete set of winning pairs by induction.
If (An,Bn),An £ Bn is the last move discovered, then An+1 is
the minimum positive integer that does not appear in a winning pair yet, and
Bn+1 = An+1 + 1 + (Bn - An).
(An+1,Bn+1) must be a new winning move because it is impossible to
generate a lower winning move from it in one turn. Neither An+1 nor
Bn+1 appear in a lower pair,so taking from a single stack fails. Also,
no lower winning pair has a difference of An+1-Bn+1,so taking from
both stacks will fail.
Plotting An against n and Bn against n reveals near linear
relationships, which turn out to be represented exactly by the equations:-
An
=
floor(nf)
Bn
=
floor(nf2)
where the floor function rounds values to the next lowest integer, and f is
the golden section. A good way to discover these relationships is to plot them in
Excel and infer them from the regression line equations. For a proof, see
ref [10] in this paper by Xinyu Sun
Even when you know the winning pairs, it is not trivial to calculate the next
best move from a given starting position, since the above formulae must be
inverted (the floor function complicates matters) and applied with some care.
The winning move from a (500,1000) start will take you to (500, 309).