Ответы на вопрос:
Представим себе двудольный граф: слева вершины, обозначающие студентов, справа — во Если студент ответил на во то между этим студентом и этим во проведем ребро.
Рассмотрим первую пару во Для них по условию найдется хотя бы 6 студентов, каждый из которых ответил правильно ровно на один из этих двух во Пусть это множество из хотя бы 6 студентов называется . Тогда остальных студентов (тех, что не удовлетворяют описанному требованию) не больше 5 — это множество . Рассмотрим следующую пару во попарно отличных от предыдущих). Тогда имеет с хотя бы одно пересечение. Поэтому для пары будет хотя бы одно ребро из множества . Рассматривая далее пары и соответственно пары "берем" еще один элемент из . Так можно продолжать до тех пор, пока все элементы из , коих не больше пяти, не будут взяты. То есть всего можно добавить 2*5=10 во дополнительно к . То есть всего не более 12.
Примечание: множество делится на два множества, из каждого идут ребра к во но из каждого к ровно одному. Для того, чтобы мы могли всегда изымать элементы из надо всего лишь без ограничения общности потребовать, чтобы ребро из шло в наибольшее из множеств, на которое делится . Тогда наименьшее из этих множеств деления не превосходит 5.
Популярно: Математика
-
анабель12503.07.2022 14:24
-
Khedi199921.11.2021 08:34
-
11SOS1119.03.2020 20:12
-
malenkayakreyz17.06.2020 00:39
-
rimmabuketova13.04.2021 14:08
-
Angela868901.10.2021 07:33
-
elyaivanova17.08.2021 01:42
-
Космос198611.10.2021 17:52
-
Nicner12030.03.2021 21:59
-
katerinaderiiu22.08.2021 13:37