Draw - Revision history

Selinger: Added a reference.

2023-05-30T04:09:31Z

Added a reference.

Selinger: Expanded the stub

2023-05-30T03:42:18Z

Expanded the stub

Roland Illig (Admin) at 20:37, 20 February 2012

2012-02-20T20:37:52Z

Roland Illig (Admin): Reverted edits by Sanders Dowdy (Talk); changed back to last version by Adams Quinn

2012-02-20T20:37:08Z

Reverted edits by Sanders Dowdy (Talk); changed back to last version by Adams Quinn

Roland Illig (Admin): Reverted edits by VictoriaGreenham (Talk); changed back to last version by Halladba

2011-12-18T00:52:00Z

Reverted edits by VictoriaGreenham (Talk); changed back to last version by Halladba

Halladba: another equivalence

2009-03-22T17:33:34Z

another equivalence

Halladba: added cat. theory

2008-01-31T15:10:20Z

added cat. theory

Halladba: referenced to proof on Y page

2007-11-09T17:25:30Z

referenced to proof on Y page

SAS: some corrections and link for Brouwer's Fixed Point Theorem

2006-03-31T14:21:14Z

some corrections and link for Brouwer's Fixed Point Theorem

Reiner Martin at 11:02, 16 February 2005

2005-02-16T11:02:19Z

New page

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 [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-yproof.html elegant proof] using the [[Y|game of Y]].

In fact, the no-draw property is equivalent to Brouwer's fixed point theorem (a non-trivial theorem from topology saying that any continuous map from the unit square onto itself must contain a fixed point).

← Older revision		Revision as of 04:09, 30 May 2023
Line 22:		Line 22:

	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.		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.
		+
		+	== References ==
		+
		+	* David Gale, [http://www.maa.org/programs/maa-awards/writing-awards/the-game-of-hex-and-the-brouwer-fixed-point-theorem The game of Hex and the Brouwer fixed-point theorem]. ''American Mathematical Monthly'' 86(1979), pp. 818–827.

	[[category:Theory]]		[[category:Theory]]

@@ 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 this, for example:
+== Elementary proofs of the no-draw property ==
 * 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.
-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).
+== Proofs by reductions to other theorems ==
-In 2006, [[Yasuhito Tanaka]] proved another equivalence involving Hex. The no-draw property is equivalent to the [[Arrow impossibility 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]]

← Older revision		Revision as of 20:37, 20 February 2012
Line 12:		Line 12:

	[[category:Theory]]		[[category:Theory]]
−	~~[http://customwrittendissertation.com/ dissertation help]~~

← Older revision		Revision as of 20:37, 20 February 2012
Line 12:		Line 12:

	[[category:Theory]]		[[category:Theory]]
		+	[http://customwrittendissertation.com/ dissertation help]

@@ Line 3: / Line 3: @@
 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]].
 * 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).
 [[category:Theory]]

← Older revision	Revision as of 00:52, 18 December 2011
(No difference)

← Older revision		Revision as of 15:10, 31 January 2008
Line 8:		Line 8:

	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, 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).
		+
		+	[[category:Theory]]

← Older revision		Revision as of 14:21, 31 March 2006
Line 6:		Line 6:
	* A [http://www.cs.ualberta.ca/~javhar/hex/hex-yproof.html elegant proof] using the [[Y\|game of Y]].		* A [http://www.cs.ualberta.ca/~javhar/hex/hex-yproof.html elegant proof] using the [[Y\|game of Y]].

−	In fact, the no-draw property is equivalent to Brouwer's fixed point theorem (a non-trivial theorem from topology saying that any continuous map from the unit square ~~onto~~ itself must ~~contain~~ a fixed point).	+	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).