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

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:32 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


gcrhoads@yahoo.com (Glenn C. Rhoads) wrote in message news:<3396efc6.0403200010.aab22a4@posting.google.com>...
> 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.


Consider two adjacent hexes along the winning chain on the reduced
board. Each of corresponding adjacent/overlapping triangles must
have at least two pieces of the winning color.

Case 1: The unique hex in the overlap is of the winning color.
Then both of the other disjoint "truncated triangles" has some
piece of the winning color. Both pieces are adjacent to the
piece in the overlap and hence must form a chain connecting the
corresponding edges.

Case 2: The unique hex in the overlap is not of the winning color.
Then all four of the remaining hexes are occupied by the winning
color. Again these hexes form a chain connecting the corresponding
edges. (it helps to draw a diagram).

A triangle corresponding to a reduced hex, contains at least two
pieces of the same color and thus, each edge of the triangle must
contain at least one piece (since each edge contains all but one
of the hexes in the triangle). This observation completes the proof.

(you need this fact to establish that for any piece connected to the
edge of the reduced board, that color must also be connected to the
corresponding edge in the original board. This fact also acts as a
base case for induction.)


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


Steve Meyers posted a link to a web page containing essentially
this same argument. However, this page claims *only* the converse
of the above lemma which is not sufficient for the proof; the
other direction is what is needed.



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.