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!

  • $\begingroup$ Do you know the answer to the question? $\endgroup$ – Bubbler Dec 6 '20 at 4:45
  • $\begingroup$ 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? $\endgroup$ – Daniel Mathias Dec 6 '20 at 4:53
  • 1
    $\begingroup$ 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 :/ $\endgroup$ – Bubbler Dec 6 '20 at 4:59
  • $\begingroup$ @Bubbler The organiser gave us the solutions after the competition. $\endgroup$ – Culver Kwan Dec 6 '20 at 7:59

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


...instead of a binary array.

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\}$.

Thus the answer is

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

  • $\begingroup$ Although this is not the official solution, it is a nice one! $\endgroup$ – Culver Kwan Dec 6 '20 at 8:42
  • $\begingroup$ This is precisely the answer I had in mind with less than a minute's thought. It is a trivial lower bound. Proving that it is also an upper bound would have required a bit more effort, and it was way too late for that. $\endgroup$ – Daniel Mathias Dec 6 '20 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.