A nim-type game and continued fractions

Tamás Lengyel

Occidental College, 1600 Campus Road, Los Angeles, CA 90041 April 2001

1. INTRODUCTION

In the two-person nim-type game called Euclid a position consists of a pair (a, b) of positive integers. Players alternate moves, a move consisting of decreasing the larger number in the current position by any positive multiple of the smaller number, as long as the result remains positive. The first player unable to make a move loses. In the restricted version a set of natural numbers Λ is given, and a move decreases the larger number in the current position by some multiple λ ∈ Λ of the smaller number, as long as the result remains positive. We present winning strategies and tight bounds on the length of the game assuming optimal play. For Λ = Λ_{k} = {1, 2, …, k}, k ≥ 2, the winner is determined by the parity of the position of the first partial quotient that is different from 1 in a reduced form of the continued fraction expansion of b/a.

Apparently, the game was introduced by Cole and Davie [1]. An analysis of the game and more references can be found in [1,7] (see also [3]). The goal is to determine those a and b for which the player who goes first from position (a, b) can guarantee a win with optimal play. There is no tie and the game is finite so one of the players must have a winning strategy for each starting position (a, b). The winning positions are intimately related to the ratio of the larger number to the smaller one when compared to the golden ratio, Φ = \frac{1+\sqrt{5}}{2} ≈ 1.6180, as it is demonstrated by Theorem A: Player 1 has a winning strategy if and only if the ratio of the larger number to the smaller in the starting position is greater than Φ.

The winning strategy can be described in terms of the set W of all unordered pairs (a, b), a, b > 0, with the property that b/a > Φ or a/b > Φ, and its complement set L. It is showed [1,8] that for any pair in W, there is at least one move that leaves a pair in L, and for any pair in L, all legal moves leave a pair in W. We describe the solution in geometric terms in Section 2.

Without loss of generality, we can assume that a < b for the starting position (a, b). (Afterwards, whenever it is helpful, we automatically rearrange the terms so that the first number is the smaller one as long as the numbers are different.) Accordingly, Player 1 has a winning strategy if and only if b/a > Φ. We study a simple variation of the game in Section 3. It leads to the use of the Euclidean algorithm to obtain the continued fraction expansion relevant to the game. In Section 4 this approach is applied to the original game, and results on its length L(a, b) are also given. Generalized versions of the game are introduced and analyzed in Section 5.

2. THE GEOMETRIC APPROACH

We consider the open cone defined by L = {(x, y) | x, y > 0, 1/Φ < y/x < Φ}. The goal of the game is to move to the diagonal y = x and thereby prevent the other player from making further moves. We have two cases depending on whether (a, b) is in L or not. The following two properties describe the differences and are illustrated in Figures 1–3.

[figure]
[figure: (6,8); (7,5)]

[figure: x=3; (3,8); (3,2)]
Figure 1  Figure 2  Figure 3

(i) For every pair (a, b), a ≠ b, there is exactly one direction (horizontal or vertical) in which one can make a legal move. From a position (a, b) ∈ L there is only one legal move, and it leads to a position outside L.

(ii) For every a there are exactly a points in L with x = a. Therefore, if a < b, then there is a unique integer multiple of a, say d = λa, such that decreasing b by d places the new pair (a, b − d) in L provided (a, b) ∉ L.

The first graph shows that (a, b) with a < b forces a downward move while we must move to the left if a > b. Note that the case (a, b) with a > b can be reduced to the one with a < b by a reflection with respect to the line y = x. If (a, b) ∈ L, a < b, then a < b < 2a and thus (a, b − a) is the only legal move from (a, b) (Figure 2). It is easy to see that \frac{a}{b−a} > Φ, yielding property (i). Property (ii) is illustrated in Figure 3. For every integer a there are exactly a points with integer coordinates on the line x = a within the cone L. This follows by the observation that the line x = a meets L in a segment of length Φa − \frac{1}{Φ}a = a. If (a, b) ∉ L then, by the irrationality of Φ, there is exactly one move leading to a point (a, b′) ∈ L for some integer b′, as opposed to the case (a, b) ∈ L when the only legal move will take the player outside L (Figure 2).

In case of the optimal play the loser has only one legal move available to him at each step, i.e., his moves are forced upon him and he cannot even extend the length of the game. Figure 4 illustrates two typical games: the starting positions (9, 2) and (11, 8) give the winning strategy to Players 1 and 2, respectively. In Section 5 we introduce variations of the game in which restrictions on the moves guarantee that even the loser has choices to make.

[figure: (9,2); (1,1); (11,8)]

Figure 4

3. A VARIATION AND THE EUCLIDEAN ALGORITHM In this section, we turn to a deterministic version of the game. Players alternate

moves, and a move decreases the larger number in the current position by the smaller number, as long as the result remains positive. The first player unable to make a move loses. The reason for introducing this variation is to understand how simple continued fractions help in analyzing these and the original games. In fact, the notion of continued fractions is based on the process of continued alternating subtractions [2]. We can express rational numbers as continued fractions by using the Euclidean algorithm. First we take the finite simple continued fraction expansion of b/a = [a_{0}, a_{1}, a_{2}, … a_{n}]. The natural number a_{i} is called the ith partial quotient (or continued fraction digit) of b/a. (Note that we start indexing at i = 0.) This form provides us with a representation of the steps of this game. Note that if b = qa + r with integers q and r (0 ≤ r < a), then q = a_{0}. After a_{0} consecutive subtractions of a from b the remainder becomes smaller than a. We switch their roles and keep continuing the subtractions until r = 0, at which point a = b. The number of legal moves in this game is a_{0} + a_{1} + ⋯ + a_{n} − 1; thus Player 1 wins if and only if ∑_{i=0}^{n} a_{i} is even.

Note that if a_{n} ≠ 1 then the n + 1-digit [a_{0}, a_{1}, a_{2}, … a_{n}] and the n + 2-digit [a_{0}, a_{1}, a_{2}, … a_{n−1}, a_{n} − 1, 1] forms stand for the same rational number and the digit sum is not affected. The former expansion is called the short form. In this paper we always use short forms.

Asymptotic results for the average of the length L′(a, b) = ∑_{i=0}^{n} a_{i} − 1 of the game are given in [2].

4. THE CONTINUED FRACTION BASED APPROACH

We can also completely describe the winning strategy for the original game in terms of the partial quotients a_{i} of b/a, a < b. If b/a = [a_{0}, a_{1}, …, a_{n+1}] = [1, 1, …, 1], i.e., a_{i} = 1 for each i = 0, 1, …, n + 1, then we switch to the short form [a_{0}, a_{1}, … a_{n−1}, 2] with a_{i} = 1, i = 0, 1, …, n − 1. (Note that this happens only if we divide two consecutive Fibonacci numbers.) In this way, we can guarantee that at least one of the partial quotients is different from 1.

Clearly, as long as a_{i} = 1, i = 0, 1, …, k−1, players are forced to take the smaller number from the larger. If the next quotient a_{k} ≠ 1, then we say that a_{k} is the first digit different from 1. For any position (a, b), a < b, with b/a = [a_{0}, a_{1}, …, a_{n}], the actual move of taking λa from b can be specified by the positive integer multiplier λ. The resulting position can be described by the fraction [a_{1}, …, a_{n}] if λ = a_{0} or [a_{0} − λ, a_{1}, …, a_{n}] if λ < a_{0}. Clearly, every move affects the actual first continued fraction digit only. The following theorem was suggested by Richard E. Schwartz [6].

Theorem 1: Let [a_{0}, a_{1}, …, a_{n}] with a_{n} ≥ 2 be the continued fraction expansion of b/a for the starting position (a, b), a < b. Player 1 has a winning strategy if and only if the first partial quotient a_{i} that is different from 1 appears at a position with an even index. In other words, the first player who can actually make a non-forced move has a winning strategy.

This theorem is the explicit form of the statement made by Spitznagel [7] who noted that “the opponent of someone following the (winning) strategy is likely to notice his moves are being forced every step of the way, and from this observation it might be possible for him to determine what the strategy must be.”

Note that the short continued fraction notation guarantees that there is a digit different from 1, namely a_{n} ≥ 2. We use the notation e_{k+1} = [a_{k+1}, a_{k+2} …, a_{n}].

Proof. If a_{k} ≥ 2 then the player facing the ratio b′/a′ = [a_{k}, …, a_{n}] can win. This means that once a player meets the first partial quotient different from 1 then she can win, and the other player will face a 1 in every consecutive step (otherwise a reversal of strategy would be possible). Assume that we have already removed the leading 1s from the expansion and k < n. We will see that the optimal play closely follows the continued fraction expansion by processing and removing consecutive digits. It takes one or two moves (one for each player) to eliminate the actual digit. We have two cases.

(*) If e_{k+1} < Φ then this player can take a_{k}a′ from b′ leaving y = e_{k+1} behind, with 1/Φ < 1 < e_{k+1} < Φ. Note that a_{k+1} = 1 follows. In this case there is a single move used to remove a_{k} from the expansion to get position (a′′, b′′) with ratio y = [a_{k+1}, a_{k+2}, …, a_{n}] = [1, a_{k+2}, …, a_{n}].

(**) Otherwise e_{k+1} > Φ and player takes only (a_{k} − 1)a′ from b′ leaving y = [1, a_{k+1}, a_{k+2}, …, a_{n}] behind. Once again y < Φ, for

1/Φ < 1 < y = 1 + 1/e_{k+1} < 1 + 1/Φ = Φ.

The pair (a′′, b′′) left for the other player has ratio y = b′′/a′′ < Φ. Therefore, y has a continued fraction expansion starting with 1 and thus the other player is forced to take a′′ from b′′. In this case it takes two moves to remove a_{k} from the continued fraction expression.

In any case, after the other player’s move is finished, we get \frac{b′′−a′′}{a′′} = \frac{b′′}{a′′} − 1 < Φ − 1 = \frac{1}{Φ}. We set b′′′ = a′′ and a′′′ = b′′ − a′′, flip the numerator and denominator, and derive that the resulting ratio b′′′/a′′′ > Φ. With d = ⌊b′′′/a′′′⌋ ≥ 1 we can rewrite b′′′/a′′′ = d + \frac{1}{z} > Φ. In fact, d = a_{k+2} and z = [a_{k+3}, a_{k+4}, …, a_{n}] if we followed (*), while d = a_{k+1} and z = [a_{k+2}, a_{k+3}, …, a_{n}] if we used (**). The case d ≥ 2 can be reduced to that of a_{k} ≥ 2. If d = 1 then 1/z > Φ − 1 = 1/Φ, i.e., z < Φ, and we proceed with the argument used in (*), with z playing the role of e_{k+1}.

We can continue this until k becomes n when the player can take the (a_{n} − 1)- times multiple of the smaller number from the larger one, leaving equal numbers for the other player, who will be unable to make a move.

We repeatedly applied the simple fact that 1 + \frac{1}{z} > Φ if and only if z < Φ. The player with winning strategy cannot make a mistake if she wants to win. In summary, she can (and must) always leave y = [1, u_{0}, u_{1}, …, u_{m}] with u = [u_{0}, u_{1}, …, u_{m}] > Φ behind for the other player. This makes y < Φ and forces the other player to simply take the actual smaller number from the larger one. In turn she will face a position with a “safe fraction” u > Φ, i.e., a position outside L. Remark. Theorems A and 1 both give a necessary and sufficient condition for Player 1 to have a winning strategy. This way we obtain a characterization of the condition that x = [a_{0}, a_{1}, …, a_{n}] is greater than Φ in terms of the parity of the location of the first continued fraction digit a_{i} different from 1. This is in agreement with the fact that Φ = [1, 1, 1, …], and the convergents alternately are above and below the exact value.

Assuming optimal play by the winner, tight bounds for the length L(a, b) of the game are given in

Theorem 2: Let [a_{0}, a_{1}, …, a_{n}] with a_{n} ≥ 2 be the continued fraction expansion of b/a for the starting position (a, b), a < b. For the number L(a, b) of steps of the game we get that

n + 1 ≤ L(a, b) = n + 1 + ∑_{{a_{k}≥2 \atop [a_{k+1},...,an]>Φ}} 1 ≤ 2n + 1.

The lower bound is attained if and only if the partial quotients are equal to 1 at all even or all odd positions. The upper bound is reached if and only if all partial quotients are at least 2.

Note that we use the short notation. For example, the position (5, 13) has ratio 13/5 = [2, 1, 1, 2]; hence the lower bound is not attained according to the theorem. In fact, L(5, 13) = 5. The long form 13/5 = [2, 1, 1, 1, 1] does not satisfy the condition a_{n} ≥ 2 of the theorem.

Proof. The proof is based on that of Theorem 1. The lower bound assumes that there are only simple moves, i.e., either a 1 is removed or (*) is used. In the latter case, if for some k and m > k: a_{k} ≠ 1, a_{k+1} = ⋯ = a_{m−1} = 1, and a_{m} ≠ 1, then m − k must be even to guarantee that e_{k+1} < Φ by the Remark made after Theorem 1.

The identity for L(a, b) follows from the observation that an extra move is made when a player applies (**), i.e., when the conditions a_{k} ≥ 2 and e_{k+1} > Φ are satisfied.

To reach the upper bound a_{k} ≥ 2, k = 0, 1, …, n, suffices. In this case the game and the Euclidean algorithm are closely related in the following sense. At any position (a, b), if b = qa + r, q ≥ 2, 0 ≤ r < a, then Player 1 takes q − 1 (rather than q) times a away from b. If r = 0 then the game is over. Otherwise, the other player is left with no other choice but to take a from b−(q−1)·a, for a < b−(q−1)·a < 2a. If the original ratio is b/a = [a_{0}, a_{1}, …, a_{n}] then, at each step, Player 1 will take a_{0} − 1, a_{1} − 1, … times the actual smaller number from the actual bigger one while Player 2 always subtracts the smaller one from the bigger one (and stops when the numbers are equal). Note that Player 1 has a winning strategy when the upper bound is attained.

Examples. The games illustrated in Figure 4 have length L(9, 2) = 3 for 9/2 = [4, 2] (better yet 9/2 = [4_{+}, 2]), and L(11, 8) = 4 for 11/8 = [1, 2, 1, 2]. (The symbol + in the subscript indicates that an extra step is needed due to passing through (**).)

Example: reverse games. We can reverse the continued fraction digits of b/a to get the “reverse” game. If b/a = [a_{0}, a_{1}, …, a_{n}] and gcd(a, b) = 1 then we take c = [a_{n}, a_{n−1}, … a_{0}] in its short form. It is easy to see that the numerator of c (in lowest terms) is b, i.e., c = b/a′ with some a′ such that gcd(a′, b) = 1. If a_{0} > 1 then for the “reverse” game starting at position (a′, b) we obtain L(a′, b) = L(a, b). For example, 18/7 = [2_{+}, 1, 1, 3] gives L(7, 18) = 5 and a reverse 18/5 = [3_{+}, 1, 1, 2] which takes L(5, 18) = 5 steps. If Player 2 has the winning strategy then L(a′, b) = L(a, b) − 1; otherwise L(a′, b) = L(a, b) by the Remark made after Theorem 1. In fact, 43/25 = [1, 1, 2_{+}, 1, 1, 3] has L(25, 43) = 7 and 43/12 = [3_{+}, 1, 1, 2_{+}, 2] gives L(12, 43) = 7.

The game favors Player 1. In fact, Player 1 has more than 60% chance of winning [7]. Assuming that the average behavior of integers 0 < a < b ≤ N approximates that of the random reals in [0, N] and using the geometric approach, Theorem A suggests 1/Φ ≈ .618 for the winning probability in the following sense: lim_{N→∞} P ((a, b) ∈ W | a < b ≤ N) = 1/Φ.

The length n + 1 of the shortest game is the running time of the Euclidean algorithm, and its average is asymptotically \frac{12 ln 2}{π^{2}} ln N ≈ 0.843 ln N for randomly selected starting positions (a, b), a < b ≤ N, as N → ∞ (cf. [2]). (The worst case scenario for the length of the shortest game occurs for Fibonacci-type games, i.e., when the starting position is (a, b) = (q_{n+1}, p_{n+1}) for some n ≥ 1 such that p_{n+2} = p_{n+1} + p_{n} and q_{n+1} = p_{n} with p_{0} = 1 and integer p_{1} = c ≥ 2. The resulting ratio is b/a = [a_{0}, a_{1}, … a_{n}] = [1, 1, …, 1, c], and the length is asymptotically \frac{ln N}{ln Φ} ≈ 2.078 ln N in this case.)

For the length L(a, b) computer simulation suggests that it takes about 9-10 steps on the average to finish games with starting positions (a, b), a < b ≤ 10000.

5. THE RESTRICTED GAME: REDUCTION AND GENERALIZATIONS

In this section, emphasizing the competitive nature of the original game, we discuss its restricted versions which, at the same time, generalize the version discussed in Section 3. Given a set of natural numbers Λ, players alternate moves, and a move decreases the larger number in the current position by some multiple λ ∈ Λ of the smaller number, as long as the result remains positive. The first player unable to make a move loses. For the original game we have Λ = {1, 2, 3, …}. We are interested in various subsets of this set. Theorems 4, 5, and 6 give the complete analysis for three different subsets. The simplified deterministic game of Section 3 works with Λ = {1}. By the connection between the game and the corresponding continued fraction expansion we can easily see Proposition 3: Theorems 1 and 2 can be extended to hold under the conditions Λ = Λ_{k} = {1, 2, …, k}, b/a = [a_{0}, a_{1}, …, a_{n}] with a < b, a_{i} ∈ {1, 2, …, k} for all i = 0, 1, …, n, and a_{n} ≥ 2.

The next interesting case is Λ = Λ_{2} with no restrictions on the a_{i}’s. We sketch the analysis of this game and characterize winning strategies in Theorem 4. The general case of Λ_{k} is covered by Theorem 5. There is an evident parallelism with the original game though the restricted version seems more fair and interesting, for it is no longer true that the first player who can actually make a non-forced move has a winning strategy.

We introduce a reduction of the partial quotients of [a_{0}, a_{1}, …, a_{n}] resulting in a reduced sequence of digits [r_{0}, r_{1}, …, r_{m}] made of 1s and 2s only. This form helps us in finding the player with a winning strategy. In fact, the characterization of a winning strategy in terms of the digits of the reduced sequence reminds us of that of the original game. Once a player meets the first digit r_{i} different from 1 then she can win by never letting the other player face a 2 in the reduced sequence.

Every partial quotient a_{i} ≥ 4 can be replaced by a 1 if a_{i} ≡ 1 mod 3 and by a 2 if a_{i} ≡ 2 mod 3. Any multiple of 3 simply can be dropped from the continued fraction expansion as it gives benefit to neither player: it can be used for keeping one’s turn but cannot be used to switch turns. (Although this fact can be seen directly, a formal justification of this rule will come out in Cases (e) and (f) in the proof of Theorem 4.) We append a 2 to the end of all reduced sequences not ending in a 2. For example, after replacements, we get 11/9 = [1, 4, 2] ⇒ [1, 1, 2] and 36/29 = [1, 4, 7] ⇒ [1, 1, 1, 2], and Player 1 and Player 2 can win in the respective games. In both cases the first 2 characterizes the goals of Player 1: in the former one Player 1 will force Player 2 to finish the removal of the partial quotient 4. In the latter one, Player 1 tries to accomplish the removal of 4 but Player 2 can prevent it from happening by moving to 3, and then to 0, thus forcing Player 1 to face the last quotient 7, then 4 and 1. Remarkably, the conditions of Theorem 1 still work.

Theorem 4: For the game Λ = Λ_{2}, Player 1 has a winning strategy if and only if in the reduced form the first digit r_{i} that is different from 1 appears at a position with an even index.

Proof. The proof is done by induction on the length of the reduced sequence [r_{0}, r_{1}, …, r_{m}]. We give only the main ideas. Let x = [a_{0}, a_{1}, …, a_{n}] be a ratio with reduced form [r_{0}, r_{1}, …, r_{m}], r_{i} ∈ {1, 2}, i = 0, 1, …, m. Player 1 refers to the player facing x. The statement holds for m = 0, i.e., reduced sequences of length 1. In this case, the a_{i}’s are multiples of 3 potentially followed by a last digit a_{n} ≡ 2 mod 3. Winning by Player 1 is assured (cf. Cases (e) and (c) below). Suppose that the statement is true for any reduced sequence [r_{1}, r_{2}, …, r_{m}] of length m.

We prove that any reduced sequence [r_{0}, r_{1}, r_{2}, …, r_{m}] of length m + 1 means a win for Player 1 if the first digit is r_{0} = 2 or if the player facing the sequence [r_{1}, …, r_{m}] loses. Nothing changes if the first digit a_{0} is dropped. We have six cases. The first two deal with r_{0} = 1, while the next two are concerned with r_{0} = 2.

The last two refer to cases when a_{0} is removed, i.e., when a_{0} is a multiple of 3. Each step involves a goal to be met by the player with a winning strategy.

Case (a): The player faced with [r_{1}, r_{2}, …, r_{m}] wins and a_{0} ≡ 1 mod 3. Any move with multiplier λ by Player 1 can be complemented by Player 2 using a move with multiplier 3 − λ to yield a′_{0} ≡ 1 mod 3, and finally forcing Player 1 to remove the first digit of x, leaving Player 2 in a winning position [r_{1}, r_{2}, …, r_{m}].

Case (b): The player faced with [r_{1}, r_{2}, …, r_{m}] loses and a_{0} ≡ 1 mod 3. Player 1 can always move to some a′_{0} congruent to 0 mod 3 and finally remove the first digit of x. This makes Player 2 start with [r_{1}, r_{2}, …, r_{m}] and hence Player 1 a winner.

Case (c): The player faced with [r_{1}, r_{2}, …, r_{m}] wins and a_{0} ≡ 2 mod 3. Player 1 can always move to some a′_{0} congruent to 1 mod 3 and finally force Player 2 to remove the first digit of x. Now Player 1 is facing [r_{1}, r_{2}, …, r_{m}] and wins.

Case (d): The player faced with [r_{1}, r_{2}, …, r_{m}] loses and a_{0} ≡ 2 mod 3. Player 1 can always move to some a′_{0} congruent to 0 mod 3 and finally remove the first digit of x. This makes Player 2 start with [r_{1}, r_{2}, …, r_{m}] and hence Player 1 a winner.

Case (e): The player faced with [r_{1}, r_{2}, …, r_{m}] wins and a_{0} ≡ 0 mod 3. Player 1 can always move to some a′_{0} congruent to 1 mod 3 and finally force Player 2 to remove the first digit of x. Now Player 1 is facing [r_{1}, r_{2}, …, r_{m}] and wins.

Case (f): The player faced with [r_{1}, r_{2}, …, r_{m}] loses and a_{0} ≡ 0 mod 3. Any move with multiplier λ by Player 1 can be complemented by Player 2 using a move with multiplier 3 − λ to yield a′_{0} ≡ 0 mod 3. Finally Player 2 removes the first digit of x. Now Player 1 is facing [r_{1}, r_{2}, …, r_{m}] and loses. This completes the inductive step.

Note that if the first digit is reduced to 1 then it acts like a negation, i.e., changing the winner-loser relationship based on [r_{1}, r_{2}, …, r_{m}] in agreement with the theorem. The optimal play can be established by processing the reduced sequence backwards, i.e., from right to left and setting goals for the moves in accordance with the proof. At the end, the winning strategy emerges as a sequence of instructions on how to remove the digits of the original continued fraction one by one, from left to right. The following examples illustrate the process.

Example. The starting position (6, 19), i.e., 19/6 = [3, 6] reduces to [2] which is a win for Player 1. As [6] reduces to [2], which is a win for Player 1, we proceed with Case (e). The goal for Player 1 is to always move to some value v ≡ 1 mod 3 at this digit. As [3, 6] reduces to [2] again, the same goal is set for Player 1. In terms of the actual steps, Player 1 first finds that the first target is v = 1 as v ≡ 1 mod 3. This instructs Player 1 to take twice the smaller number from the larger one, i.e., 2 · 6 from 19. It leaves the position (6, 7) with 7/6 = [1, 6] for Player 2 forcing the removal of the quotient 1. Player 1 is presented with 6/1 = [6], i.e., the position (1, 6). Player 1 has to move to 4 ≡ 1 mod 3 by Case (e) again. In fact, the game is completed by taking 2 · 1 from 6 to yield (1, 4). Now Player 2 moves to (1, u), u = 2 or 3, and Player 1 wraps up the win by moving to 1 mod 3, i.e., (1, 1).

Example. The ratio 2393/459 = [5, 4, 1, 2, 6, 5] results in [2, 1, 1, 2, 2], i.e., a win for Player 1. The backward processing provides the following goals: at quotient 5 move to 1 mod 3 by Case (c), at 6 move to 1 mod 3 by Case (e), at 2 move to 1 mod 3 by Case (c), at 4 move to 0 mod 3 by Case (b), and at 5 move to 1 mod 3 by Case (c). Note that 1934/459 = [4, 4, 1, 2, 6, 5] is a win for Player 2 according to the reduced sequence [1, 1, 1, 2, 2]. The goals for Player 2 are similar to those of the previous example for Player 1 except that at processing the first quotient 4, Player 2 must move to 1 mod 3 by Case (a).

For the length L_{2}(a, b) of the game we get L_{2}(a, b) = 2 ∑_{a_{i}≠1}⌈\frac{a_{i}}{3} ⌉+n_{1} −n_{a,b,d} −1 where n_{1} and n_{a,b,d} are the number of a_{i}’s that are equal to 1 and the number of times we used Cases (a), (b), and (d).

The general case Λ = Λ_{k}, k ≥ 2, is fairly similar to that of Λ_{2}. Reduction can be applied in the following sense: any multiple of k + 1 can be dropped from the continued fraction expansion and every partial quotient a_{i} > 2 can be replaced by a 1 if a_{i} ≡ 1 mod (k + 1) and by a 2 if a_{i} ≡ 2, 3, …, k mod (k + 1). Theorem 4 translates into

Theorem 5: Player 1 has a winning strategy for the game Λ = Λ_{k}, k ≥ 2, if and only if in the reduced form the first digit r_{i} that is different from 1 appears at a position with an even index. For the length L_{k}(a, b) of the game we get L_{k}(a, b) = 2 ∑_{a_{i}≠1}⌈\frac{a_{i}}{k+1}⌉ + n_{1} − n_{a,b,d} − 1 where n_{1} and n_{a,b,d} are the number of a_{i}’s that are equal to 1 and the number of times we used Cases (a), (b), and (d).

We omit the proof, which closely follows that of Theorem 4 with Cases (c) and (d) referring to a_{0} ≡ 2, 3, …, k mod (k + 1). Note that if k = 1 then we never encounter Cases (c) and (d). Cases (a) and (b) correspond to an odd quotient a_{i} and thus, L_{1}(a, b) is in agreement with L′(a, b) = ∑_{i=0}^{n} a_{i} − 1.

The winner can be determined by using the reduced sequence in its short form.

One might think (but the author has not been able to prove) that the winning probability of Player 1 for game Λ_{k} changes from 1/2 to 1/Φ as k → ∞.

The reader might consider other generalizations of the original game. Clearly, Λ must contain 1 if we want the game to be playable until a ratio of 1 is reached. The referee suggested selecting Λ to be the set of all odd natural numbers. It turns out that this version can be analyzed similarly to the deterministic game discussed in Section 3 by means of a slightly more general

Theorem 6: For any subset Λ of the odd natural numbers containing 1, Player 1 wins if and only if the parity of the sum of the partial quotients of b/a is even.

The proof is straightforward for every move changes the parity of the sum. The game is deterministic in the sense that the outcome of the game is not influenced by skill. Only the length of the game can be affected by the particular moves.

We note that the general game with starting position (a, b), a < b, and b/a = [a_{0}, a_{1}, …, a_{n}] can be also analyzed by playing Bachet’s subtraction game on a sequence of n + 1 connected intervals. Two consecutive intervals share one of their endpoints. The length of the ith interval is equal to the partial quotient a_{i−1}, 1 ≤ i ≤ n, and a_{n} − 1 if i = n + 1. Starting with the first interval, each move takes the player to go to another point of the interval. The Sprague–Grundy numbers can be easily determined. (Visually, one can play the game on the Stern–Brocot tree of rationals, starting at point 1 and ending at point (a, b), a < b, with the game represented by intervals of length a_{0}, a_{1}, …, a_{n−1}, a_{n} − 1.)

ACKNOWLEDGMENT

I wish to thank Ramin Naimi for helpful discussions and for involving Richard Schwartz who suggested Theorem 1. I also thank Greg Tollisen for his useful suggestions and comments, and Jerrold Grossman for providing me with some references. The author is grateful to an anonymous referee for careful reading and making helpful recommendations that significantly improved the presentation of the paper.

REFERENCES

1. A. J. Cole and A. J. T. Davie. “A game based on the Euclidean algorithm and a winning strategy for it.” Math. Gaz. 53 (1969): 354–357.

2. Philippe Flajolet, Brigitte Vallée, and Ilan Vardi. “Continued fractions from Euclid to the present day.” INRIA preprint, March 2000.

3. Jerrold W. Grossman. “Problem #1537.” Mathematics Magazine 70 (1997): 382.

4. A. Ya. Khinchin. Continued fractions. New York: Dover, 1997.

5. A. J. van der Poorten. “Notes on continued fractions and recurrence sequences.” Number theory and cryptography (Sydney, 1989), 86–97, London Math. Soc. Lecture Note Ser. 154, Cambridge Univ. Press, Cambridge, 1990.

6. Richard E. Schwartz. personal communication, 2000.

7. Edward L. Spitznagel, Jr. “Properties of a game based on Euclid’s algorithm.” Mathematics Magazine 46 (1973): 87–92.

8. Philip D. Straffin. “A Nim-type Game, Solution to Problem #1537.” Mathematics Magazine 71 (1998): 394–395.

AMS Classification Numbers: 91A46, 91A20, 11A55, 11A05