На встрече 20 человек, дружба взаимна, сам с собой никто не дружит. Докажите, что у двоих одинаковое число друзей на…
Quant ResearchУровень: ПрактикаGraph pigeonhole
На встрече 20 человек, дружба взаимна, сам с собой никто не дружит. Докажите, что у двоих одинаковое число друзей на встрече.
Подсказки
- Почему все 20 возможных чисел не могут сосуществовать?
- После исключения крайностей примените принцип Дирихле.
Ответ
Степени лежат от 0 до 19, но 0 и 19 не могут присутствовать вместе: знакомый со всеми знаком и с предполагаемым одиночкой. На 20 человек остаётся не более 19 значений, значит есть повтор.
Источник и лицензия: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · ответ: редакция Quantoros · перевод: Quantoros