Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: More Game theory

  1. Sep 25, 2010 #1
    1) Problem 1 For every i; j with 1<=i; j<=8 fi nd a nim heap which is equivalent to the i x j
    game of Chop.

    CHOP Game Start with an i x j array of boxes viewed as a plank which
    is secured only at the lower left hand corner. Each player is a
    pirate, and they alternate turns. On each turn a player must
    either make a vertical or horizontal chop of the plank, and then
    any piece no longer connected to the lower left hand corner falls
    off into the water. The player who moves last wins.


    What I need to do
    Generalize the result of Problem 1 by finding a general formula for the nim heap
    equivalent to an i x j game of Chop.

    What I did

    Essentially the way we were showed in class was to start with a 1x1 and then 1x2, 2x2, 2x3,3x3,etc chop game and determine the "small base cases" and work our way up. after we had a 2x2 grid,

    1 0
    0 1

    He said that each new board was simple the smallest value not present in the corresponding row and column.

    For example: If i had the below configuration and wanted to know X, I would look at the 2,3,0 and 2,3 and notice that no 1 is present, therefore X=1

    2 3 0 X
    1 0 3 2
    0 1 2 3

    I did this up to i,j=11

    10 11 8 9 14 15 12 13 2 3 0
    9 8 11 10 13 12 15 14 1 0 3
    8 9 10 11 12 13 14 15 0 1 2
    7 6 5 4 3 2 1 0 15 14 13
    6 7 4 5 2 3 0 1 14 15 12
    5 4 7 6 1 0 3 2 13 12 15
    4 5 6 7 0 1 2 3 12 13 14
    3 2 1 0 7 6 5 4 11 10 9
    2 3 0 1 6 7 4 5 10 11 8
    1 0 3 2 5 4 7 6 9 8 11
    0 1 2 3 4 5 6 7 8 9 10


    I can see some patterns in the table but none that apply in all cases...I have no idea where to go with this!

    Thanks


    PS: SOrry the grid doesn't line up perfectly, not sure how to do ASCII in here or post a table
     
  2. jcsd
  3. Sep 25, 2010 #2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook