В школе 2025 учеников. Каждому нравится ровно 𝑘 из них. При каких 𝑘 можно утверждать, что найдутся двое учеников, которые либо оба друг другу нравятся, либо оба друг другу не…
В школе 2025 учеников. Каждому нравится ровно 𝑘 из них. При каких 𝑘 можно утверждать, что найдутся двое учеников, которые либо оба друг другу нравятся, либо оба друг другу не нравятся?
Чтобы решить эту задачу, мы можем применить принцип Дирихле (или принцип ящиков). Мы рассматриваем 2025 учеников и то, как выставляются симпатии между ними.
Каждому ученику нравится ровно k других учеников. Следовательно, каждый ученик делит свою симпатию на двух групп: тех, кто ему нравится, и тех, кто ему не нравится. Таким образом, это деление можно представить в виде графа, где ученики - это вершины, а симпатии - это рёбра между ними.
Согласно принципу Дирихле, если у нас более 2025 учеников и каждый из них выбирает k симпатий, то при достаточно большом k (то есть когда k > 1012,5, что округляется до 1013, поскольку k должно быть целым числом), обязательно найдётся как минимум один ученик, которому нравятся одни и те же ученики, что может привести к ситуации, когда среди этих учеников будет хотя бы одна пара, которая либо взаимно нравится друг другу, либо наоборот.
Таким образом, условие, при котором мы гарантируем, что найдутся два ученика, которые либо оба друг другу нравятся, либо оба друг другу не нравятся, может быть сформулировано следующим образом:
Если k > 1012, то такие ученики обязательно существуют.
