Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Hex Win Proof?
Replies: 41   Last Post: Mar 24, 2004 6:39 PM

 Messages: [ Previous | Next ]
 Glenn C. Rhoads Posts: 31 Registered: 12/13/04
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).

Date Subject Author
3/18/04 Bill Taylor
3/18/04 Tim Brauch
3/19/04 Brian Chandler
3/19/04 Jonathan Welton
3/19/04 Tim Brauch
3/19/04 Richard Henry
3/20/04 Chan-Ho Suh
3/21/04 Arthur J. O'Dwyer
3/19/04 Bob Harris
3/19/04 Tim Smith
3/19/04 Dvd Avins
3/20/04 Nate Smith
3/20/04 Chan-Ho Suh
3/20/04 G. A. Edgar
3/19/04 Richard Henry
3/19/04 Steven Meyers
3/20/04 Nate Smith
3/20/04 Larry Hammick
3/20/04 Tim Smith
3/21/04 Steven Meyers
3/22/04 Torben Mogensen
3/22/04 Chan-Ho Suh
3/22/04 Torben Mogensen
3/22/04 Chan-Ho Suh
3/23/04 Torben Mogensen
3/23/04 Robin Chapman
3/23/04 Chan-Ho Suh
3/24/04 Robin Chapman
3/24/04 Tim Smith
3/24/04 Robin Chapman
3/24/04 Tim Smith
3/24/04 Jon Haugsand
3/22/04 Andrzej Kolowski
3/23/04 Alexander Malkis
3/23/04 Chan-Ho Suh
3/23/04 Dr. Eric Wingler
3/24/04 Danny Purvis
3/24/04 Danny Purvis