# n rows and 18 columns

I haven't posted for a long long time, so here is an interesting combinatorics problem!

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 𝑛?

This is a question from a 3-hour competition I participated few days ago. More details of the competition will be given later.

P.S. I could not solve it in the 3-hour period. The competition has 4 questions, so try limiting yourself to finish this in 45 minutes!

• Do you know the answer to the question? – Bubbler Dec 6 '20 at 4:45
• Did the competition require some logical argument in support of an answer, or could you simply write a number and get full credit if it is correct? – Daniel Mathias Dec 6 '20 at 4:53
• I have a guess that can be derived in two ways, and I'm pretty sure it's the answer since it is supposed to be computed by hand, but I don't have a proof :/ – Bubbler Dec 6 '20 at 4:59
• @Bubbler The organiser gave us the solutions after the competition. – Culver Kwan Dec 6 '20 at 7:59

The situation gets a lot simpler to reason about if we reformulate it in terms of

sets

In particular,

Consider subsets of $$\{1,2,\cdots, 18\}$$. To each row associate a $$6$$-element subset as follows: if there is a $$1$$ in the $$i$$-th column, put $$i$$ in our subset; otherwise $$i$$ is not in it. Thus we get a collection of $$n$$ subsets of $$\{1,\cdots, 18\}$$.

The first two conditions then say

no two subsets are the same, and every subset has exactly six elements.

The interesting condition is the third one, which translates into

No three of them cover the entire set $$\{1,\cdots, 18\}$$: in other words, if $$A, B, C$$ are three subsets in our collection, their union is a proper subset of $$\{1,\cdots, 18\}$$.

Let's try to figure how of these we can have at max.

Note that three subsets that do cover the entire 18-element set form a neat 6-6-6 partition. How many such partitions are possible? Basic combinatorics says $$\tfrac{18!}{6!^3\times 3!}$$; the $$3!$$ is there to account for the order of the three parts. From each such partitions, only two, at max, can make it to our special collection. But each of these subsets in our collection has been counted in $$\frac{12!}{6!^2\times 2!}$$ of these partitions.

Therefore, the size of the collection can be at most

$$\frac{18!}{6!^3\times 3!}\times 2\div \frac{12!}{6!^2\times 2!}$$. This simplifies to $$\binom{17}{6}$$; I will skip the arithmetic.

Of course, this simply gives a bound: we need to show this bound is achievable. This is easy now:

Simply take all the 6-element subsets of $$\{1,\cdots, 17\}$$.

$$\binom{17}{6}$$, or $$12376$$, in case you care about the actual numeric value.