You may also like

problem icon

Nim

Start with any number of counters in any number of piles. 2 players take it in turns to remove any number of counters from a single pile. The loser is the player who takes the last counter.

problem icon

FEMTO

A new card game for two players.

problem icon

FEMTO: Follow Up

Follow-up to the February Game Rules of FEMTO.

Got a Strategy for Last Biscuit?

Stage: 3 and 4 Challenge Level: Challenge Level:3 Challenge Level:3 Challenge Level:3

We received the most complete solution from Neil Poole :

Stuff I've worked out:

At the end of your turn, you must not leave:
1a) either 1, 2, 3, 4 or 5 biscuits in either stack
1b) 6 in one stack if there is 11 or more in the other
1c) 7 in one stack if there is 5 or more in the other
1d) 8 in one stack if there is 14 or more in the other
1e) 10 in one stack if there is 7 or more in the other
1f) 13 in one stack if there is 9 or more in the other

2) stacks with consecutive numbers of biscuits (eg. 4 in one and 5 in the other) OR stacks with the same number of biccies in each

3a) stacks with 2 difference from 4 in one, 6 in the other upwards.
3b) stacks with 3 difference from 5 in one, 8 in the other upwards.
3c) stacks with 4 difference from 7 in one, 11 in the other upwards
3d) stacks with 5 difference from 9 in one, 14 in the other upwards

All the above are true except if you leave "winning combos" (see below).

Winning combos (if you make them):

4) 1 in one stack, 2 in the other
5) 3 in one stack, 5 in the other (then opponent must leave either 1), 2) or 3))
6) 4 in one stack, 7 in the other
7) 6 in one stack, 10 in the other
8) 8 in one stack, 13 in the other

If the opponent does 1), 2) or 3) then you will be able to make 4), 5), 6), 7) or 8).

Keep doing winning combinations until you can take the last biccy(-ies)!!!!!!!

Other winning combos include 9 & 15, 11 & 18, 12 & 20, etc.
 

There are an infinite amount of winning combinations.

To find one, find the lowest whole positive number that hasn't been used yet (that is one of the numbers of the winning combo) and add it to the lowest positive whole difference between the two nos in the combos not yet used to find the other number in the combo.
For example: The lowest integer not yet used in any of our combos is 14, as 13 has been used in 8 & 13, 12 has been used in 12 & 20, etc.
The difference between 11 & 18 is 7.
The difference between 12 & 20 is 8.
9 isn't the difference in any of our combos so far so we add 9 to 14 to get 23.

So our new winning combo is 14 & 23.

Combos with the same difference as lower winning combos are "losing combos".
Any number in a winning combo with a number higher than its pair (eg. 14 & 27 coz 27 is higher than 23) is a losing combo.

There's probably an easier way to work all that out!!!!!!!!!

More findings out:

I think it's only ever possible to make one winning combo (if you can).
I think that if you start, and the starting amount of biccies isn't a winning combo, then you will be able to make a winning combo.
If the starting amount of biccies is a winning combo and you start, against the "expert computer" you've lost.
If the expert computer starts, and the starting combo is a winning combo, you've won (if you're good enough).
If the expert computer starts, and the starting combo isn't a winning combo, you've lost.
If the computer hasn't just, and it isn't the first go of the game, you can always make a winning combo, and vice-versa.
 

This is great Neil. Many thanks for such a full solution.

Mike from the NRICH team has also been working on this problem and has added:

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.

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://www.numericana.com/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!