Track / Stage 5 / 96 of 400 #1176 of 2444

Problem 1176

AIME late

Combinatorics Difficulty 5.2 Prove it Belarus — Selection and Training Session · 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$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.