Question

11 студентов написали тест.Учитель проверил работы и заметил, что для любых двух вопросов теста, найдутся хотя бы 6 студентов, каждый из которых ответил правильно ровно на один из этих двух вопросов. Докажите, что в тексте было не более 12 вопросов.

Answer 1

Представим себе двудольный граф: слева вершины, обозначающие студентов, справа — вопросы. Если студент ответил на вопрос, то между этим студентом и этим вопросом проведем ребро.

Рассмотрим первую пару вопросов ($a_{1},a_{2}$). Для них по условию найдется хотя бы 6 студентов, каждый из которых ответил правильно ровно на один из этих двух вопросов. Пусть это множество из хотя бы 6 студентов называется $A_{1}$. Тогда остальных студентов (тех, что не удовлетворяют описанному требованию) не больше 5 — это множество $B_{1}$. Рассмотрим следующую пару вопросов ($a_{3},a_{4}$,попарно отличных от предыдущих). Тогда $A_{2}$ имеет с $A_{1}$ хотя бы одно пересечение. Поэтому для пары $a_{2},a_{3}$ будет хотя бы одно ребро из множества $B_{1}$. Рассматривая далее пары $a_{5},a_{6}$ и соответственно пары $a_{2},a_{4}$ "берем" еще один элемент из $B_{1}$. Так можно продолжать до тех пор, пока все элементы из $B_{1}$, коих не больше пяти, не будут взяты. То есть всего можно добавить 2*5=10 вопросов дополнительно к $a_{1}, a_{2}$. То есть всего не более 12.

Примечание: множество $A_{1}$ делится на два множества, из каждого идут ребра к вопросам $a_{1},a_{2}$, но из каждого к ровно одному. Для того, чтобы мы могли всегда изымать элементы из $B_{1}$ надо всего лишь без ограничения общности потребовать, чтобы ребро из $a_{2}$ шло в наибольшее из множеств, на которое делится $A_{1}$. Тогда наименьшее из этих множеств деления не превосходит 5.