```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 PurvisSo, Red wins if and only if a dam is present, and Blue wins if andonly if a dam is not present.
```