11 студентов написали тест.Учитель проверил работы и заметил, что для любых двух во теста, найдутся хотя бы 6 студентов, каждый из которых ответил правильно ровно на один из этих двух во Докажите, что в тексте было не более 12 во
Ответы на вопрос:
Представим себе двудольный граф: слева вершины, обозначающие студентов, справа — во Если студент ответил на во то между этим студентом и этим во проведем ребро.
Рассмотрим первую пару во Для них по условию найдется хотя бы 6 студентов, каждый из которых ответил правильно ровно на один из этих двух во Пусть это множество из хотя бы 6 студентов называется . Тогда остальных студентов (тех, что не удовлетворяют описанному требованию) не больше 5 — это множество . Рассмотрим следующую пару во попарно отличных от предыдущих). Тогда имеет с хотя бы одно пересечение. Поэтому для пары будет хотя бы одно ребро из множества . Рассматривая далее пары и соответственно пары "берем" еще один элемент из . Так можно продолжать до тех пор, пока все элементы из , коих не больше пяти, не будут взяты. То есть всего можно добавить 2*5=10 во дополнительно к . То есть всего не более 12.
Примечание: множество делится на два множества, из каждого идут ребра к во но из каждого к ровно одному. Для того, чтобы мы могли всегда изымать элементы из надо всего лишь без ограничения общности потребовать, чтобы ребро из шло в наибольшее из множеств, на которое делится . Тогда наименьшее из этих множеств деления не превосходит 5.
Популярно: Математика
-
LedyKoshka07.02.2023 22:10
-
danielasaske431.12.2020 07:26
-
megamerezhniko10.01.2022 14:29
-
Арина09876508.11.2022 02:40
-
Soulwax24.08.2022 13:48
-
sabinanuray181006.01.2020 19:42
-
верадубовая200714.12.2021 06:34
-
roman1999555521.03.2021 04:06
-
рвовттатс23.08.2022 12:12
-
kotovich929202.09.2022 15:07