Maths Olympiad Prep

Library / /292 of 520

Combinatorics Difficulty 5.3 AIME, harder Find the answer

Four, (50 points) 11 interest classes, several students participate (can participate repeatedly), and each interest class has the same number of students (full, unknown number). It is known that any nine interest classes include all students, while any eight interest classes do not include all students. Find the minimum total number of students.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let the set of students in 11 interest classes be A1A_{1}, A2,,A11A_{2}, \cdots, A_{11}.
By the problem, we know A1=A2==A11=x\left|A_{1}\right|=\left|A_{2}\right|=\cdots=\left|A_{11}\right|=x.
Let T=A1A2A11T=A_{1} \cup A_{2} \cup \cdots \cup A_{11}.
By the problem, we know the union of any nine sets is TT, and the union of any eight sets is a proper subset of TT.

Construct a table, if student aiAja_{i} \in A_{j}, then fill the cell in the ii-th row and jj-th column with 1, otherwise fill it with 0.

By the condition, we know that the union of any eight sets is not TT, i.e., for any eight columns, there must be a row where the intersecting cells are all 0, which we call a "zero row".

Furthermore, by the condition that the union of any nine sets is TT, any two zero rows cannot be the same row.
Thus, we form a one-to-one mapping from every 8 columns to one row.
Therefore, C118T\mathrm{C}_{11}^{8} \leqslant|T|.
On the other hand, each row has 3 zeros, and the columns of zeros in any two rows are not all the same, with a total of C113\mathrm{C}_{11}^{3} ways to fill. And C113=C118\mathrm{C}_{11}^{3}=\mathrm{C}_{11}^{8}, so each row is filled in exactly one way. At this point, the conditions of the problem are exactly satisfied.
In summary, the minimum number of students is C118=165\mathrm{C}_{11}^{8}=165.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.