The box below forms a basis for a game between two players. The idea is that the two players take turns shading in one of the six rectangles (numbered 1 through 6) with one of two colors- say red or blue.

+-+---+------------+
| |   |            |
| | 2 |     3      |
| |   |            |
| +---+--------+---+
|1|            |   |
| |     6      | 4 |
| |            +---+
| |            | 5 |
+-+------------+---+

Either player can use either color on any turn. It is illegal to shade a rectangle with a color that has already been given to a neighboring rectangle. If you don't have a legal move at your turn, you lose the game.

Prove that for each opening move by the first player, the second player can always win.

To fully colour this rectangle requires three colours.  Note that each of the internal vertices bordering the "6" zone is flanked by 3 areas.

At the moment I'm failing to express a generalisation the proof rests in addressing that concept.

Posted by brianjn on 2013-05-03 04:51:05