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?
(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.