Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Glenn C. Rhoads

Posts: 31
Registered: 12/13/04
Re: Hex Win Proof?
Posted: Mar 20, 2004 3:10 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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
Read Hex Win Proof?
Bill Taylor
3/18/04
Read Re: Hex Win Proof?
Tim Brauch
3/19/04
Read Re: Hex Win Proof?
Brian Chandler
3/19/04
Read Re: Hex Win Proof?
Jonathan Welton
3/19/04
Read Re: Hex Win Proof?
Tim Brauch
3/19/04
Read Re: Hex Win Proof?
Richard Henry
3/20/04
Read Re: Hex Win Proof?
Glenn C. Rhoads
3/20/04
Read Re: Hex Win Proof?
Chan-Ho Suh
3/21/04
Read Re: Hex Win Proof?
Arthur J. O'Dwyer
3/19/04
Read Re: Hex Win Proof?
Bob Harris
3/19/04
Read Re: Hex Win Proof?
Tim Smith
3/19/04
Read Re: Hex Win Proof?
Dvd Avins
3/20/04
Read Re: Hex Win Proof?
Nate Smith
3/20/04
Read Re: Hex Win Proof?
Chan-Ho Suh
3/20/04
Read Re: Hex Win Proof?
G. A. Edgar
3/19/04
Read Re: Hex Win Proof?
Richard Henry
3/19/04
Read Re: Hex Win Proof?
Steven Meyers
3/20/04
Read Re: Hex Win Proof?
Nate Smith
3/20/04
Read Re: Hex Win Proof?
Larry Hammick
3/20/04
Read Re: Hex Win Proof?
Tim Smith
3/20/04
Read Re: Hex Win Proof?
Glenn C. Rhoads
3/20/04
Read Re: Hex Win Proof?
Glenn C. Rhoads
3/21/04
Read Re: Hex Win Proof?
Steven Meyers
3/22/04
Read Re: Hex Win Proof?
Glenn C. Rhoads
3/22/04
Read Re: Hex Win Proof?
Torben Mogensen
3/22/04
Read Re: Hex Win Proof?
Chan-Ho Suh
3/22/04
Read Re: Hex Win Proof?
Torben Mogensen
3/22/04
Read Re: Hex Win Proof?
Chan-Ho Suh
3/23/04
Read Re: Hex Win Proof?
Torben Mogensen
3/23/04
Read Re: Hex Win Proof?
Robin Chapman
3/23/04
Read Re: Hex Win Proof?
Chan-Ho Suh
3/24/04
Read Re: Hex Win Proof?
Robin Chapman
3/24/04
Read Re: Hex Win Proof?
Tim Smith
3/24/04
Read Re: Hex Win Proof?
Robin Chapman
3/24/04
Read Re: Hex Win Proof?
Tim Smith
3/24/04
Read Re: Hex Win Proof?
Jon Haugsand
3/22/04
Read Re: Hex Win Proof?
Andrzej Kolowski
3/23/04
Read Re: Hex Win Proof?
Alexander Malkis
3/23/04
Read Re: Hex Win Proof?
Chan-Ho Suh
3/23/04
Read Re: Hex Win Proof?
Dr. Eric Wingler
3/24/04
Read Re: Hex Win Proof?
Danny Purvis
3/24/04
Read Re: Hex Win Proof?
Danny Purvis

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.