Combinatorics - Chapter 2

Question 1

perfect information

Answer 1

Once you start the game you know everything. (what the board looks like, winning conditions, all other players options/cards)

Question 2

The winning set is…

Answer 2

the same for player 1 and player 2

Question 3

player 1

Answer 3

the 1st player

Question 4

player 2

Answer 4

the 2nd player

Question 5

player 1 in the Maker-Breaker Game

Answer 5

maker

Question 6

player 2 in the Maker-Breaker Game

Answer 6

breaker

Question 7

Player 1 in the Breaker-Maker Game

Answer 7

breaker

Question 8

Player 2 in the Breaker-Maker Game

Answer 8

maker

Question 9

Colouring in a positional game

Answer 9

each time a player claims an element they colour it with their colours. So to claim all elements in a winning set corresponds to a monochromatic A.

Question 10

Winning Strategy =>

Answer 10

Drawing Strategy

Question 11

Drawing Strategy does not imply

Answer 11

winning strategy

Question 12

A strong game G is a player 2 win…

Answer 12

is impossible.

Question 13

in a maker-breaker game the goal of player 2 (breaker is)….

Answer 13

to STOP player 1 winning (not to claim the winning sets himself)

Question 14

What does Erdos-Selfridge Theorem provide?

Answer 14

a sufficient condition for breaker to win a maker breaker game (and thus by proposition 2.4 a drawing strategy for player 2 in the strong game)

Question 15

winning strategy for breaker =>

Answer 15

drawing strategy for player 2

Question 16

If F is n uniform what does Erdos-Selfidge say

Answer 16

|F|<2ⁿ⁻¹ is a sufficient condition for breaker to win maker-breaker

Question 17

The bounds of erdos-selfidge are…

Answer 17

best possible

Question 18

difficulty of pairing stratgies.

Answer 18

finding x₁,x₂,..,xₖ,y₁,y₂,…,yₖ with the desired property is difficult and sometimes impossible.

Question 19

How to find a pairing strategy

Answer 19

Find a pair of points in each winning set (has to be distinct for each winning set).

Question 20

if n≤4 in the unrestricted mxm n-in-a-row maker breaker game

Answer 20

then makers win

Question 21

if n≥8 in the unrestricted mxm n-in-a-row maker breaker game

Answer 21

then breakers win

Question 22

if n=5,6,7 in the unrestricted mxm n-in-a-row maker breaker game

Answer 22

then we don’t know who wins

Question 23

|F|

Answer 23

number of winning sets

Question 24

preparation for pairing strategy

Answer 24

Find distinct elements x₁,x₂,..,xₖ,y₁,y₂,…,yₖ with the property that each winning set A∈F there exits some i∈[k] such that xᵢ,yᵢ∈A

Question 25

property that has to hold for x₁,x₂,..,xₖ,y₁,y₂,…,yₖ pairing strategy

Answer 25

in each winning set there exists a pair xᵢ,yᵢ

Question 26

why does pairing strategy work

Answer 26

Since each A∈F contains some pair {xᵢ,yᵢ} and player 2 claims at least one element from each A∈F player 1 is unable to claim all the elements of any A∈F so player 1 cannot win

Question 27

What is the end result of a pairing stratgey for player 2

strong game/maker breaker

Answer 27

A player 2 draw in the strong game

A breaker win in the maker breaker game

Question 28

Cases when playing a pairing strategy for player 2

Answer 28

Suppose that player 1 claims an element z and it is now player 2s turn. If z∈{xᵢ,yᵢ} for some i and {xᵢ,yᵢ}\z is unclaimed then player 2 claims the element {xᵢ,yᵢ}\z. Otherwise player 2 claims an arbitrary element.

Question 29

is there a pairing strategy for the 4x4 maker-breaker tic-tac-toe

Answer 29

no (unless you make a move first)

Question 30

You can take a pairing strategy after….

Answer 30

the first move (the first move will destroy some winning sets, take cases and work with symmetry)

Question 31

pairing strategy for player 1

Answer 31

claim an arbitrary element first then follow a pairing strategy.

Question 32

How to show there is no pairing strategy

Answer 32

Assume for a contradiction there is.
Count the number of winning sets, then given each winning set contains a unique pair double this number, the size of the board must be greater than or equal to this..
Show that |X| is smaller than this, a contradiction.

Question 33

For tic-tac-toe if you have a pairing strategy for nxn how do you get a pairing strategy for (n+m)x(n+m)

Answer 33

• Define the grid X of the nxn as {aᵢⱼ} for i,j=1 to n.
• Similarily define to grid of the (n+m)x(n+m) but up to n+m
• Count the number of new winning sets (new columns, rows and changed backwards diagonal). Define these precisely e.g. for a new row the new winning set is {aᵣₒᵥᵥ,ᵢ : i∈[n+m]}
• define an xᵢ and yᵢ in each of the new winning sets (a picture may help)

Question 34

If asked to give an explicit pairing strategy

Answer 34

Give the pairing strategy AND show that each winning set contains a pair AND state that clearly no board element is in more than one pair.

Question 35

Even if you have a strategy take the case into account where the player…

Answer 35

doesn’t follow the strategy

Question 36

what type of game is the connectivity game

Answer 36

breaker-maker