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!
# of \k
n games 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
1 1 1
2 1 . 1
3 2 1 . 1
4 3 . 2 . 1
5 5 1 . 3 . 1
6 8 . 3 . 4 . 1
7 13 1 . 6 . 5 . 1
8 21 . 4 . 10 . 6 . 1
9 34 1 . 10 . 15 . 7 . 1
10 55 . 5 . 20 . 21 . 8 . 1
11 89 1 . 15 . 35 . 28 . 9 . 1
12 144 . 6 . 35 . 56 . 36 . 10 . 1
13 233 1 . 21 . 70 . 84 . 45 . 11 . 1
14 377 . 7 . 56 . 126 . 120 . 55 . 12 . 1
15 610 1 . 28 . 126 . 210 . 165 . 66 . 13 . 1
16 987 . 8 . 84 . 252 . 330 . 220 . 78 . 14 . 1
17 1597 1 . 36 . 210 . 462 . 495 . 286 . 91 . 15 . 1
18 2584 . 9 . 120 . 462 . 792 . 715 . 364 . 105 . 16 . 1
19 4181 1 . 45 . 330 . 924 . 1287 . 1001 . 455 . 120 . 17 . 1
20 6765 . 10 . 165 . 792 . 1716 . 2002 . 1365 . 560 . 136 . 18 . 1
21 10946 1 . 55 . 495 . 1716 . 3003 . 3003 . 1820 . 680 . 153 . 19 . 1
22 17711 . 11 . 220 . 1287 . 3432 . 5005 . 4368 . 2380 . 816 . 171 . 20 . 1
23 28657 1 . 66 . 715 . 3003 . 6435 . 8008 . 6188 . 3060 . 969 . 190 . 21 . 1
24 46368 . 12 . 286 . 2002 . 6435 .11440 .12376 . 8568 . 3876 . 1140 . 210 . 22 . 1
25 75025 1 . 78 . 1001 . 5005 .12870 .19448 .18564 .11628 . 4845 . 1330 . 231 . 23 . 1
The number of games for a given n is F(n) -- i.e., the nth Fibonnaci number.
The triangle of possible number of games by length k is Pascal's triangle. When k and n are of opposite parity, the result is zero, marked with a dot on the chart. When k and n are of the same parity, the number is C((n+k)/2-1, k-1).
DECLARE SUB choose (choice#)
CLEAR , , 9999
DEFDBL A-Z
DIM SHARED n, k
DIM SHARED ct(50, 50)
FOR n = 1 TO 25
PRINT n
k = 0
FOR i = 1 TO n STEP 2
choose i
NEXT
NEXT
OPEN "alwgreat.txt" FOR OUTPUT AS #2
FOR n = 1 TO 25
PRINT USING "## #####"; n; ct(n, 0);
FOR j = 1 TO 14
IF ct(n, j) > 0 THEN
PRINT USING "#####"; ct(n, j);
ELSE
PRINT " .";
END IF
NEXT
PRINT
NEXT
FOR n = 1 TO 25
PRINT #2, USING "## #####"; n; ct(n, 0);
FOR j = 1 TO n
IF ct(n, j) > 0 THEN
PRINT #2, USING "#####"; ct(n, j);
ELSE
PRINT #2, " .";
END IF
NEXT
PRINT #2,
NEXT
SUB choose (choice)
k = k + 1
IF choice = n THEN ct(n, k) = ct(n, k) + 1: ct(n, 0) = ct(n, 0) + 1: k = k - 1: EXIT SUB
FOR i = choice + 1 TO n STEP 2
choose i
NEXT
k = k - 1
END SUB
|
|
Posted by Charlie
on 2007-04-14 15:12:01 |
solution
