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 ]
Torben Mogensen

Posts: 60
Registered: 12/6/04
Re: Hex Win Proof?
Posted: Mar 22, 2004 4:59 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) writes:

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


The easy part is proving that both players can't win at the same time:

Assume that there is a white path connecting top and bottom and a
black path connecting left to right. These must intersect, but on a
hex board two paths can only intersect if they share a hex. Since
this can't be both black and white, one of the paths must be broken.
This contradicts the assumption.

It is a bit harder proving that one side must win. But it isn't too
bad.

We consider connected areas of one colour. It is easy to see that an
area that does not connect to the edge of the board must be completely
sorrounded by the other colour, so it makes no difference if we
replace these by the sorrounding colour (as it neither blocks nor
connects anything). We are now left only with areas that connect to
the edge of the board. Those that connect to only one edge of the
board (corners are counted as two edges) can also be replaced with the
other colour, so we are left with areas that connect two or more edges
of the board. If an area is at a corner and only touches the two
sides that share that corner, it can also be replaced by the opposite
colour. This can be repeated until the only remaining areas touch two
opposite edges (and possibly more). If there is only one area left,
that colour obviously wins. If there are more than one area left, the
pair of opposite edges they connect must be the same (otherwise the
areas would cross, which we showed above isn't possible). So one pair
of opposite edges are connected by both colours, and one of them must
be the colour that has this as a goal.

QED.

Torben



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.