Combinatorics - Chapter 2 Flashcards
perfect information
Once you start the game you know everything. (what the board looks like, winning conditions, all other players options/cards)
The winning set is…
the same for player 1 and player 2
player 1
the 1st player
player 2
the 2nd player
player 1 in the Maker-Breaker Game
maker
player 2 in the Maker-Breaker Game
breaker
Player 1 in the Breaker-Maker Game
breaker
Player 2 in the Breaker-Maker Game
maker
Colouring in a positional game
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.
Winning Strategy =>
Drawing Strategy
Drawing Strategy does not imply
winning strategy
A strong game G is a player 2 win…
is impossible.
in a maker-breaker game the goal of player 2 (breaker is)….
to STOP player 1 winning (not to claim the winning sets himself)
What does Erdos-Selfridge Theorem provide?
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)
winning strategy for breaker =>
drawing strategy for player 2
If F is n uniform what does Erdos-Selfidge say
|F|<2ⁿ⁻¹ is a sufficient condition for breaker to win maker-breaker
The bounds of erdos-selfidge are…
best possible
difficulty of pairing stratgies.
finding x₁,x₂,..,xₖ,y₁,y₂,…,yₖ with the desired property is difficult and sometimes impossible.
How to find a pairing strategy
Find a pair of points in each winning set (has to be distinct for each winning set).
if n≤4 in the unrestricted mxm n-in-a-row maker breaker game
then makers win
if n≥8 in the unrestricted mxm n-in-a-row maker breaker game
then breakers win
if n=5,6,7 in the unrestricted mxm n-in-a-row maker breaker game
then we don’t know who wins
|F|
number of winning sets
preparation for pairing strategy
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
property that has to hold for x₁,x₂,..,xₖ,y₁,y₂,…,yₖ pairing strategy
in each winning set there exists a pair xᵢ,yᵢ
why does pairing strategy work
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
What is the end result of a pairing stratgey for player 2
strong game/maker breaker
A player 2 draw in the strong game
A breaker win in the maker breaker game
Cases when playing a pairing strategy for player 2
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.
is there a pairing strategy for the 4x4 maker-breaker tic-tac-toe
no (unless you make a move first)
You can take a pairing strategy after….
the first move (the first move will destroy some winning sets, take cases and work with symmetry)
pairing strategy for player 1
claim an arbitrary element first then follow a pairing strategy.
How to show there is no pairing strategy
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.
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)
- 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)
If asked to give an explicit pairing strategy
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.
Even if you have a strategy take the case into account where the player…
doesn’t follow the strategy
what type of game is the connectivity game
breaker-maker
