```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 versionof the game played like Hex but with cell size and shape only limitedby 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 gofrom 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 ofnoninteracting "Red components" on a Blue background.  A Redcomponent is a set of mutually adjoining Red cells.  There are fourtypes of Red components.  An "island" does not touch any externalboundary.  A "wharf" touches either one boundary or two contiguousboundaries.  A "canal wall" touches both the North boundary and theSouth boundary and at most one other boundary.  A "dam" touches theEast boundary and the West boundary.Clearly the presence of a dam signals a win for Red (only).  By thedefinition of generalized Hex, there is no way for Blue to getthrough a Red component, and there is no going around a dam sinceit touches the East and West boundaries.Each of the other three component types, however, fail to connect theEast and West boundaries, and each of these component types arecircumnavigated by Blue.  Clearly, there is a path of navigable "Bluespace" adhering to each of these component types.  Likewise, it isobvious that any noninteracting collection of these three componenttypes neither connects the East and West boundaries nor blocks offthe Blue connection from North to South.  (We can think of addingthese components one by one, with each addition not changing things.)So, Red wins if and only if a dam is present.Danny Purvis
```