
Re: Hex Win Proof?
Posted:
Mar 24, 2004 10:46 AM


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.

