|
|
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.
|
|
