5
$\begingroup$

Alice and Bob play the following game that starts with $N\ge3$ green marbles on the table.

  • Alice and Bob move alternatingly.
  • Alice makes the first move. In this first move, Alice removes $x$ green marbles from the table; the number $x$ is chosen by Alice so that it satisfies $1\le x\le N-1$.
  • In every further move, the active player removes $y$ marbles from the table. The number $y$ is chosen by the active player to satisfy $1\le y\le2z$, where $z$ denotes the number of marbles that have been removed in the preceding move of the other player.
  • The player who takes the last marble wins the game.

Question: Which player is going to win this game (in dependence on $N$)?

(As usual, we assume that Alice and Bob both use optimal strategies.)

$\endgroup$
5
$\begingroup$

My answer offers no proof, only truth.

This puzzle is related to the base Fibonacci representation of numbers. In base b, the nth digit represents $b^{n-1}$. In base Fibonacci, the nth digit represents the Fibonacci number $F_{n+1}$. For example, $101101_F$ represents $F_{6+1}+F_{4+1}+F_{3+1}+F_{1+1}=13+5+3+1=22$.

A number can have several equivalent base-Fib representations. For example, $3=100_F=11_F$. However, every number has a unique representation which doesn't have any adjacent ones. When we wrote $22=101101_F$, this had two adjacent ones in the middle, but we can equivalently write $22=1000001_F$ without any adjacent ones.

With this new base system under our belts, we can now solve the puzzle:

If a player is faced with a heap of $N$ marbles, their winning strategy is to remove $F_m$ marbles, where $F_m$ is the Fibonacci number corresponding to the least significant nonzero digit of $N$'s base-Fib representation. If the player cannot remove this much, they lose.

For example, if a player is faced with a heap of $81 = 101001000_F$ marbles, they should remove $5$ marbles, since the fourth digit is the least significant nonzero digit, which corresponds to the Fibonacci number $F_{4+1}=5$.

This mean that Bob can win if and only if the initial position is a Fibonacci number, because in this case the base-Fib representation of $N$ is $1000...000_F$, and the only way to follow the required strategy would be to remove the entire heap.

$\endgroup$
7
$\begingroup$

Alice wins when N is not a Fibonacci number. Bob wins when N is a Fibonacci number

Let losses be on $F(x). F(1) = 3; F(2) = 5, F(x) = F(x-1) + F(x-2)$

Suppose there are k marbles, and that all previous marbles N < k this Fibonacci formula decides correctly.

The person to reduce the marbles to a Fibonacci number wins, as long as they remove less than half of that number to do so. If they cannot, then they treat the game as if the Fibonacci number is instead 0, ie. if $k = 17$, the greatest Fibonacci number less than that is $F(x) = 13$, so they play like the game where $N = k - F(x) = 17-13 = 4$.

We know that this will always win in the case of non Fibonacci numbers, by induction. In the case where the second number is also Fibonacci (ie if $N=18-13 = 5$), the first player can "win" that game by just removing all 5. This is allowable until the second Fibonacci number is more than half of the nearest Fibonacci number less than $k$.This only happens when the nearest Fibonacci number $< k $ is $F(x)$ and the previous number is $F(x-1)$. Hence, the new place that Alice loses is $k = F(x) + F(x-1)$, which generates the Fibonacci sequence.

$\endgroup$
  • 2
    $\begingroup$ This is very messily written and hard to follow, even if the general idea is correct. $\endgroup$ – Fimpellizieri Mar 24 '16 at 20:14
2
$\begingroup$

I'm not sure this answer works, but I think that

Alice wins if $N$ is not a 'losing number'. (Converse may/ may not be true)

We first determine a list of losing numbers. We draw a table with 2 columns and start with a number 3.

Losing    Previous
3

Now we write the greatest number less than half this number on the right hand side.

Losing    Previous
3         1

Now we add both of them and find the next number to use in the new row. (3+1=4, next number is 5)

Losing    Previous
3         1
5

Now we use the same process repeatedly.

Losing    Previous
3         1
5         2
Losing    Previous
3         1
5         2
8

and so on.....

Losing    Previous
3         1
5         2
8         3
12        5
18        8
27        13
41        20
62

Now on every turn, Alice will reduce the number of objects to the greatest losing number (ignore the column on the right now). The moment Alice gets an opportunity to win, she should take it (obviously).

However, if the game itself starts with Alice facing a 'losing number', then she cannot use this strategy. I am yet to solve this case.

$\endgroup$
  • 1
    $\begingroup$ In the case of N=5, bob wins. If Alice takes >= 2, bob can take the rest. If alice takes 1, bob takes 1, ending up in the N=3 case. $\endgroup$ – Lacklub Mar 24 '16 at 12:33
  • $\begingroup$ And of course if $N=3$ Bob also wins. Bob can always take all marbles on his first turn $\endgroup$ – Ivo Beckers Mar 24 '16 at 12:35
  • $\begingroup$ @IvoBeckers Thanks for noticing. I've edited now. $\endgroup$ – ghosts_in_the_code Mar 24 '16 at 12:39
  • 1
    $\begingroup$ For $N = 12$, (a losing number), I think alice still wins. A takes 1 (11 left). Bob can either take 1 (10): Alice takes 2 (8 - alice wins). Or bob can take 2 (9) and alice takes 1 (8 - alice wins). $\endgroup$ – Lacklub Mar 24 '16 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.