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 ]
Chan-Ho Suh

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


In article <3dfcbf81.0403191414.33bb386a@posting.google.com>, Jonathan
Welton <j_welton@hotmail.com> wrote:

> > 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?

> >
>
> Neither of the proofs (which are basically the same) posted so far is
> correct. Both would apparently conclude that a winning path would be
> formed on a squared board, whereas this is not the case - a squared
> board could end in a draw.
>
> An actual proof must use the hex nature of the board or,
> alternatively, that 3 cells meet at each vertex. A proof is given in
> Cameron Browne's book Hex Strategy, but whether it would convince an
> intelligent layman is not clear.
>
> Maybe a simpler proof could be achieved by induction?
>


Im not sure what proof you are thinking of, but you make it sound like
it's rather complicated.

Here's a proof I think is pretty simple and straightforward (but as
we've some evidence of, not simple to come up with!); you'll have to
tell me if this is the same as Browne's proof. I think the following
proof is understandable to the so-called intelligent layman:

Suppose we've filled up the board with black and white colors.
The boundaries of the hexagons form a graph with edges and vertices.
We can look at the edges that separate hexagons of different colors.
Because of the way the hexagons meet (three to a vertex), there is
always a unique way to continue one of these special edges to another
edge that separates different colors.

In other words, we can't have more than two of these color separating
edges meeting at a common vertex.

So the boundary between the colors consists of either loops (that don't
intersect each other or themselves) and/or paths (that don't intersect
themselves) from a spot on the boundary of the board to another spot on
the boundary of the board.

Now we're not done since we haven't shown the boundary between colors
has at least one of these paths, and furthermore, even if we knew that,
we would have to show there's a path connecting one side of the board
to the opposite side. Then we could conclude there's a chain of one
color joining opposite sides, i.e. there is a winning path.

Here's a simply way to accomplish both these goals. At each corner of
the board, there is a hexagon that is basically shared by each side.
We extend the graph (given by taking the boundaries of all the hexagons
on the board) by adding an edge to each corner hexagon: there's only
one way of doing this without favoring either side. We also pretend
that each side of the board has an extra row of hexagons already
colored by one color. So if one side belongs to white, then the extra
row added adjacently is colored black, and vice versa. Note that the
edge we added at each corner separates these newly added rows and so is
one of the color separating edges of our graph.

Now we've killed two birds with one stone. Since the boundary between
colors now has edges that can't close up to be loops, we must have
paths going from one side to one side (possibly the same side). By
checking the possibilities of where a path starting at a corner can end
up, we can easily see we have a winning path.

I struggled a little in explaining the modification of the board; I can
only wish I was adept in ASCII since with pictures it's pretty simple.
Hopefully people can figure it out.

Final observation, it still remains to show there is *only* one winner!
This is harder (basically one needs to prove a piecewise-linear version
of the Jordan separation theorem), so I'll stop here. In any case, it
doesn't seem the OP was interested in more than showing there is at
least one winner.



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.