There is a table with rows and 18 columns. Each of its cells contains a 0 or a 1. The table satisfies the following properties:
(i) Every two rows are different.
(ii) Each row contains exactly 6 cells that contain 1.
(iii) 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 ?
Solution
The greatest possible value of is .
We can identify each row as a 6-element subset of , so that the elements correspond to the numbers of columns which contain 1. Then we need to maximize the number of such subsets so that no three of them form a partition of , since forming a partition is the only case for their complement to have an empty intersection.
First we construct an example of 12376 subsets. We simply need to consider all 6-element subsets of . Since in any three subsets, there are elements, there must be an element belonging to at least two of the subsets by the pigeonhole principle. Therefore, the condition is satisfied. In this example, there are subsets.
Next we show that . Suppose are the 6-element subsets corresponding to the rows, and let be the unused 6-element subsets, where . Let be the number of pairs such that and are disjoint.
On the one hand, for each , the 12 elements not in can form unordered pairs of 6-element subsets. At least one subset in each pair must be a subset since no three of the 's can form a partition of . As each disjoint with belongs to exactly one such pair, this gives at least pairs containing . Thus, .
On the other hand, for each , there are only subsets of which are disjoint with . Hence, .
Combining these, we obtain , i.e. . This completes the proof.