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

Ответы

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

Рассмотрим первую пару во Для них по условию найдется хотя бы 6 студентов, каждый из которых ответил правильно ровно на один из этих двух во Пусть это множество из хотя бы 6 студентов называется $A_{1}$ . Тогда остальных студентов (тех, что не удовлетворяют описанному требованию) не больше 5 — это множество $B_{1}$ . Рассмотрим следующую пару во попарно отличных от предыдущих). Тогда $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}$ делится на два множества, из каждого идут ребра к во но из каждого к ровно одному. Для того, чтобы мы могли всегда изымать элементы из $B_{1}$ надо всего лишь без ограничения общности потребовать, чтобы ребро из $a_{2}$ шло в наибольшее из множеств, на которое делится $A_{1}$ . Тогда наименьшее из этих множеств деления не превосходит 5.