There is a table with $n$ rows and $18$ columns. Each of its cells contains a $0$ or a $1$. The table satisfies the following properties: Every two rows are different. Each row contains exactly $6$ cells that contain $1$. For every three rows, there exists a column so that the intersection of the column with the three rows (the three cells) all contain $0$. What is the greatest possible value of $n$?
Problem
Source: 2021CHKMO Q1
Tags: combinatorics
jchang0313
06.12.2020 11:29
I had an incomplete proof: First note that 17C6 rows can be achieved, by putting all zeros in the first column, then we have 17C6 ways to "insert" the ones. Then I proved 17C6+1 cannot be achieved: 17C6+1 meant there was at least 1 number in the "most zero row" that has a 1 in it. WLOG delete all the numbers starting with ones, and let the remaining number be $111111000000000000$. Then $000000111111000000$ with $000000000000111111$ could not satisfy the third condition, so the greatest possible is 17C6.
Tintarn
08.12.2020 19:06
$n=\binom{17}{6}$ can be achieved by choosing all rows with a zero in a fixed column (say the first).
On the other hand, we cannot do better: Consider all $\binom{18}{6}$ possible rows and all triples containing three rows such that the 18 ones in these three rows cover all columns exactly once. Of such a triplet, at most two rows can be contained in our table.
Since every row is contained in the same number of triplets, averaging over all triplets shows that at most $\frac{2}{3}$ of all possible rows can be in the table, so $n \le \frac{2}{3} \cdot \binom{18}{6}=\binom{17}{6}$.
JustKeepRunning
11.04.2021 02:16
The answer is $\frac{2}{3}\cdot \binom{18}{6}$. We first show it is optimal, then show that it is achievable. Essentially, notice that the only way for condition $3$ to be violated is if in every column, there is exactly one $1$ in one of the three rows. This is because there are only $3\cdot 6=18$ total $1$'s, so we have to have one $1$ in each column, and if we had more than that, than some column would have all 0s, a contradiction. From the first two conditions, there are clearly a maximum of $\binom{18}{6}$ rows. We now show that we can split these $\binom{18}{6}$ row configurations into triplets such that in each of these triplets, at most $2$ of the configurations can be used. We construct these triplets as follows. First, let the first cell be $1$ in all of these triplets. Then we will have $\binom{17}{5}$ total configurations. In each of these configurations, we have $12$ remaining squares, so choose any $6$ of them be $1$s. This will be our second configuration. Now, there are 6 remaining spots that have not been $1$s in the first or second configurations, and by $1$s in these spots we have a third configuration. I claim that if we do this for each of $\binom{17}{5}$ original configurations, then we will have $\binom{17}{5}$ triplets, of which I can only choose two of the configurations in each triplet. Notice that none of the configurations in these triplets can possibly overlap because in every triplet, the original configuration had the $1$ overlapping with the rest of the beginning configurations, meaning it could not become one of the other two configurations created in any other triplet. Furthermore, none of latter two created configurations can overlap... Will edit this later when I get a chance.