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.

Danny Purvis