```Date: Mar 20, 2004 2:33 AM
Author: Tim Smith
Subject: Re: Hex Win Proof?

In article <716e06f5.0403181938.72a82f90@posting.google.com>, Bill Taylorwrote:> 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 following has a bunch of cases, but I think the intelligent layman canfollow them.Let's assume Red has top/bottom, and Blue has the sides.  We want to showthat if Blue does not have a win when the board is full, the Red must haveone.There must be at least one Red hex on the top, and at least one on thebottom, or else Blue would have a win along the top or bottom.  Pick a Redhex on top, U, and a Red hex on the bottom, D, and consider any path betweenthem.  Go along that path from bottom to top.If Red doesn't have a win, that path must run into a Blue hex.  Let S be theset of all Blue hexes connected to that Blue hex.  Call the Red hex that raninto S A.  As you continue along the path, you must eventually reach a Redhex that is not surrounded by S.  Call that Red hex B.If S does not touch any edge, then there is an all Red path from A to B.Just go around the edge of S in either direction from A to B.  If S touchesone edge, there is still a Red path from A to B.Thus, we cannot reroute around S only if S connects to two or more edges.Let's consider the cases:1. S connects to the top and bottom.  Then the Red hexes adjacent to atleast one of its sides form a win for Red, unless S connects is connected toopposite corners, in which case S would be a win for Blue.2. S connects to left and right.  S is a win for Blue.3. S connects to the bottom and a side.  WLOG we can assume S is connectedto the left side.  If the connection to the bottom is to the left of D, thenthere is a path from A to B around the boundary of S.  If the connection tothe bottom is to the right of D, then there is a connection from B to thebottom along the boundary of S (unless S connects to the bottom at thecorner, in which case S is a win for Blue).4. S connects to the top and a side.  Similar to case #3.  If the topconnection is on the same side of U as the side connection, then there is aconnection from A to B.  Otherwise, there is a connection from A to the top.In all these cases, we are able to reroute the path such that it is stillconnected to the top and the bottom, but avoids S.  Hence, if Blue does nothave a win, there is a win for Red, and this procedure will even find such awin.-- --Tim Smith
```