All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
Always greater (Posted on 2007-04-14) Difficulty: 3 of 5
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!

    See The Solution Submitted by Federico Kereki    
    Rating: 4.0000 (2 votes)

    Comments: ( Back to comment list | You must be logged in to post comments.)
    Solution solution | Comment 3 of 6 |
        # 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
    Please log in:
    Login:
    Password:
    Remember me:
    Sign up! | Forgot password


    Search:
    Search body:
    Forums (0)
    Newest Problems
    Random Problem
    FAQ | About This Site
    Site Statistics
    New Comments (1)
    Unsolved Problems
    Top Rated Problems
    This month's top
    Most Commented On

    Chatterbox:
    Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information