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 re: Doubling case Solved by Jer)

Fibonacci numbers:

 2 
 3 
 5 
 8 
 13 
 21 
 34 
 55 
 89 
 144 
 233 
 377 
 610 
 987 
 1597 
 2584 
 4181 
 6765 
 10946 
 17711 
 28657 
 46368 
 75025 
 121393 
 196418 
 317811 
 514229 
 832040 
 1346269 
 2178309 
 3524578 
 5702887 
 9227465 
 14930352 
 24157817 
 39088169 
 63245986 
 102334155 
 165580141 
 267914296 
 433494437 
 701408733 
 1134903170 
 1836311903 
 2971215073 
 4807526976 
 7778742049 
 12586269025 
 20365011074 
 32951280099 
 53316291173 
 86267571272 
 139583862445 
 225851433717 
 365435296162 
 591286729879 
 956722026041 
 1548008755920 
 2504730781961 
 4052739537881 
 6557470319842 
 10610209857723 
 17167680177565 
 27777890035288 
 44945570212853 
 72723460248141 
 117669030460994 
 190392490709135 
 308061521170129 
 498454011879264 
 806515533049393 
 1304969544928657 
 2111485077978050 
 3416454622906707 
 5527939700884757 
 8944394323791464 
 14472334024676221 
 23416728348467685 
 37889062373143906 
 61305790721611591 
 99194853094755497 
 160500643816367088 
 259695496911122585 
 420196140727489673 
 679891637638612258 
 1100087778366101931 
 1779979416004714189 
 2880067194370816120 
 4660046610375530309 
 7540113804746346429 
 12200160415121876738 
 19740274219868223167 
 31940434634990099905 
 51680708854858323072 
 83621143489848422977 
 135301852344706746049 
 218922995834555169026 
 354224848179261915075 
 573147844013817084101 
 927372692193078999176 

So 43546758443209876 is not Fibonacci.  The next lower number that is Fibonacci is 37889062373143906.

Posted by Charlie on 2004-05-11 09:18:34