Maths Olympiad Prep

Library / /85 of 94

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Hong Kong

There is a table with nn 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 nn?

Solution

The greatest possible value of nn is (176)=12376\binom{17}{6} = 12376.
We can identify each row as a 6-element subset of S18={1,2,,18}S_{18} = \{1, 2, \dots, 18\}, 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 S18S_{18}, 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 {1,2,,17}\{1, 2, \dots, 17\}. Since in any three subsets, there are 6×3=186 \times 3 = 18 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 (176)=12376\binom{17}{6} = 12376 subsets.
Next we show that n12376n \le 12376. Suppose S1,S2,,SnS_1, S_2, \dots, S_n are the 6-element subsets corresponding to the rows, and let T1,T2,,TmnT_1, T_2, \dots, T_{m-n} be the unused 6-element subsets, where m=(186)m = \binom{18}{6}. Let NN be the number of pairs (Si,Tj)(S_i, T_j) such that SiS_i and TjT_j are disjoint.
On the one hand, for each SiS_i, the 12 elements not in SiS_i can form 12(126)\frac{1}{2}\binom{12}{6} unordered pairs of 6-element subsets. At least one subset in each pair must be a subset TjT_j since no three of the SkS_k's can form a partition of S18S_{18}. As each TjT_j disjoint with SiS_i belongs to exactly one such pair, this gives at least 12(126)\frac{1}{2}\binom{12}{6} pairs containing SiS_i. Thus, Nn2(126)N \ge \frac{n}{2}\binom{12}{6}.
On the other hand, for each TjT_j, there are only (126)\binom{12}{6} subsets of S18S_{18} which are disjoint with TjT_j. Hence, N(mn)(126)N \le (m-n)\binom{12}{6}.
Combining these, we obtain n2(126)(mn)(126)\frac{n}{2}\binom{12}{6} \le (m-n)\binom{12}{6}, i.e. n2m3=12376n \le \frac{2m}{3} = 12376. This completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.