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 ]
Tim Smith

Posts: 1,142
Registered: 12/6/04
Re: Hex Win Proof?
Posted: Mar 20, 2004 2:33 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


In article <716e06f5.0403181938.72a82f90@posting.google.com>, Bill Taylor
wrote:
> 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 following has a bunch of cases, but I think the intelligent layman can
follow them.

Let's assume Red has top/bottom, and Blue has the sides. We want to show
that if Blue does not have a win when the board is full, the Red must have
one.

There must be at least one Red hex on the top, and at least one on the
bottom, or else Blue would have a win along the top or bottom. Pick a Red
hex on top, U, and a Red hex on the bottom, D, and consider any path between
them. Go along that path from bottom to top.

If Red doesn't have a win, that path must run into a Blue hex. Let S be the
set of all Blue hexes connected to that Blue hex. Call the Red hex that ran
into S A. As you continue along the path, you must eventually reach a Red
hex that is not surrounded by S. Call that Red hex B.

If S does not touch any edge, then there is an all Red path from A to B.
Just go around the edge of S in either direction from A to B. If S touches
one edge, there is still a Red path from A to B.

Thus, we cannot reroute around S only if S connects to two or more edges.
Let's consider the cases:

1. S connects to the top and bottom. Then the Red hexes adjacent to at
least one of its sides form a win for Red, unless S connects is connected to
opposite corners, in which case S would be a win for Blue.

2. S connects to left and right. S is a win for Blue.

3. S connects to the bottom and a side. WLOG we can assume S is connected
to the left side. If the connection to the bottom is to the left of D, then
there is a path from A to B around the boundary of S. If the connection to
the bottom is to the right of D, then there is a connection from B to the
bottom along the boundary of S (unless S connects to the bottom at the
corner, in which case S is a win for Blue).

4. S connects to the top and a side. Similar to case #3. If the top
connection is on the same side of U as the side connection, then there is a
connection from A to B. Otherwise, there is a connection from A to the top.

In all these cases, we are able to reroute the path such that it is still
connected to the top and the bottom, but avoids S. Hence, if Blue does not
have a win, there is a win for Red, and this procedure will even find such a
win.

--
--Tim Smith



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.