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