The Welter game of n coins with the coins in positions 0, a, b, c ... is the same as the Welter game with n-1 coins in positions a-1, b-1, c-1 ... Prove that the Welter function that we defined in class satisfies the following identity:
[ 0 | a | b | ... ] = [ a-1 | b-1 | ... ]
Suppose a ^ b ^ c ^ ... = x. Let t be any non-zero number. Prove that among the following inequalities an even number are true:
a ^ t < a
b ^ t < b
...
x ^ t < x
(Here ^ indicates xor, or nim-addition.) This fact is used in the final step of Conway's proof that the Welter function is indeed the nimber of the game.
Polyonimo Tic-Tac-Toe
A polyomino is defined as follows. Imagine a bathroom floor tiled with square tiles. Take a subset of tiles that are connected. (Two tiles are adjacent if they share a side.) This is a polyomino.
There are 5 distinct tetrominos (polyominos with 4 squares). Note that two tetrominos are the same if one can be mapped to the other via rotations, reflections, or translations.
Tic-Tac-Toe can be played on an infinite tiled bathroom floor with a polyomino P as follows. The two players alternate putting down Xs and Os on the tiles of the floor. The first one to create P using squares marked with her symbol wins.
For each of the five tetrominos, determine if the game is a first-player-win, or if the 2nd player can achieve a draw.
+---+---+---+---+ +---+---+ | | | | | The I | | | +---+---+---+---+ +---+---+ The Square | | | +---+---+---+ +---+---+ | | | | +---+---+---+ The Ell +---+---+ | | | | | +---+ +---+---+---+ The Zee | | | +---+---+---+ +---+---+ | | | | +---+---+---+ The Tee | | +---+