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

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


Chan-Ho Suh <suh@math.ucdavis.nospam.edu> writes:

> In article <w565cxi4n1.fsf@pc-032.diku.dk>, Torben Ægidius Mogensen
> <torbenm@diku.dk> wrote:
>

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

> [snipped]
>
> Why must they intersect? That would seem to be the core of the proof.


If you have a rectangle (skewed or not), a curve that connects top and
bottom must intersect a curve that connects left and right (though
this can be at the end-point of one or both curves). This is true for
any two continuous curves, not just for paths through hexes. I
suppose you can be deliberately obtuse and require a proof for this,
but I think an "intelligent layman" would accept this without proof.
After all, what was asked for was a proof that would be
"understandable and reasonably convincing".

I think going into a rigid mathematical proof from first principles
would be more confusing than not, same as requiring a formal proof
that a+b = b+a in an informal discussion about addition.

Nevertheless, you can come through the proof without using the
intersection property:

We add an extra line filled with white at the top and bottom and
filled with black left and right. The new figure has no corner hexes
and a white path connects top and bottom of the old board if and only
if in the new board the two new white lines are parts of the same
connected area and similarly for the black left-to-right connection.
(If you need a proof for this, you are _really_ obtuse).

We can now do the same reduction as before of eliminating completely
surrounded areas. This eliminates all areas except those that contain
the four new edges, at most one area for each edge. So, we have the
following possibilities:

1) All four edges belong to distinct areas.

2) The two white edges are in the same area, but the two black areas
are distinct.

3) The two black edges are in the same area, but the two white areas
are distinct.

4) There is only one black area and only one white area.

If we can eliminate cases 1 and 4, we are done.

We first make an observation (a lemma, to the mathematicians among
you): An area that contains only one edge has a border consisting of
this edge plus an unbroken path of hexes of the opposite colour. This
means it neighbours exactly one area of the opposite colour.

If all four edges belong to distinct areas, white area A must connect
to a black area B. But since neither can connect to more than one
area, the combination of A and B must be disconnected from the other
two areas, which makes the board disconnected. This eliminates case
1.

Let us assume case 4 and look at the border between the two areas.
This border meets the edge of the board at the four corners (there is
a black/white switch at each corner), so we have four points to
connect by border lines. This must be done by connecting the four
points pairwise by two curves (as the four border lines from the
corners can not all meet in a point). If the two curves intersect,
they must have at least one hex-edge in common (they can not cross in
a point, as each point have only three ways in), so you get an H-like
connection. At the place where two lines join into one, there are
three neighbouring hexes and two of those must be of the same colour.
Hence, one of the three lines can not be a border between two colours.
This means that the border lines can not intersect. So we must have
connections like )(, that clearly separate the board into 3 areas.
Hence, the assumption that there were only two areas is wrong.

Now, all that needs to be made more precise/convincing is that an area
not on the border is completely surrounded by another and can be
eliminated. The first part is easy: The border of an area not
touching an edge must consist of hexes of the opposite colour, and
these are all connected, so they must belong to a single area. Since
they are all connected already, we don't get any new connections by
replacing the surrounded area by the surrounding colour, nor do we
break any connections to the edges, as the surrounded area is
disconnected from both edges.

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.