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 | | +---+`

Mathematical Games Home Page

Danny Sleator Last modified: Fri Jan 28 8:03:31 2005