Can you explain the strategy for winning this game with any target?
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.
A new card game for two players.
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.
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.
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.
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!