MathDB

Alice and Bob play, 8x8 table, white red black, minimum n for victory

Source: JBMO Shortlist 2018 C3

July 22, 2019

combinatoricsColoringgame strategyminimumgametable

Problem Statement

The cells of a

8 \times 8

table are initially white. Alice and Bob play a game. First Alice paints

n

of the fields in red. Then Bob chooses

4

rows and

4

columns from the table and paints all fields in them in black. Alice wins if there is at least one red field left. Find the least value of

n

such that Alice can win the game no matter how Bob plays.