Олимпиадная задача по теории графов, делимости и принципу Дирихле для 8-9 класса
При каком n > 1 может случиться так, что в компании из n + 1 девочек и n мальчиков все девочки знакомы с разным числом мальчиков, а все мальчики – с одним и тем же числом девочек?
Показать ответ
При любом нечётном n > 1.
Разобрать решение
Девочка может быть знакома с 0, 1, ..., n мальчиками. Поскольку девочек n + 1 и вариантов n + 1, то все эти варианты реализуются. При этом общее число пар знакомых равно (0 + 1 + ... + n) = n(n+1)/2, поэтому каждый мальчик знаком с (n+1)/2 девочками. Значит, n нечётно.
При любом нечётном n = 2m + 1 можно осуществить требуемые знакомства: разобьём девочек на пары (всего m + 1 пара); первую девочку k-й пары
(k = 0, 1, ..., m) познакомим с k мальчиками, вторую – с остальными n – k мальчиками. При этом каждый мальчик знаком ровно с одной девочкой из каждой пары.
Обсуждение
0Комментариев пока нет.