Reply
Mon 27 Oct, 2008 01:25 am

There are n dots on a plane (flat surface). There are two players, A and B, who move alternatively; A moves first. The rules of the game are the same for both players: at each move they can connect two points, but they cannot connect points which were already connected or connect a point with itself. In other words, they build a graph (with predefined n vertices) by connecting some of the dots. The winner is the one who makes the graph connected (a graph is connected if there is a path between any two nodes of the graph, however, not every two nodes have to be connected directly). What is the winning strategy for player A, if such exists?

Clearly, if n = 2, the first player always wins.

If n = 3, the second player always wins.

If n = 4, the first player has a winning strategy.

What if n = 13 or n = 14 ???

Organize yourselves into groups of two and play several games where n = 13 and n = 14. Determine which player (first or second) has a winning strategy? Provide convincing argument.

@Valedictum,

The second player wins when n=13 or n=14.