
Re: Hex Win Proof?
Posted:
Mar 24, 2004 7:01 AM


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

