Solution
Maker and Breaker on a Grid
Show the problem again
Maker and Breaker alternately claim an unclaimed cell of a 4×4 grid, Maker moving first. Maker wins if at some point Maker owns all four cells of some row or some column. Breaker wins if the grid fills up without that happening. (Diagonals do not count.) Who wins with optimal play? Answer 'Maker' or 'Breaker'.
Worked solution
Breaker wins by a pairing strategy. Label cells by (row, column) from 1 to 4 and pair them as follows: (1,1)-(1,2), (2,1)-(2,2), (3,3)-(3,4), (4,3)-(4,4), (3,1)-(4,1), (3,2)-(4,2), (1,3)-(2,3), (1,4)-(2,4). These eight pairs are disjoint and cover all 16 cells, and each of the eight lines contains a whole pair: rows 1 to 4 contain the first four pairs, and columns 1 to 4 contain the last four. Whenever Maker claims a cell, Breaker claims its partner. Then every row and every column contains a cell owned by Breaker, so Maker never completes a line. An exhaustive search of the game tree confirms that Breaker wins.
Source: Maker-Breaker positional games (Erdos and Selfridge); the pairing strategy is standard. Statement written for AxiomIQ.