3
$\begingroup$

This is a problem I encountered in this page:

Given an N-sized grids, like the figure A shown below (as N = 4). The blue points are the places the first player can choose, and the red points are the places the second player can choose.

Figure

In the game, the two players take turns to choose two points to get connected by a stick. The two chosen points’ distance should be exactly one-unit length. The first player’s goal is to create a ‘bridge’ that connects a most left point and a most right point. The second player’s goal is to create a ‘bridge’ that connects a most top point and a most bottom point. Figure B shows a possible result (the first player won). In addition, the stick shouldn’t get crossed.

It is said that the first player has a winning strategy, since the grids are symmetric and whoever moves first has an advantage. However, I don't think that the explanation is mathematically rigorous. I need an explanation that is logical and convincing. The explanation can be either constructive or nonconstructive.

$\endgroup$
5
$\begingroup$

This is just the game of Hex. The proof that the first person always wins goes like this:

1) There can be no ties. The only way for a player to block the other person completely is to make a "bridge" themselves.

2) Having an extra move is never a harm. Either we end up using that piece as a bridge (beneficial) or we don't use it and it is irrelevant.

3) Suppose that the second player has a winning strategy. Then the first player can just make a random move and steal that strategy. If that random move is called for in the second person's strategy, then make another random move.

Thus, the first player must always win. This is called a strategy stealing argument.

$\endgroup$
  • $\begingroup$ Thank you for your answer. The strategy-stealing argument is an interesting proof method. $\endgroup$ – Decong Liu Aug 14 '16 at 12:20
  • $\begingroup$ @DecongLiu: Yea, it is. Non constructive proof methods have the ability to lead to weird feelings. $\endgroup$ – Sandeep Silwal Aug 14 '16 at 16:05
0
$\begingroup$

Sandeep Silwal has answered the question; here's a little more about the game. This is the game of Gale or Bridg-it. (Pace Sandeep Silwal, not Hex.) Martin Gardner featured it in his Mathematical Games column in the Oct 1958 Scientific American, reprinted in his New Mathematical Diversions from Scientific American, ch.18. There, he gives a constructive first-player strategy sent to him by Oliver Gross. The game is also described in Wikipedia.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.