Assignment 4, Due Tuesday, November 27th.

1. Consider the 6x7 game of hex, where the first player is trying to connect the two more distant sides and the second player is trying to connect to two nearer sides. It turns out that there's a pairing strategy the guarantees a win for the 2nd player. Show this. Does your solution generalize to the n by n+1 game?
2. In Misere Hex, the goal is to force your opponent to make a path connecting her two sides before you do. Who wins nxn Misere Hex?
3. Mudcrack Y is played on a convex board that is constructed as follows. Imagine the map of a circular country that is divided into n states. A state is a connected set, and no four states meet at a point. (I.E The dual of the map is a planar graph, triangulated except for one large face.) The country is surrounded by three oceans: the Red, the Blue, and the Green. The bounary between two oceans does not occur at a state boundary.

   Play proceeds like Hex (players alternate putting down white and black stones into the states). When the board is filled, the winner is the one who has formed a "Y" with his color. A Y must have beachfront property on all three oceans.

   Give an informal proof that at the end of the game, there must be a Y.

   Below is a picture of the dual graph of a specific game of Mudcrack Y. (Ignore the line around the whole thing.) The three acute corners are the boundaries between the three oceans.