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)
Problem
Source: Stars of Mathematics 2013 - Juniors - Problem 4
Tags: combinatorics proposed, combinatorics
29.10.2013 14:36
i) One element is called "special for a row/column" if it is the only element of that row/column. Thus, any element is special for at most 1 row and 1 column. With 2n row and column in total, thus, we need n elements at least. $m(n) = n$, and each meagre set is a set of cells, each cell lies on a different row and column, there are $n!$ meagre sets. ii) Consider a fat set, each element is special for at least one row or column and each row or column has at most 1 special element. Consider a set of at least $2n-1$ elements. Thus, there are n elements that are special for n rows or n elements that are good for n columns. With n elements specialfor n rows or n columns, we find out that the above n rows/ n columns have no other elements and thus, the set has at most n elements (a contradiction). Thus, $M(n) \leq 2n-2$. We prove that there is a fat set with $2n-2$ elements: There has to be $n-1$ elements special for $n-1$ rows, and $n-1$ elements special for $n-1$ columns. Any fat sets has the form of a full row and a full column eliminating their intersection. Thus, there are $n^2$ fat sets.
29.10.2013 15:19
Except for $n=2$, when there are only $2$ fat sets (not $4$).