|
Re: Hex Win Proof?
Posted:
Mar 20, 2004 3:10 AM
|
|
w.taylor@math.canterbury.ac.nz (Bill Taylor) wrote in message news:<716e06f5.0403181938.72a82f90@posting.google.com>... > > It is an old theorem that in Hex, once the board has been completely > filled in with two colours, there *must* be a winning path for one > or other of them. > > Now, I can prove this easily enough mathematically, but I'm wondering if > there is a simple proof, or proof outline, that would be understandable > and reasonably convincing to the intelligent layman. > > Can anyone help out please?
Here's a pretty proof involving a closely related game called Y. (Don't hesitate about the length of this post; it consists mostly of descriptions of Y, the relation to Hex, and the definition of "Y-reduction". The final proof is very short.)
A Y board consists of a triangular configuration of hexagons. Play is the same as Hex except that the goal is to build a chain that connects all three sides (as in Hex, corner hexes belong to both sides).
Y is a generalization of Hex as illustrated in the following ascii diagram. (view in a fixed font)
_ _/* _/*\_/ _/*\_/* _/ \_/*\_/ _/ \_/ \_/* _/ \_/ \_/ \_/ / \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/+ \_/ \_/+\_/ \_/+\_/+ \_/+\_/ \_/+ \_/
* are pieces of one player and + are pieces of the other player.
Playing Y from the above legal position is equivalent to playing Hex in the unoccupied hexes of this position because a chains wins for Y if and only if the chain restricted to originally unoccupied hexes wins for Hex (in the Hex version, player * is connecting the southwest border up to the northeast). Thus, to prove a completely filled-in Hex board has a winning chain for one of the two players, it suffices to prove that a filled-in Y board has a winning chain for one of the two players.
The proof makes use of "Y-reduction."
Y-reduction: From a completely filled-in order n Y-board,construct a completely filled-in order n-1 Y-board as follows. For each triangle of three mutually adjacent hexes oriented the same way as the board, replace it with a single hexagon whose piece color is that of the majority of the colors in the triangle. Ex. _ _/4\ _/3\1/ _/3 _/2\1/3\ _/2\1/ /1\1/2\2/ /1\1/2 \1/1\2/2\ \1/1\2/ \2/1\3/ \2/1 \3/1\ \3/ \4/
The triangle of hexes with coordinates x x+1 x y y y+1 on the order-n board corresponds to the hexagon x y on the order n-1 board
Lemma: If a player has a winning chain on the reduced board, then that player also has a winning chain on the original board.
It's easy to verify (but ugly to write up rigorously) that if a player has a winning chain on the reduced board, then he also has a winning chain through the corresponding triangles on the original board. [note: the converse of the lemma is also true but we don't need it.]
Thm. One of the player's has a winning chain on a completely filled-in Y board.
Proof: From any completely filled-in Y board, perform a sequence of Y-reductions to reduce the board to a filled-in order 1 board. The filled-in order 1 board obviously has a winning chain and hence by the lemma, each Y board in the sequence has a winning chain.
I wish I could take credit for this proof but it is due to Ea Ea (his former name was Craige Schensted).
|
|