Задача 010 — Задачи на Графы

В лагере $2012^{2012}$ детей, у каждого не более трех друзей. Всегда ли можно их построить в ряд так, чтобы между любыми двумя друзьями стояло не более чем 2012 человек?

Подсказка

Попробуйте построить контрпример в виде дерева

Решение

Ответ: Не всегда.

Решение: Пусть Петя знаком с двоими, каждый из его знакомых — с двоими новыми, каждый из этих четверых — снова с двоими новыми и т.д., пока не перезнакомим всех $2012^{2012}$ детей. В получившемся «двоичном дереве» знакомств на $k$ -ом от Пети ярусе (кроме, возможно, самого последнего) — $2^{k}$ детей, поэтому ярусов в нем не больше, чем $m$ , где $m$ таково, что $2^{m-1}<2012^{2012}<2^{m}$ . Поскольку $2^{11}=2048>2012, m<11 \cdot 2012$ . Допустим, нам удалось построить детей нужным образом. Возьмем самого левого и самого правого. Между ними в построенном нами дереве есть путь длины не более $2 m<22 \cdot 2012$ . Но между любыми двумя соседями на этом пути в строю стоят не более 2012 человек. Поэтому длина строя должна быть не больше 2013•22•2012, что, очевидно, намного меньше, чем $2012^{2012}$ . Противоречие.