Предмет: Математика, автор: Juliana0798

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

Ответы

Автор ответа: Guerrino
3

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

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

Похожие вопросы
Предмет: Английский язык, автор: школа891