|
|
Re: Hex Win Proof?
Posted:
Mar 22, 2004 10:35 AM
|
|
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
|
|
