[Guest]

in a topic written by superprismatic, i posted the partition equation

P(n,a_k) = P(n,a_k-1) +P(n-a_k,a_k)

now a game: you start with some large number of coins selected by player 2. you can split it into 2 groups but one of the two groups must be a fibinochi number > 1 unless a group of 2 occurs. with each split, if a single coin remians in the group, the player who made the split gets to keep the coin. the player with the most coins at the end of the game wins.

for example, if player 2 selected 3 coins for starting, player 1 loses, as he only has one choice, split it into a group of 2 and a group of 1, keep the 1 coin. then player 2 splits the 2 coins into 1 coin and 1 coin, keeping both.

player 2 selected 55 coins. which player wins, assuming both players play optimally?

for which numbers will player 2 win?

[k-man]

By always separating 3 coins from a larger group the player forces another player to split the larger remaining group until the remaining group is less than 3 coins. If both players follow this strategy, player 1 wins for any initial number of coins that can be expressed as 3x or 3x+1 and loses for all 3x+2 (the exceptions are 3 as given in the OP and 4, which results in a tie.)

So, for 55 coins, if both players follow this strategy, player 1 wins by getting 37 coins.

Of course, this may not be the best strategy, but that's just my first stab at the problem.

[k-man]

By always separating 3 coins from a larger group the player forces another player to split the larger remaining group until the remaining group is less than 3 coins. If both players follow this strategy, player 1 wins for any initial number of coins that can be expressed as 3x or 3x+1 and loses for all 3x+2 (the exceptions are 3 as given in the OP and 4, which results in a tie.)

So, for 55 coins, if both players follow this strategy, player 1 wins by getting 37 coins.

Of course, this may not be the best strategy, but that's just my first stab at the problem.

I just came back to think about this problem and read my post again. I clearly didn't think it through. Ignore that post...

[Guest]

i'm thinking the best starting is with listing fibonaccis less than 55...

which is

2

3

5

8

13

21

34

55

[k-man]

So, I gave it some more thought and my initial thoughts were correct, although I rushed and came to incorrect conclusions. Here is my final answer

Player 1 wins if the initial number of coins is EVEN and loses if it's ODD. The only strategy that's important to follow for both players is that if you have a group of even number of coins then you should split it into 2 odd groups (for example, 3 + the rest). First, I will prove that it's impossible to win starting with any odd number of coins...

We know that starting with 3 coins player 1 loses. It's easy to see that the same is true for 5 and 7 coins as well. Suppose that there are some odd starting numbers and a strategy or strategies that lead to a win for player 1. Then there must be the SMALLEST of these numbers. Let's call it X. For all odd numbers less than X there is no winning strategy for player 1. Player 1 starts with X number of coins and must divide X into 2 groups. One of the resulting groups will be even and the other will be odd. If player 2 will use his next move to split the even group into 2 smaller odd groups player 1 cannot win because he now has to play 3 games starting with odd numbers smaller than X. As long as the player 2 always splits the even group into 2 odd groups he's guaranteed a win as eventually there will be nothing left other than groups of 3s and player 1 will have to make his move.

So, from the above, if player 1 starts with an even number of coins he can split it into 2 odd groups giving no chance to player 2 to win.

Additional note:

I don't see the importance of the Fibonacci numbers in the game. It doesn't make a difference that one of the groups must be a Fibonacci number. If this requirement was added to disallow always taking one coin from the group then it's a clever distraction that achieves the goal and introduces some corner cases to think about. The corner cases are when the starting number of coins is 1 greater than a Fibonacci number. This allows player 1 immediately grab one coin from the pot. It doesn't change the end result though, because all of the above is still true and the winning player beats the loser approximately by the ratio of 2 to 1, so 1 extra coin doesn't help if the initial number was odd.

[Guest]

agreed k-man, nicely done!

i often write riddles without knowing the answer, and this was one of the cases.

i hoped that resticting to fibinochi numbers would make the problem more challenging but obviously not.