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 ]
Danny Purvis

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


On 24 Mar 2004, Danny Purvis wrote:
>On 18 Mar 2004, Bill Taylor wrote:
>>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?
>>

>
>I think a simple proof is available even for the generalized version
>of the game played like Hex but with cell size and shape only limited
>by the provisos that there still must be four external boundaries
>(let's say Blue tries to go from North to South and Red tries to go
>from East to West) and that adjoining cells must still touch solidly,
>not in a pointlike way.
>
>Any generalized Hex position can be thought of as a collection of
>noninteracting "Red components" on a Blue background. A Red
>component is a set of mutually adjoining Red cells. There are four
>types of Red components. An "island" does not touch any external
>boundary. A "wharf" touches either one boundary or two contiguous
>boundaries. A "canal wall" touches both the North boundary and the
>South boundary and at most one other boundary. A "dam" touches the
>East boundary and the West boundary.
>
>Clearly the presence of a dam signals a win for Red (only). By the
>definition of generalized Hex, there is no way for Blue to get
>through a Red component, and there is no going around a dam since
>it touches the East and West boundaries.
>
>Each of the other three component types, however, fail to connect the
>East and West boundaries, and each of these component types are
>circumnavigated by Blue. Clearly, there is a path of navigable "Blue
>space" adhering to each of these component types. Likewise, it is
>obvious that any noninteracting collection of these three component
>types neither connects the East and West boundaries nor blocks off
>the Blue connection from North to South. (We can think of adding
>these components one by one, with each addition not changing things.)
>
>So, Red wins if and only if a dam is present.
>
>
>Danny Purvis



So, Red wins if and only if a dam is present, and Blue wins if and
only if a dam is not present.



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.