Competition problem — Combinatorics

Library / /18 of 50

Combinatorics Difficulty 5.2 AIME, harder Prove it Belarus

$N$ cells are marked on an $n \times n$ table so that at least one marked cell is among any four cells of the table which form the figure $\Box\Box$ (the figure may be rotated). Find the smallest possible value of $N$ .

Solution

Answer: $(n - 3)([n/3] + 1) + 1$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.