TAOCP 1.2.8 Exercise 38

Section 1.2.8: Fibonacci Numbers

Exercise 38. [35] Write a computer program that plays the game described in the previous exercise and that plays optimally.

Verified: no
Solve time: -

Setup

Exercise 37 defines the following game. A pile initially contains $n$ chips. On the first move, the first player may remove any positive number of chips except all $n$ chips. Thereafter, if the preceding player removed $m$ chips, the next player must remove between $1$ and $2m$ chips inclusive. The player who removes the last chip wins.

Exercise 38 asks for a computer program that plays this game optimally.

Let a position be denoted by $(r,m)$, where $r$ is the number of remaining chips and $m$ is the maximum legal move. Thus the player to move may remove any integer $t$ satisfying

$$ 1 \le t \le \min(r, m). $$

After removing $t$ chips, the game passes to the position

$$ (r-t,2t). $$

The initial move from a pile of $n$ chips corresponds to choosing any

$$ 1 \le t \le n-1, $$

after which the opponent faces the position

$$ (n-t,2t). $$

A position is called winning if the player to move can force a win; otherwise it is called losing.

The task is to characterize the winning positions and then to write a program implementing the optimal strategy.

Solution

The Fibonacci numbers satisfy

$$ F_{k+2}=F_{k+1}+F_k, $$

with

$$ F_1=F_2=1. $$

We claim that the losing positions are precisely those for which

$$ r = F_{k+1}, \qquad m < F_k, $$

for some $k \ge 1$.

The proof proceeds by induction on $r$.

Suppose first that

$$ r = F_{k+1}, \qquad m < F_k. $$

Consider any legal move removing $t$ chips. Since

$$ 1 \le t \le m < F_k, $$

we have

$$ r-t = F_{k+1}-t > F_{k+1}-F_k = F_{k-1}. $$

Also,

$$ 2t < 2F_k. $$

We show that the resulting position $(r-t,2t)$ is winning.

By the Zeckendorf representation theorem implicit in exercise 35, every positive integer has a representation as a sum of nonconsecutive Fibonacci numbers. Since

$$ F_{k-1} < r-t < F_{k+1}, $$

the largest Fibonacci number occurring in the representation of $r-t$ is at most $F_k$.

Write

$$ r-t = F_j + u, $$

where

$$ F_j $$

is the largest Fibonacci number in the representation. Then

$$ u < F_{j-1}. $$

$$ 2t \ge F_{j-1}, $$

then

$$ t \ge \frac12 F_{j-1}. $$

Hence

$$ r = (r-t)+t \ge F_j + \frac32 F_{j-1}. $$

Since

$$ F_{j+1}=F_j+F_{j-1}, $$

this gives

$$ r > F_{j+1}. $$

But

$$ r=F_{k+1}, $$

therefore

$$ j<k. $$

Consequently

$$ F_j \le F_{k-1}, $$

contradicting

$$ r-t>F_{k-1}. $$

Thus

$$ 2t < F_{j-1}. $$

The player who moves next can therefore remove exactly

$$ u=r-t-F_j $$

chips, because

$$ u<F_{j-1} $$

and

$$ u\le 2t. $$

The resulting position is

$$ (F_j,2u). $$

Since

$$ 2u<2F_{j-1}, $$

the induction hypothesis implies that this is a losing position. Therefore every move from $(F_{k+1},m)$ with $m<F_k$ leads to a winning position.

Hence all such positions are losing.

Now suppose that $(r,m)$ is not of this form. Let

$$ F_k \le r < F_{k+1}. $$

$$ m \ge F_{k-1}, $$

the player can remove

$$ t=r-F_k. $$

Since

$$ r<F_{k+1}=F_k+F_{k-1}, $$

we obtain

$$ t<F_{k-1}\le m. $$

Therefore the move is legal. The remaining position is

$$ (F_k,2t). $$

Also,

$$ 2t < 2F_{k-1}. $$

Since

$$ t=r-F_k < F_{k-1}, $$

we have

$$ 2t < F_{k-1} $$

$$ 2t = F_{k-1} $$

according to the value of $t$. In either case the induction hypothesis shows that the resulting position is losing.

Now consider the remaining case:

$$ m < F_{k-1}. $$

Since $(r,m)$ is not losing, we cannot have

$$ r=F_k. $$

Thus

$$ F_k < r < F_{k+1}. $$

Hence

$$ 0<r-F_k<F_{k-1}. $$

Removing

$$ t=r-F_k $$

chips is legal because

$$ t<F_{k-1} $$

and

$$ t\le m $$

would fail only if the original position were already losing.

The resulting position is again

$$ (F_k,2t), $$

which is losing by the induction hypothesis.

Therefore every position not of the form

$$ (F_{k+1},m), \qquad m<F_k, $$

is winning.

The losing positions have now been characterized completely.

The optimal strategy is therefore immediate. Given a position $(r,m)$:

$$ r\le m, $$

remove all remaining chips and win.

Otherwise, let

$$ F_k < r \le F_{k+1}. $$

Remove

$$ t=r-F_k $$

chips whenever

$$ 1\le t\le m $$

and

$$ 2t<F_{k-1}. $$

This leaves the opponent in a losing position.

For the initial move from a pile of $n$ chips, choose the largest Fibonacci number strictly less than $n$, say $F_k$, and remove

$$ n-F_k $$

chips. The opponent then faces

$$ (F_k,2(n-F_k)), $$

which is losing because

$$ n-F_k<F_{k-1}. $$

The corresponding program is straightforward.

procedure Play(r,m)
begin
    if r <= m then
        take r;

    find k such that F_k <= r < F_{k+1};

    t := r - F_k;

    if 1 <= t <= m and 2t < F_{k-1} then
        take t;
    else
        choose any legal move;
end;

For the first move, the parameter $m$ is effectively $n-1$.

Verification

Consider the initial position with $1000$ chips from exercise 37.

The Fibonacci numbers near $1000$ are

$$ F_{16}=987, \qquad F_{17}=1597. $$

The optimal first move removes

$$ 1000-987=13 $$

chips.

The opponent then faces

$$ (987,26). $$

Since

$$ 26 < F_{15}=610, $$

this is a losing position.

Therefore the first player wins by removing $13$ chips initially.

The program above always moves from a winning position to a losing position whenever such a move exists, and the induction proved that every nonlosing position admits such a move. Hence the program plays optimally.

Notes

The losing positions are determined entirely by Fibonacci numbers because the move constraint depends on doubling the previous move. The same phenomenon appears in Wythoff's game and in Zeckendorf representations.