Date: Mar 24, 2004 10:46 AM
Author: Danny Purvis
Subject: Re: Hex Win Proof?

On 24 Mar 2004, Danny Purvis wrote:

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

>

>

>Danny Purvis

So, Red wins if and only if a dam is present, and Blue wins if and

only if a dam is not present.