2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Олимпиада "Физтех", комбинаторика
Сообщение05.08.2017, 01:36 


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

 Профиль  
                  
 
 Re: Физтех
Сообщение05.08.2017, 03:11 
Аватара пользователя


04/10/15
271
Пусть $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}$ получаем биекцию.

 Профиль  
                  
 
 Re: Физтех
Сообщение05.08.2017, 03:28 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Физтех
Сообщение06.08.2017, 11:14 


05/08/17
18
Отлично!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group