
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

