Quiz Three

Question 0

Zermelo’s Theorem (2)

Answer 0

Proof: by the Game Tree Lemma, T has finitely many nodes. We can label each terminal node * ( I wins) or +(II wins) by using axiom 3 of TFGWT. We can label up the game tree using axioms 1 and 2 of TFGWT.
There are only finitely many steps to complete backwards induction; thanks to the Game Tree Lemma. Thus, whoever gets their symbo assigns to the T top node has a WS in Game G.

Question 1

Zermelo’s Theorem (1)

Answer 1

Goal: if G is a TFGWT then player I or Player II has a winning strategy

Question 2

Game Tree Lemma (1)

Answer 2

Goal: prove for every TFGWT, G, G’s games tree, T, has finitely many nodes

Question 3

Game Tree Lemma (2)

Answer 3

Proof: as G is a TFGWT we know axiom 4 is true -> every play of G ends after finitely many moves.
We know plays of G correspond to branches in G’s game T. So every branch of T is finite in length.
We also know axiom5 is true -> there are always only finitely many options for a player’s next move. These options correspond to a fork in T, so each fork is finite in width.
As T satisfies I and II of Konig’s Infinity Lemma, III fails. So T has finitely many nodes.

Question 4

Hex theorem

Answer 4

Goal: for each n, Red has a WS in Hex (n).
Lemma A: Hex is a TFGWT
Lemma B: it is impossible for Black to have a WS in Hex (n).
By Zermelo’s Theorem, as hex is a TFGWT, either Red or Black has a WS in hex. It’s not black by Lemma B so it must be red.

Question 5

Lemma A:

Answer 5

Goal -> prove that Hex is a TFGWT

1) there are two plates that move alternately
2) there are no randomizing mechanisms
4) every play ends after finitely many moves: n squared is the longest game possible
5) at each point of a play, there are only finitely many next legal options. At most n squared options.

Question 6

Proof of Lemma A part 3

Answer 6

There is only one winner at the end of each play. Imagine red chain represents open water and the black chain represents a concrete dam. Either the water can flow from UL to LR or the concrete dam will connect UR to LL, blocking the water. Thus, re chains cannot overlap, only one player can have a winning chain.

Question 7

Statement of Zarmelo’s theory

Answer 7

Every TFGWT, player I or player II has a winning strategy

Question 8

Statement of game tree Lemma

Answer 8

For each TFGWT G G’s game tree T has finitely many nodes.