Removing green marbles from the table

Question

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.)

Answer 1

My answer offers no proof, only truth.

This puzzle is related to the base Fibonacci representation of numbers. In base b, the n^th digit represents $b^{n-1}$. In base Fibonacci, the n^th 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.

Answer 2

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.

Answer 3

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.

Answer 4

As described above, the first player loses if $N$, the initial number of marbles, is a Fibonacci number, and wins for any other integer $N > 1$. Proof follows.

First, a definition.

The remainder of any integer $k$ is the smallest entry in a list of distinct non-consecutive Fibonacci numbers that add up to $k$. (For Fibonacci numbers, the remainder of $k$ is $k$.)

Proof of uniqueness: Find the largest integer $i$ such that $F(i) \leq k$. Start the list with $F(i)$. Then iterate by finding the list for $k - F(i)$. Note that at each step, you must be skipping a Fibonacci number, since $F(i) + F(i-1) = F(i+1)$. Thus, if $F(i)$ and $F(i-1)$ would be in the list, then both numbers should be excluded and $F(i+1)$ included, instead.

This process provides a deterministic formula for finding the list of non-consecutive Fibonacci numbers that add up to $k$. Since the ratios of non-consecutive Fibonacci numbers is always $\geq 2$, finding a second list that adds up to the same $k$ would be equivalent to (harder than) finding two distinct binary expressions for the same positive integer, which is impossible.

Strategy: If you see $N$ marbles in front of you, determine the unique list of non-consecutive Fibonacci numbers that add up to $N$, the smallest of which is the remainder of $N$. If you are allowed to remove the remainder number of marbles, do so, and you will win. If you cannot, you will lose, no matter what you do.

This strategy works because if you make the list shorter on your turn by removing the remainder of the current number of marbles, your opponent will not be able to make the list shorter on their turn, and if you do not make the list shorter on your turn, your opponent will be able to make the list shorter on their turn.

Proof: If you remove the remainder, $F(i)$, then you make the list shorter. Either you win immediately (because there was only one entry in the list), or the remainder of the new number of marbles at least $F(i+2) = F(i) + F(i+1) > 2*F(i)$. (Detail: while $F(3) = 2 = 2*F(1)$, you could not have both those entries in the list, as they would be replaced with $F(4) = 3$). Thus, if you make the list shorter, your opponent will never be able to make the list shorter on their next turn.

If, however, you cannot shorten the list, then you must remove some number of marbles $k$ less than the remainder of $N$. Let $F(i)$ be the remainder of $k$. The remainder of $N - k$ will always be either $F(i+1)$ or $F(i-1)$. This is because if $a+b=c$ (all positive integers), then the only way the remainder of $c$ can be greater than the remainders of both $a$ and $b$ is if the remainders of $a$ and $b$ are consecutive Fibonacci numbers. Otherwise, when you combine the sequences, the smaller remainder will always be left behind.

Note, also, that the ratio of two Fibonacci numbers is always $\leq 2$. Thus, if you remove $k$ marbles from $N$, where $k$ is less than the remainder of $N$, then the remainder of $N-k$ will be the next Fibonacci number higher or lower than the remainder of $k$. Since the remainder of $k$ cannot be greater than $k$, the remainder of $N-k$ must be less than or equal to $2k$. Thus, your opponent can always remove the remainder of $N-k$, shortening the list.

Conclusion Thus, the only time you cannot win is if you cannot remove the remainder of the initial number of marbles $N$. This only occurs when $N$ is a Fibonacci number. For any other positive integer, you have a winning strategy.