Difference between revisions of "Draw"
From HexWiki
m (added cat. theory) |
(another equivalence) |
||
| Line 3: | Line 3: | ||
There are various ways of proving this, for example: | There are various ways of proving this, for example: | ||
| − | * 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. |
* An [http://www.cs.ualberta.ca/~javhar/hex/hex-yproof.html elegant proof] using the [[Y|game of Y]]. | * An [http://www.cs.ualberta.ca/~javhar/hex/hex-yproof.html elegant proof] using the [[Y|game of Y]]. | ||
* Another [[Y#No draws|proof]] using the game of Y. | * Another [[Y#No draws|proof]] using the game of Y. | ||
| − | In fact, 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 fact, David Gale showed 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]]. | ||
[[category:Theory]] | [[category:Theory]] | ||
Revision as of 17:33, 22 March 2009
One of the beautiful properties of Hex is that the game can never end in a draw, i.e., there is always a winner.
There are various ways of proving this, for example:
- 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.
In fact, David Gale showed 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.
