|
|
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).
|
|
