Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 Danny Purvis Posts: 176 Registered: 12/6/04
Re: Hex Win Proof?
Posted: Mar 24, 2004 7:01 AM

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

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

Date Subject Author
3/18/04 Bill Taylor
3/18/04 Tim Brauch
3/19/04 Brian Chandler
3/19/04 Jonathan Welton
3/19/04 Tim Brauch
3/19/04 Richard Henry
3/20/04 Chan-Ho Suh
3/21/04 Arthur J. O'Dwyer
3/19/04 Bob Harris
3/19/04 Tim Smith
3/19/04 Dvd Avins
3/20/04 Nate Smith
3/20/04 Chan-Ho Suh
3/20/04 G. A. Edgar
3/19/04 Richard Henry
3/19/04 Steven Meyers
3/20/04 Nate Smith
3/20/04 Larry Hammick
3/20/04 Tim Smith
3/21/04 Steven Meyers
3/22/04 Torben Mogensen
3/22/04 Chan-Ho Suh
3/22/04 Torben Mogensen
3/22/04 Chan-Ho Suh
3/23/04 Torben Mogensen
3/23/04 Robin Chapman
3/23/04 Chan-Ho Suh
3/24/04 Robin Chapman
3/24/04 Tim Smith
3/24/04 Robin Chapman
3/24/04 Tim Smith
3/24/04 Jon Haugsand
3/22/04 Andrzej Kolowski
3/23/04 Alexander Malkis
3/23/04 Chan-Ho Suh
3/23/04 Dr. Eric Wingler
3/24/04 Danny Purvis
3/24/04 Danny Purvis