Stars in a 4x4 table
Source: 1961 All-Soviet Union Olympiad
August 4, 2015
combinatorics
Problem Statement
We are given a table.
a) Place stars in the cells in such a way that the erasing of any two rows and two columns will leave at least one of the stars.
b) Prove that if there are less than stars, you can always find two columns and two rows such that erasing them, no star remains in the table.