Олимпиада "Физтех", комбинаторика

[Nikita432472]

Тест по английскому языку сдавали 10 школьников. Известно,
что любые пять школьников ответили вместе на все вопросы, а любые четыре школьника отве-
тили вместе не на все вопросы. При каком наименьшем количестве вопросов теста такое могло
случиться?

[iou]

Пусть $A = \{a_1, ~\cdots, ~ a_n \} ~ -$ множество вопросов. $S_i \subset A , ~ 1 \le i \le 10 ~ -$ подмножества, содержащие те вопросы, на которые ответили соответствующие школьники.
Утверждение.

$$|A| = \binom{10}{4}.$$

Доказательство. Обозначим $S_{i_1 i_2 \cdots i_k} = S_{i_1} \cup \cdots \cup S_{i_k}.$ Поскольку для любых номеров $i_1, ~i_2, ~i_3, ~i_4$ есть включение $S_{i_1 i_2 i_3 i_4} \subsetneq A$, а также для любого номера $i_5$, отличного от предыдущих четырех, имеем $S_{i_1 i_2 i_3 i_4 i_5} = A,$ следовательно существует хотя бы один такой $a_s \in A,$ который не содержится $S_l,$ где $l \in \{i_1, ~\cdots, ~i_4\},$ но $a_s \in S_{i_5}.$ Таким образом, можно каждому множеству (которое суть объединение четырех подмножеств) сопоставить один элемент множества $A.$ Заметим, что это инъекция. Действительно, если мы двум множествам $S_{i_1 i_2 i_3 i_4}$ и $S_{j_1 j_2 j_3 j_4}$ сопоставим один и тот же вопрос $a_r,$ то к первому множеству добавим $S_{j_1}$, но при этом не получим $A,$ поскольку там нет $a_r.$

Мы получили инъекцию $S \hookrightarrow A,$ где множество $S$ состоит из подмножеств вида $S_{i_1 i_2 i_3 i_4},$ то есть $|S|=\binom{10}{4}$ (очевидно, что все такие подмножества различны), тогда при $|A|=\binom{10}{4}$ получаем биекцию.

[DeBill]

Т.е., если не пугать детей страшными словами, это же можно сказать и так:
поставим в соответствие каждой четверке школьников вопрос (какой-нибудь), который все люди из четверки не знают.
Разным четверкам соответствуют разные вопросы (иначе и пятеро не будут его знать). Потому, вопросов не менее $C^4_{10}$.
Ну, и пример с таким количеством строится, как и указано: назначим каждой четверке какой-то вопрос, и по этим назначениям определим для каждого, что он знает, а что - не знает....

[Nikita432472]

Отлично!