Princeton University
|
Computer Science 345 |
|
The Ramsey GameYou have a red crayon, and your friend has a blue one. The board consists of 6 dots are drawn on a piece of paper. You two alternate moves - in each move one of you connects a pair of (yet unconnected) dots using your crayon. You lose if you have completed a triangle with your color.
Play it with friends. Can you see a good strategy? Can you prove that this game can never end with a draw? Is the same true with 5 dots instead of 6? Is it true with 7?
GameAlice and Bob play the following game on a rectangle board. Each move a player picks a non-marked square on the board and marks all the squares that are below and to the left of the chosen square (see the picture below). The game ends when the last square is marked, and the player who makes the last move loses. Who wins Alice or Bob, if Alice starts first? Does the answer depend on the size of the board?
M Alice M M M M M M M Bob M M M M M M