
Re: Hex Win Proof?
Posted:
Mar 22, 2004 10:35 AM


ChanHo Suh <suh@math.ucdavis.nospam.edu> writes:
> In article <w565cxi4n1.fsf@pc032.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 endpoint 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 lefttoright 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 hexedge in common (they can not cross in a point, as each point have only three ways in), so you get an Hlike 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

