Date: Mar 23, 2004 3:49 AM
Author: Torben Mogensen
Subject: Re: Hex Win Proof?

Chan-Ho Suh <> writes:

> In article <>, Torben Ægidius Mogensen
> <> wrote:

> > Chan-Ho Suh <> writes:
> >

> > > In article <>, Torben Ægidius Mogensen
> > > <> 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".
> > [snipped]

> That's a good point, about what's "reasonably convincing" to the
> layman. I was just thinking the other day that probably none of the
> proofs (or attempted proofs) in this discussion is needed to be
> "reasonably convincing" to the layman.
> Anyway, it appears to me that the discussion has turned basically on
> how to prove these results (barring considerations of
> laymen-convincing).
> But regardless of all that, my point was that you purported to give a
> proof of a result by reducing it to something which is more or less the
> the crux of the matter, and then saying it was obvious.

IMHO, the fact that the paths must intersect is obvious to a layman,
but the fact that a path must exist is not. Hence, it is the latter
part that needs to be detailed.

> It's not a matter of being deliberately obtuse. Showing the result
> for continuous curves is much harder than anything required for the
> Hex proof.

Indeed, as it requires a rigorous definition of what it means to be
continuous. However, a layman has a good intuition about what it means
for a curve to be continuous and what the consequences of that is.
Basically, a non-mathematician will think of a continuous curve as
"something that can be drawn without lifting the pencil", and that is
good enough for this purpose.

> Of course, in this case, we are in a discrete setting and so we
> don't have to work so hard, but I felt that it needed to be pointed
> out to readers that this is something that needs to be demonstrated
> rigorously.

Indeed, if we want to prove it to a mathematician who does not already
accept the intermediate value theorem (of which the intersection
property is a simple consequence).

> It seems your goal was to give a pseudo-proof, convincing to the person
> on the street; on the other hand, you combined that with a fairly
> rigorous proof in the rest of your post. I think it's perfectly
> natural for me to critique your post based on the standards you follow
> in most of your post.

As I said above, I can rely on a laymans intuition about continuous
curves, but there is no such intuition to rely on for the second part
of the proof, which hence needs to be more detailed/rigorous.