home | topics | authors | contact

Minimal play winning strategies.

Author: Garikai Campbell [ profile | email ]
Recall that we define
(n) = min {l | player one has a winning strategy for Hex(n,l)}
and
(n) = min { d | player one can guarantee a win at Hexd(n) },
where Hex(n,l) denotes the game of Hex(n) with the added constraint that player one wins only by constructing a path of length less than or equal to l and Hexd(n) denotes the game of Hex(n) with the added constraint that player one must win by playing at most d counters. We clearly have (n) ≥ (n), and in the case of n=4, we have equality. Indeed, this figure (left) not only shows that (4)=5, but also that:
Theorem 1: (4)=5.

Likewise, the same figure (right) proves that we have:

Theorem 2: 6≤ (5) ≤ 7.

Now consider the following lemma suggested to us by Carl Pomerance [PC1]:

Lemma 3: Player one needs at least 5 counters to complete a winning path on an n x 4 board.
Proof: First observe that if player one is to complete a winning path on an n x 4 board with 4 counters, then every counter placed must be part of the winning path. Now, suppose that player one's first move is in tile [i,j]. [i,j] sits in precisely one 4 x 4 sub-board of the n x 4 board which contains all possible winning paths of length 4 through [i,j]. Let us call this sub-board H. Since (4)=5, player 2 can guarantee that it takes player one at least 5 counters to win Hex(4) on H. But then, by definition of H, this means that player one cannot complete a winning path of length 4 that contains every counter placed. Therefore, player one needs at least 5 counters to complete a winning path on the n x 4 board.

Therefore, we get:

Theorem 4: For all n, (n) ≥ n+n/4.
Proof: Divide the n x n board into n x 4 sub-boards, Hk, where Hk consists of the tiles [i,j], 1≤ i ≤ n, 4(k-1) < j ≤ 4k, 1 ≤ k ≤ n/4 and the (n-4 n/4) x n sub-board H consisting of the tiles [i,j], 1≤ i ≤ n, 4 n/4 < j ≤ n. (See Figure 1 below, for example.)

Now, in order to win Hex(n) , player one must have a winning path across H and across each Hk, 1≤ k≤ n/4. Player one can complete a path across H with (n-4 n/4) counters, but for each k, player one needs at least 5 counters to complete a path across Hk by the lemma above. Therefore, player one needs at least 5 n/4 + (n-4 n/4) = n+n/4 counters to complete a winning path in Hex(n) .

Figure 1. Subdivision of a 10 x 10 Hex board into two 10 x 4 sub-boards and one 10 x 2 sub-board as demanded in the proof above.

Where to go from here?

References

Back to Top
home | topics | authors | contact