Date: Mar 20, 2004 3:10 AM Author: Glenn C. Rhoads Subject: Re: Hex Win Proof?

w.taylor@math.canterbury.ac.nz (Bill Taylor) wrote in message news:<716e06f5.0403181938.72a82f90@posting.google.com>...

>

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

Here's a pretty proof involving a closely related game called Y.

(Don't hesitate about the length of this post; it consists mostly

of descriptions of Y, the relation to Hex, and the definition

of "Y-reduction". The final proof is very short.)

A Y board consists of a triangular configuration of hexagons. Play is

the same as Hex except that the goal is to build a chain that connects

all three sides (as in Hex, corner hexes belong to both sides).

Y is a generalization of Hex as illustrated in the following ascii diagram.

(view in a fixed font)

_

_/* _/*\_/

_/*\_/* _/ \_/*\_/

_/ \_/ \_/* _/ \_/ \_/ \_/

/ \_/ \_/ \_/ \_/ \_/ \_/ \_/

\_/ \_/ \_/+ \_/ \_/+\_/

\_/+\_/+ \_/+\_/

\_/+ \_/

* are pieces of one player and + are pieces of the other player.

Playing Y from the above legal position is equivalent to playing

Hex in the unoccupied hexes of this position because a chains wins

for Y if and only if the chain restricted to originally unoccupied

hexes wins for Hex (in the Hex version, player * is connecting the

southwest border up to the northeast). Thus, to prove a completely

filled-in Hex board has a winning chain for one of the two players,

it suffices to prove that a filled-in Y board has a winning chain

for one of the two players.

The proof makes use of "Y-reduction."

Y-reduction: From a completely filled-in order n Y-board,construct

a completely filled-in order n-1 Y-board as follows. For each

triangle of three mutually adjacent hexes oriented the same way as

the board, replace it with a single hexagon whose piece color is

that of the majority of the colors in the triangle.

Ex.

_

_/4\

_/3\1/ _/3 _/2\1/3\ _/2\1/

/1\1/2\2/ /1\1/2 \1/1\2/2\ \1/1\2/

\2/1\3/ \2/1 \3/1\ \3/

\4/

The triangle of hexes with coordinates

x x+1 x

y y y+1

on the order-n board corresponds to the hexagon

x

y on the order n-1 board

Lemma: If a player has a winning chain on the reduced board, then

that player also has a winning chain on the original board.

It's easy to verify (but ugly to write up rigorously) that if a player

has a winning chain on the reduced board, then he also has a winning

chain through the corresponding triangles on the original board.

[note: the converse of the lemma is also true but we don't need it.]

Thm. One of the player's has a winning chain on a completely filled-in

Y board.

Proof:

From any completely filled-in Y board, perform a sequence of

Y-reductions to reduce the board to a filled-in order 1 board.

The filled-in order 1 board obviously has a winning chain and

hence by the lemma, each Y board in the sequence has a winning

chain.

I wish I could take credit for this proof but it is due to

Ea Ea (his former name was Craige Schensted).