Bologna Sandwich was worried about an upcoming test in Discrete Mathematics and was finding it hard to get to sleep. Bologna awoke early in the morning, aroused by devilish laughter, only to see an impish looking homunculus sitting at the bottom of the bed next to a seemingly infinite pile of chips. Hello, Bologna, it said, would you like to play a little game? This pile contains 43546758443209876 chips and the bottom chip represents your immortal soul. The rules are quite simple. The first player removes some chips, but not all of them. After that we take turns removing some chips.

The only rule now is that a player cannot remove more than the previous player removed in his last turn. The winner is the player who takes the last chip. If I win I get to keep your soul and if you win, you get an A in the test. Would you like to go first or second? This seemed a reasonable bet to Bologna.

Can you give Bologna a strategy for playing no matter how many chips there are? (What if there were just one more chip in the initial pile?)

What if the rule were that one is allowed to take up to twice the number of chips the previous player took?

(In reply to Doubling case started. by Jer)

It turns out it is Fibonacci. My previous post had errors which I decided not to change.

If you leave your opponent with a Fibonacci number of chips he will lose. Instead of trying to explain, I'll just show the recursive structure.

W is a win, the number(s) following it are the move(s) you must make if faced with the given number of chips.
L is a lose, you will always lose if faced with this number of chips.

2L
3L
4W1
5L
6W1
7W2
8L
9W1
10W2
11W3
12W1 (opponent cannot win because he cannot take 3)
13L
14W1
15W2
16W3
17W4,1
18W5
19W1
20W2
21L
22W1
23W2
24W3
25W4,1
26W5
27W6,1
28W7,2
29W8
30W9,1
31W10,2
32W3
33W4
34L
35W1
36W2
37W3
38W4,1
39W5
40W6,1
41W7,2
42W8
43W9,1
44W10,2
45W11,3
46W12,1
47W13
48W14,1
49W15,2
50W16,3
51W4,1
52W5
53W1
54W2
55L
This pattern continues, so I'll skip to
76W21
77W22,1
78W23,2
79W24,3
80W25,4,1
81W26,5
82W27,6,1
83W7,2
84W8
85W9,1
86W10,2
87W3
88W1
89L

Is 43546758443209876 Fibonacci?

-Jer

Posted by Jer on 2004-05-10 22:13:28