# Homework Assignment 2

## Due Friday February 4

1. 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 | ... ]

2. 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.

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