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?