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

Показать ответ

Ответ:

Лuзуня

15.10.2020 07:30

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

Рассмотрим первую пару вопросов ( $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.