Problem 1530

The answer is $\binom{11}{4} = 330$; here and later on $\binom{n}{k}$ denotes a binomial coefficient.

Here is an example with $n=330$. Form the $\binom{11}{4} = 330$ (unordered) quadruples $i, j, k, l$ with elements from $\{1, 2, \dots, 11\}$. To every such quadruple assign a row of length $12$ in which there are $1$'s exactly at positions $i, j, k, l$; the remaining entries are $0$'s. The obtained $330$ rows can be arranged to form a $330 \times 12$ table, which satisfies conditions (a) – (c) by construction. (For condition (c) note that column $12$ contains only zeros.)

Let us show that $n \le 330$ for each table $T$ with the given properties. For each row $F$ consider the $4$ columns that intersect it at $1$'s. We say that they form an *admissible* quadruple $Q$. It is uniquely determined by $F$ in view of condition (b). In addition different rows generate different admissible quadruples by condition (a). Hence there is a bijection between the rows and the admissible quadruples; in particular there are exactly $n$ admissible quadruples.

Let $Q$ be an admissible quadruple. Consider all partitions of its complementary $8$ columns into $2$ quadruples $Q_1$ and $Q_2$. Since $4$ columns out of $8$ can be chosen in $\binom{8}{4}$ ways, there are $\frac{1}{2} \binom{8}{4}$ such partitions. Clearly the quadruples $Q_1$ and $Q_2$ are different for different partitions. Observe also that in each partition at least one of $Q_1$ and $Q_2$ is non-admissible. Indeed if $Q_1$ and $Q_2$ are admissible then no column intersects their respective rows at $3$ zeros, which contradicts condition (c). Hence the specified $\frac{1}{2} \binom{8}{4}$ partitions generate at least $\frac{1}{2} \binom{8}{4}$ non-admissible quadruples associated to the initial admissible quadruple $Q$. Because there are $n$ admissible quadruples, this argument yields a list of $l \ge \frac{1}{2} \binom{8}{4} n$ non-admissible quadruples. We are about to see that the repetitions in it are not too numerous.

Each non-admissible quadruple $Q'$ on the list occurs in it as many times as there are admissible quadruples $Q$ that generate $Q'$ in the way explained above. Every such $Q$ occupies $4$ columns among the $8$ complementary columns of $Q'$, which gives at most $\binom{8}{4}$ possibilities for $Q$. Consequently every non-admissible quadruple on the list occurs at most $\binom{8}{4}$ times in it.

Given the length $l \ge \frac{1}{2} \binom{8}{4} n$ of the list and the maximum number $\binom{8}{4}$ of repetitions of an item, we find at least $\frac{n}{2}$ different non-admissible quadruples in $T$. The total number of quadruples of columns is $\binom{12}{4} = 495$. Exactly $n$ of them are admissible and $495-n$ are non-admissible. Hence $495-n \ge \frac{n}{2}$, which yields the desired $n \le 330$.