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

(A_{n}, B_{n}), A_{n} \leq B_{n}

is the last move discovered, then

A_{n + 1}

is the minimum positive integer that does not appear in a winning pair yet, and

B_{n + 1} = A_{n + 1} + 1 + (B_{n} - A_{n})

$(A_{n + 1}, B_{n + 1})$ must be a new winning move because it is impossible to generate a lower winning move from it in one turn. Neither $A_{n + 1}$ nor $B_{n + 1}$ appear in a lower pair,so taking from a single stack fails. Also, no lower winning pair has a difference of $A_{n + 1} - B_{n + 1}$ ,so taking from both stacks will fail.

Plotting $A_{n}$ against $n$ and $B_{n}$ against $n$ reveals near linear relationships, which turn out to be represented exactly by the equations:-

$\begin{matrix} A_{n} & = & floor (n ϕ) \\ B_{n} & = & floor (n ϕ^{2}) \end{matrix}$

where the floor function rounds values to the next lowest integer, and $ϕ$ 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).