|
|
 |
Условие
а) Группа людей прошла опрос, состоящий из 20 вопросов, на каждый из которых возможно два ответа. После опроса оказалось, что для любых 10 вопросов и любой комбинации ответов на эти вопросы существует человек, давший именно эти ответы на эти вопросы. Обязательно ли найдутся два человека, у которых ответы ни на один вопрос не совпали?
б) Решите ту же задачу, если на каждый вопрос есть 12 вариантов ответа.
Решение
а) Можно считать, что варианты ответов – "Да" и "Нет".
Пример 1. Пусть в опросниках встречались все комбинации по 9 "Да" и комбинация из 20 "Да". Возьмём любые 10 вопросов и произвольную комбинацию ответов на них. Если среди них все 10 "Да", то так ответил последний человек, иначе подберём ответы на остальные вопросы так, чтобы оказалось ровно 9 "Да". Таким образом, условие выполнено. Если бы у двух из этих человек отличались ответы на все вопросы, то сумма количеств "Да" у них равнялась бы 20, что невозможно.
Пример 2. Пусть в опросниках встречались все комбинации, где число ответов «Да» кратно 3. Ясно, что произвольную комбинацию ответов на 10 вопросов можно дополнить до такой. Двух противоположных наборов ответов не встретится, поскольку 20 не кратно 3.
б) Пронумеруем ответы на каждый вопрос числами от 1 до 12, тогда набор ответов человека – это строка из 20 чисел. Выберем среди отвечавших 11 человек так, чтобы ответ первого начинался на 10 единиц, второго – на 10 двоек и т. д. Покажем, что можно составить строку N, которая на последних 10 местах отличается в каждом месте от любой из данных 11 строк. Рассмотрим какое-нибудь место, например, 17-е. В этих 11 строках на этом месте есть не более 11 различных чисел, поэтому какое-то из чисел от 1 до 12 там не встречается. Именно его и поставим на это место в строку N. По условию, есть человек Ч, чьи ответы полностью совпали с заполненной частью строки N. Рассмотрим его ответы в первой половине строки. На 10 местах встречаются не более 10 различных чисел, поэтому какое-то из чисел k от 1 до 11 там не встречается. Но тогда ответы Ч ни в каком месте не совпали с ответами k-го из выбранных 11 человек.
Ответ
а) Не обязательно. б) Обязательно.
Замечания
1. Пример 2 показывает, что в а) 10 можно заменить на 18. Можно доказать, что при замене на 19 ответ изменится.
2. Баллы: 5 + 6.
