Strategy Game - Similar to Nim
Source: Posted at "Post a Question"
Problem:
Two players compete in the following game: There is a pile containing n chips; the first player removes any number of chips except that he cannot take the whole pile. From then on, the players alternate moves, each person removing one or more chips but not more than twice as many chips as the preceding player has taken. The player who removes the last chip wins. (For example, suppose that n = 11; player A removes 3 chips; player B may remove up to 6 chips, and he takes 1. There remain 7 chips; player A may take 1 or 2 chips, and he takes 2; player B may remove up to 4, and he picks up 1. There remain 4 chips; player A now takes 1; player B must take at least one chip and player A wins in the his next chance.
What is the best move for the first player to ensure his win if possible if there are initially n chips?
Problem:
Two players compete in the following game: There is a pile containing n chips; the first player removes any number of chips except that he cannot take the whole pile. From then on, the players alternate moves, each person removing one or more chips but not more than twice as many chips as the preceding player has taken. The player who removes the last chip wins. (For example, suppose that n = 11; player A removes 3 chips; player B may remove up to 6 chips, and he takes 1. There remain 7 chips; player A may take 1 or 2 chips, and he takes 2; player B may remove up to 4, and he picks up 1. There remain 4 chips; player A now takes 1; player B must take at least one chip and player A wins in the his next chance.
What is the best move for the first player to ensure his win if possible if there are initially n chips?
Solution:
Highlight the part between the * symbols for the answer.
* This is Fibonacci Nim (Whinihan, 1963). The first player loses if and only if n is a Fibonacci number (sequence 1, 2, 3, 5, 8, 13, ...).
Winning move when n is not Fibonacci: write n as a sum of non-consecutive Fibonacci numbers (Zeckendorf representation, e.g. 12 = 8 + 3 + 1) and remove the SMALLEST Fibonacci in that sum.
Why it works: two facts about the Zeckendorf form do everything. (1) Non-consecutive Fibonacci numbers satisfy F > 2 * (sum of all smaller non-consecutive Fibonacci numbers below it is less than F/2...) precisely: the smallest term z_1 and the next term z_2 satisfy z_2 > 2 z_1, so after you take z_1 the opponent may take at most 2 z_1 < z_2 and cannot take the next Fibonacci term of your representation. (2) If n is itself Fibonacci, any legal first move takes k < n chips with k <= 2(n - k) failing exactly when needed: whatever you take, the opponent can apply the same rule to the remainder, which is no longer Fibonacci. Induction on n then shows Fibonacci heaps are exactly the P-positions and "take the smallest Zeckendorf term" always wins otherwise.
Example: n = 11 = 8 + 3, take 3; whatever B does with the 8-pile (max take 6), you keep replying with the smallest Zeckendorf term of the current heap and take the last chip.
Solution by Pritish (and independently Santosh Ananthakrishnan) from the comments; verified computationally: P-positions up to 89 are exactly 2, 3, 5, 8, 13, 21, 34, 55, 89. *
(obtained via discussion with Yashoteja)
ReplyDeleteThis solution is fairly involved, and requires an ingenious induction hypothesis. A more elementary solution would be interesting!
Claim. The first player looses if and only if 'n' is a Fibonacci number
[I'm referring to the standard Fibonacci sequence : 1 2 3 5 8 13 ...]
Proof.
If there are 'm' chips left, we define,
g(m) = minimum number of chips needed to be removed by the current player to win.
Thus, an initial condition of 'n' chips is winning if and only if g(n) < n.
There is an easy recurrence for g :
g(m) = argmin(i) : [g(m-i) > 2i]
If no such i exists, then g(m) = m.
Listing down a few values of g,
g(1) = 1
g(2) = 2
g(3) = 3
g(4) = 1
g(5) = 5
g(6) = 1
g(7) = 2
g(8) = 8
g(9) = 1
g(10) = 2
......
This motivates us to make the following sub-claim,
Sub-claim. Define f(m) = largest Fibonacci number less than or equal to m.
If f(m) = m, then g(m) = m
Else, g(m) = g(m-f(m))
This sub-claim can be easily proved by induction, but I'm too lazy to write the details!
Now, note that if f(m) ≠ m, then g(m) = g(m-f(m)) <= m - f(m) < m. Thus, the only numbers 'm' for which g(m) = m, are Fibonacci numbers!
g(m) also gives you a winning strategy. That is, whenever there are 'm' chips left, just take out g(m) many chips from the pile.
--------------------------
It would be interesting to see if one can come up with a neat expression for g(m) instead of a recursive one here.
proof by induction:
Deletenotations P1 => player 1 , P2 => player2 , F(k) => k'th fibonacci number
I.H. : let for all m<n , P1 loses if m is a fibonacci else P1 wins.
Base cases: n=1,4,5 P1 wins n=2,3 P1 loses
Induction Step:
for n. let F(k) < n is the nearest fibonacci to n.
let r = n-F(k).
in order for P1 to win he has to "Eat" these r chips and leave the "turn" on P2. This means he has to win a game where there were only r chips at the start. ( think for a while what i am trying to say here. )
now if n = F(k+1) then r = F(k-1), so by I.H he can't win the "sub-game" where there were only r chips.
but if n =/= F(k+1) then r=/= F(k-1), so he can win this sub-game.
Hence Proved.
correct base cases.. 1,4 P1 wins 2,3,5 Loses
DeletePardon my wrong usage of notation.
ReplyDeleteBy g(m) = argmin(i) : [g(m-i) > 2i], I meant,
g(m) = smallest i such that [g(m-i) > 2i].
Trying a few values makes the Fibonacci sequence seem like a good guess. By induction, assume that A loses for all Fibonacci numbers less than n, and wins for others. Now for n+1, if n+1 is not a Fibonacci number, A takes away the difference between n+1 and the highest F(k) < n+1, and by the induction hypothesis, A wins. If n+1 is a Fibonacci number, he can only win by leaving another Fibonacci number. The nearest one is always more than one-thirds of n+1 away (easy to show) for n>=2, letting B wipe everything out - so A cannot win.
ReplyDeleteu forgot that fact that player 1 is not in a hurry to leave fibonacci number of chips to player 2 in a single move !
DeleteHe may take a greedy strategy i.e, ensuring that other person does not win the game in next trial after his trial. He must choose less that n/3 of the remaining chips so that game does not end at next trial.
ReplyDeleteLittle correction
ReplyDeleteproof by induction:
notations P1 => player 1 , P2 => player2 , F(k) => k'th fibonacci number
I.H. : let for all m<n , P1 loses if m is a fibonacci else P1 wins.
Base cases: n=1,4,5 P1 wins n=2,3 P1 loses
Induction Step:
for n. let F(k) < n is the nearest fibonacci to n.
let r = n-F(k).
in order for P1 to win he has to "Eat" these r chips and leave the "turn" on P2. This means he has to win a game where there were only r chips at the start. ( think for a while what i am trying to say here. )
now if n = F(k+1) then r = F(k-1), so by I.H he can't win the "sub-game" where there were only r chips.
but if n != F(k+1) then r != F(k-1), so he can win this sub-game. By winning i mean Player 1 has to forget about original game and just replace original game with this sub-game. This will make sure he wont eat more than r/2 chips at any point of time, thus when this r chips game ends, P2 can't eat more than r chips.
Hence Proved.
Correct claim - this is Fibonacci Nim (Whinihan, 1963). Your g(m) formulation ("smallest winning take") is the right object: the
ReplyDeleteThe non-Fibonacci case needs one more step: after A removes the difference r = (n+1) - F(k), B faces F(k) chips but ma
ReplyDelete"Play so the opponent cannot finish next move" is necessary but not sufficient - the constraint compounds over many mo
ReplyDeleteTrue - P1 may reach a Fibonacci-sized pile over several moves, and the single-move argument does not rule that out. Wha
ReplyDeleteThe sub-game recursion is the right instinct, and your base-case corrections (2,3,5 lose; 1,4 win) are right. The subt
ReplyDelete