Skip to main content.

Solution to puzzle 146: Odds and evens

Skip restatement of puzzle.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:

Some example games (for n = 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.

  1. How many different possible games are there?
  2. 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:

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 F1 = 1, F2 = 1, Fk = Fk−1 + Fk−2, for k > 2.
Hence g(n) = Fn.

A closed form formula for the Fibonacci sequence is Fn = (Phin − phin) /root 5,
where Phi = (1 + root 5)/2 and phi = (1 − root 5)/2 are the roots of the quadratic equation x2 − x − 1 = 0.

Therefore, the number of different possible games is Fn = (Phin − phin) /root 5.

Part b

Consider the sequence (game) of length k: 1 less than or equal to a1 < a2 < ... < ak = 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 less than or equal to a1 < a2 < ... < ak−1 less than or equal to n − 1.

Let bi = ai − i + 1.
Then 1 less than or equal to b1 less than or equal to b2 less than or equal to ... less than or equal to bk−1 less than or equal to (n − 1) − (k − 1) + 1 = n − k + 1 is a sequence in which each element is odd.
Further, given each bi we can recover ai.  (ai = bi + 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 C(m+k-2, k-1).

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 C((n+k)/2 - 1, k-1) , where k must have the same parity as n.

Source: Inspired by Steven and Todd

Back to top