Problem 08

Problem 08

How many squares should one minimally select from a 4 x 4 grid, if one wants the property that if we remove any two rows and any two columns, there is at least one selected square left?

Solution

With 6 or less this is impossible: by the pigeonhole principle, there are at least two rows with 0 or 1 selected squares each. Removing the other two rows, and removing the two columns containing this one square (or any column if the row is empty), results in no square left.

×
××
××
××

If there is a solution with 7, it should not have two rows or two columns with 0 or 1 selected squares each, otherwise the same trick would end us up with no selected squares. Hence, the selections should be distributed 1-2-2-2 over both rows and columns. With this extra knowledge, one can easily construct an example showing that 7 works, such as the one depicted here on the right.

Remarks

The nice thing about this problem is that is hard by trial and error, but easy if one just tries to prove the nonexistence for 4,5,6,7... and see where things go wrong for the first time, and how a structure where things go wrong should look like. Hence, this problem demonstrates that a formal proof can also help them in practical things like constructions.