Mathematical Games --- CMU Spring 2005 --- Frieze, Sleator (original) (raw)

• The following game called "Boxing Match" was the January 1994 programmer of the month contest. (POTM site) (This POTM contest). Two CMU graduates won the contest by winning every single one of their games!

"The Boxing Match" - The January 1994 Programmer Of The Month (POTM) contest.  
        (deadline is midnight of New Year's Day, Sat. 1/1/94)  
--------------------------------   THIS IS A SAMPLE ARENA.  32x16 SPOTS.  
--------------------------------     (WITH A FEW (o) YOU CAN'T USE)  
-----o--------------------------  
--------------------------------   YOUR WEAPONS ARE SQUARE BOXES: 1x1, 2x2,  
--------------------------------     3x3, 4x4, .... through 16x16  
--------------------------------  
--------------------------------   YOUR OPPONENTS HAVE THE SAME WEAPONS.  
----------------o---------------  
---------------o-o--------------   ON YOUR TURN, YOU CAPTURE ONE BOX WORTH  
------------------o------------o   OF UNUSED ARENA - THEN YOUR OPPONENTS DO  
--oo---------------o------------   THE SAME ON THEIR TURN ...  
--oo----------------------------  
--oo----------------------------   IF YOU CAPTURE THE LAST SPOT - YOU WIN.  
--------------------------------  
--------------------------------   YOU PLAY, HEAD-TO-HEAD, AGAINST OTHER  
------------------------------oo   ENTRANTS - CAN YOU BEAT THEM????  
      <---- 32 wide ---->             ( 16 tall )  

Describe an approach to programming this game that would take advantage of the theory that you learned in this course. Your approach should be able to crush an opponent who does not know this theory.

• In class we discussed the take-away game which starts with a pile of n chips. The first player must remove 1 or more chips, but not take the whole pile. Thereafter each player must remove one or more chips, but not more than were removed on the previous move. The player taking the last chip wins. We showed that the initial game is a P position if and only if n is a power of 2.
  Compute the Sprague-Grundy function (the Nimber) of this game for_n_ up to 20.
  Propose (and prove if possible) a general formula for the Nimber of this game as a function of n.
• The SOS game is defined as follows. The board consists of a row of n squares, initially empty. Players take turns selecting an empty square and writing either an S or an O in it. The player who succeeds in completing SOS in consecutive squares wins the game. If the whole board gets filled up without an SOS appearing, the game is a draw.
  A. Supose that n=4, and the first player puts an S in the first square. Show the second player can win.
  B. Show that if n=7, the first player can win.
  C. Show that if n=2000, the second player can win.
  D. Who, if anyone, wins the game if n=14.
• Problem 4.5-4 of Ferguson, Kayles (page 26 of Ferguson Part I)