Solution to puzzle 146: Odds and evens

A and B play a game in which they alternate calling out positive integers less than or equal to n, according to the following rules:

A goes first and always calls out an odd number.
B always calls out an even number.
Each player must call out a number which is greater than the previous number. (Except for A's first turn.)
The game ends when one player cannot call out a number.

Some example games (for n = 8):

1, 8
3, 4, 5, 8
1, 2, 3, 4, 5, 6, 7, 8

The length of a game is defined as the number of numbers called out. For example, the game 1, 8, above, has length 2.

How many different possible games are there?
How many different possible games of length k are there?

Part a

Let g(n) denote the number of different games with upper bound n. If n = 1, there is only one game: 1. Similarly for n = 2, where the only game is: 1, 2. Hence g(1) = g(2) = 1. For n > 2, we establish a recurrence relation for g(n) by considering the following mutually exclusive cases, which encompass all possibilities:

A's first move is 1.
Then B has the same number of games as would A were the upper bound equal to n − 1. (Calling out numbers from the range 2...n − 1, beginning with an even number, is equivalent to calling out numbers from the range 1...n, beginning with an odd number.)
Hence there are g(n − 1) possible games in this case.
A's first move is greater than or equal to 3.
This is equivalent to the upper bound being equal to n − 2.
Hence there are g(n − 2) possible games in this case.

Putting these two cases together, we conclude that g(n) = g(n − 1) + g(n − 2).
This is simply the Fibonacci sequence, which is defined by the recurrence equation F₁ = 1, F₂ = 1, F_k = F_k−1 + F_k−2, for k > 2.
Hence g(n) = F_n.

A closed form formula for the Fibonacci sequence is F_n = (Phiⁿ − phiⁿ) /,
where Phi = (1 + )/2 and phi = (1 − )/2 are the roots of the quadratic equation x² − x − 1 = 0.

Therefore, the number of different possible games is F_n = (Phiⁿ − phiⁿ) /.

Part b

Consider the sequence (game) of length k: 1 a₁ < a₂ < ... < a_k = n, where k and n necessarily have the same parity. (Both are odd or both are even.)
Since the kth number is fixed we may regard this as a sequence of k − 1 elements bounded by n − 1:
1 a₁ < a₂ < ... < a_k−1 n − 1.

Let b_i = a_i − i + 1.
Then 1 b₁ b₂ ... b_k−1 (n − 1) − (k − 1) + 1 = n − k + 1 is a sequence in which each element is odd.
Further, given each b_i we can recover a_i. (a_i = b_i + i − 1.)
So the number of games is equal to the number of ways of choosing k − 1 odd numbers from the odd numbers in the set {1, 3, ... , n − k + 1}, disregarding order and allowing repetition.
This set contains m = [½(n − k + 2)] = ½(n − k) + 1 elements, where [x] is the greatest integer less than or equal to x. (Recall that k and n have the same parity, so ½(n − k) is always an integer.)

The number of such ways of choosing the k − 1 odd numbers from the m-element set is known as a multichoose coefficient, and may be represented in terms of a binomial coefficient by means of the following argument.

Think of the m-element set as defining m − 1 dividing lines around which the k − 1 numbers must be distributed. For instance, if m = 4 and k − 1 = 5, one possible distribution is **|*||**, which corresponds to the sequence 1, 1, 3, 7, 7. The total number of such distributions is by definition given by the binomial coefficient .

Then we have m + k − 2 = ½(n − k) + 1 + k − 2 = ½(n + k) − 1.

Therefore, the number of possible games of length k is given by , where k must have the same parity as n.

Source: Inspired by Steven and Todd