Date: Mar 24, 2004 7:01 AM
Author: Danny Purvis
Subject: Re: Hex Win Proof?
On 18 Mar 2004, Bill Taylor wrote:
>It is an old theorem that in Hex, once the board has been completely
>filled in with two colours, there *must* be a winning path for one
>or other of them.
>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.
>Can anyone help out please?
I think a simple proof is available even for the generalized version
of the game played like Hex but with cell size and shape only limited
by the provisos that there still must be four external boundaries
(let's say Blue tries to go from North to South and Red tries to go
from East to West) and that adjoining cells must still touch solidly,
not in a pointlike way.
Any generalized Hex position can be thought of as a collection of
noninteracting "Red components" on a Blue background. A Red
component is a set of mutually adjoining Red cells. There are four
types of Red components. An "island" does not touch any external
boundary. A "wharf" touches either one boundary or two contiguous
boundaries. A "canal wall" touches both the North boundary and the
South boundary and at most one other boundary. A "dam" touches the
East boundary and the West boundary.
Clearly the presence of a dam signals a win for Red (only). By the
definition of generalized Hex, there is no way for Blue to get
through a Red component, and there is no going around a dam since
it touches the East and West boundaries.
Each of the other three component types, however, fail to connect the
East and West boundaries, and each of these component types are
circumnavigated by Blue. Clearly, there is a path of navigable "Blue
space" adhering to each of these component types. Likewise, it is
obvious that any noninteracting collection of these three component
types neither connects the East and West boundaries nor blocks off
the Blue connection from North to South. (We can think of adding
these components one by one, with each addition not changing things.)
So, Red wins if and only if a dam is present.