Difference between revisions of "Draw"
(Expanded the stub) |
|||
| Line 1: | Line 1: | ||
| − | One of the beautiful properties of Hex is that the game can never end in a '''draw''', i.e., there is always a winner. | + | One of the beautiful properties of Hex is that the game can never end in a '''draw''', i.e., there is always a winner. This makes Hex a more decisive game than, say, chess, where 55-70 percent of games between highly-ranked players end in a draw. The no-draw property of Hex is also sometimes known as the "Hex theorem". |
| − | There are various ways of proving | + | == Elementary proofs of the no-draw property == |
| + | |||
| + | There are various ways of proving the no-draw property of Hex, but the following proof is perhaps the simplest to state: Given a Hex board that has been completely filled with stones, let ''T'' be the connected component of the top edge, i.e., the set of all red stones that are [[connection|connected]] to the top. If ''T'' touches the bottom edge, then the position is winning for Red. Otherwise, the blue stones along the boundary of ''T'' form a [[chain]] connecting the left and right edges, so the position is winning for Blue. | ||
| + | |||
| + | Various other elementary proofs have been given, including the following: | ||
* A [http://www.cs.ualberta.ca/~javhar/hex/hex-galeproof.html proof] by [[David Gale]] that used the fact that exactly three hexes meet at every vertex. | * A [http://www.cs.ualberta.ca/~javhar/hex/hex-galeproof.html proof] by [[David Gale]] that used the fact that exactly three hexes meet at every vertex. | ||
| Line 7: | Line 11: | ||
* Another [[Y#No draws|proof]] using the game of Y. | * Another [[Y#No draws|proof]] using the game of Y. | ||
| − | + | == Proofs by reductions to other theorems == | |
| + | |||
| + | The literature contains various results stating that the Hex theorem is equivalent to other known theorems. The best-known of these is a proof by [[David Gale]] that the no-draw property is equivalent to the 2-dimensional case of [http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem Brouwer's fixed point theorem] (a non-trivial theorem from topology saying that any continuous map from the unit square into itself must have a fixed point). | ||
| + | |||
| + | In 2006, [[Yasuhito Tanaka]] proved another equivalence involving Hex. The no-draw property is equivalent to the [[arrow impossibility theorem]]. | ||
| + | |||
| + | === Criticism === | ||
| + | |||
| + | While statements of the form "The Hex theorem is equivalent to another famous theorem" sound exciting, they must be taken with a grain of salt, because in mathematics, all true statements are equivalent to each other. It is therefore not particularly meaningful to say that the Hex theorem is equivalent to some other theorem — it is in fact equivalent to ''every'' other theorem. | ||
| − | + | A more meaningful way to make sense of the claimed equivalence of two theorems is to consider a weaker logic in which neither theorem is derivable, but their equivalence is still derivable. This approach is known as [https://en.wikipedia.org/wiki/Reverse_mathematics reverse mathematics]. An example of such a weak logic is RCA₀, a certain fragment of second-order arithmetic. Unfortunately, it appears that the Hex theorem is derivable in RCA₀, whereas Brouwer's fixed point theorem is not. Therefore, relative to RCA₀, it appears that the Hex theorem and Brouwer's fixed point theorem are not equivalent. | |
[[category:Theory]] | [[category:Theory]] | ||
Revision as of 03:42, 30 May 2023
One of the beautiful properties of Hex is that the game can never end in a draw, i.e., there is always a winner. This makes Hex a more decisive game than, say, chess, where 55-70 percent of games between highly-ranked players end in a draw. The no-draw property of Hex is also sometimes known as the "Hex theorem".
Elementary proofs of the no-draw property
There are various ways of proving the no-draw property of Hex, but the following proof is perhaps the simplest to state: Given a Hex board that has been completely filled with stones, let T be the connected component of the top edge, i.e., the set of all red stones that are connected to the top. If T touches the bottom edge, then the position is winning for Red. Otherwise, the blue stones along the boundary of T form a chain connecting the left and right edges, so the position is winning for Blue.
Various other elementary proofs have been given, including the following:
- A proof by David Gale that used the fact that exactly three hexes meet at every vertex.
- An elegant proof using the game of Y.
- Another proof using the game of Y.
Proofs by reductions to other theorems
The literature contains various results stating that the Hex theorem is equivalent to other known theorems. The best-known of these is a proof by David Gale that the no-draw property is equivalent to the 2-dimensional case of Brouwer's fixed point theorem (a non-trivial theorem from topology saying that any continuous map from the unit square into itself must have a fixed point).
In 2006, Yasuhito Tanaka proved another equivalence involving Hex. The no-draw property is equivalent to the arrow impossibility theorem.
Criticism
While statements of the form "The Hex theorem is equivalent to another famous theorem" sound exciting, they must be taken with a grain of salt, because in mathematics, all true statements are equivalent to each other. It is therefore not particularly meaningful to say that the Hex theorem is equivalent to some other theorem — it is in fact equivalent to every other theorem.
A more meaningful way to make sense of the claimed equivalence of two theorems is to consider a weaker logic in which neither theorem is derivable, but their equivalence is still derivable. This approach is known as reverse mathematics. An example of such a weak logic is RCA₀, a certain fragment of second-order arithmetic. Unfortunately, it appears that the Hex theorem is derivable in RCA₀, whereas Brouwer's fixed point theorem is not. Therefore, relative to RCA₀, it appears that the Hex theorem and Brouwer's fixed point theorem are not equivalent.
