In one board game, each player has a unique 4 x 4 grid with squares randomly labeled with each integer from 1 to 16. As the integers 1 to 16 are randomly called, each player puts an "X" in the square containing that integer. The first player with an "X" in all four squares in any row, column or diagonal wins. At most, how many integers must be called to get a winner?
For this problem, they say the answer is supposed to be 13, and I guess that's like 4 + 4 + 4 + 1 (so three row/column/diagonals of "X" 's plus 1), but why's that so?
This is an example of the Pigeonhole Principle at work. Ask yourself this: what is the greatest number of squares you can fill with an "X" and still not win? It's not hard to come up with a configuration with $3$ in each row and column, for a total of $4 \times 3 = 12$. For instance, this works: $$ \begin{array}{c|c|c|c} \times & \phantom{\times} & \times & \times \\ \hline \times & \times & \times & \phantom{\times} \\ \hline \times & \times & \phantom{\times} & \times \\ \hline \phantom{\times} & \times & \times & \times \end{array} $$
Any additional "X" will force a win, so with $12 + 1 = 13$ numbers called, a winner is guaranteed.