|
|
Re: Hex Win Proof?
Posted:
Mar 22, 2004 4:59 AM
|
|
w.taylor@math.canterbury.ac.nz (Bill Taylor) writes:
> 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.
The easy part is proving that both players can't win at the same time:
Assume that there is a white path connecting top and bottom and a
black path connecting left to right. These must intersect, but on a
hex board two paths can only intersect if they share a hex. Since
this can't be both black and white, one of the paths must be broken.
This contradicts the assumption.
It is a bit harder proving that one side must win. But it isn't too
bad.
We consider connected areas of one colour. It is easy to see that an
area that does not connect to the edge of the board must be completely
sorrounded by the other colour, so it makes no difference if we
replace these by the sorrounding colour (as it neither blocks nor
connects anything). We are now left only with areas that connect to
the edge of the board. Those that connect to only one edge of the
board (corners are counted as two edges) can also be replaced with the
other colour, so we are left with areas that connect two or more edges
of the board. If an area is at a corner and only touches the two
sides that share that corner, it can also be replaced by the opposite
colour. This can be repeated until the only remaining areas touch two
opposite edges (and possibly more). If there is only one area left,
that colour obviously wins. If there are more than one area left, the
pair of opposite edges they connect must be the same (otherwise the
areas would cross, which we showed above isn't possible). So one pair
of opposite edges are connected by both colours, and one of them must
be the colour that has this as a goal.
QED.
Torben
|
|
