Two players play a game in which they alternate calling out positive integers ≤ N, according to:

The first player must always call out odd numbers.

The second player must always call out even numbers.

Each player must call out a number greater than the previously called number (except, obviously, the very first time).

The player who cannot call out a number loses.

How many different possible games are there? And, if we count a turn each time a player calls out a number, how many different K-turns games are there?

Note: the game is not very fun to play (why?) but the puzzles are interesting!

Assume the referee starts the game by calling out 0. The game can only end when N is called. If only N-2 or less were called, the next player could call out N-1.

Since the numbers alternate odd/even, there is some number of the form 2k+1 between the numbers called out.

It is easy to see there is exactly one K game if N=K. The sequence formed by differences is then 1, 1, 1, ...

If K=N-1, there are N-1 choose 1 places to put the extra 1. If K=N-2, there are N-2 choose 2 places, and so on, until N/2, where things are a little different. Continuing on this way, one could get the observed results though.

Posted by Gamer on 2007-04-16 01:32:28