Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 Larry Hammick Posts: 1,876 From: Vancouver Registered: 12/6/04
Re: Hex Win Proof?
Posted: Mar 20, 2004 3:06 AM

"Steven Meyers" <swmeyers@fuse.net> wrote in message
> w.taylor@math.canterbury.ac.nz (Bill Taylor) wrote in message
> > 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.

> Check http://web.cs.ualberta.ca/~javhar/hex/hex-yproof.html for a
> simple proof using the game of Y.

Nice proof and a nice page.
Another way is to consider not the cells, but just the boundary
between red and blue when the board is full. A component of
the boundary must be either a closed curve (in which case we
can contract it to a point, losing nothing) or a path from an edge
to the same edge (contract again) or a path from one edge to
another. In the last case, consider an enpoint of a boundary
component which is closer than any other to an obtuse corner
of board. According to where the other endpoint of that
component is, we can determine who has won the game.

Here's a related result in topology. Let T be the Euclidean
triangle with vertices (1,0,0) (0,1,0) (0,0,1) in homogeneous
coordinates. Let f be any continuous mapping T to T, and write
f(x,y,z) = (A(x,y,z), B(x,y,z), C(x,y,z))
Let S be the (closed) subset of T consisting of the points (x,y,z)
such that _at least two_ of these inequalities hold:
A(x,y,z) >= x
B(x,y,z) >= y
C(x,y,z) >= z.
Then S has a connected component which meets all three
sides of T.
LH

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