Problem

Source: Stars of Mathematics 2013 - Juniors - Problem 4

Tags: combinatorics proposed, combinatorics



A set $S$ of unit cells of an $n\times n$ array, $n\geq 2$, is said full if each row and each column of the array contain at least one element of $S$, but which has this property no more when any of its elements is removed. A full set having maximum cardinality is said fat, while a full set of minimum cardinality is said meagre. i) Determine the cardinality $m(n)$ of the meagre sets, describe all meagre sets and give their count. ii) Determine the cardinality $M(n)$ of the fat sets, describe all fat sets and give their count. (Dan Schwarz)