На волшебной горе расположена система озер и рек. Верхнее озеро образуется из тающего ледника. Из каждого озера вытекает ровно две реки, а впадает одна (за исключением верхнего). Первым на горе возле верхнего озера поселился гном Тим. Каждый новый обитатель горы строил свой дом как можно ближе к Тиму на одном из озер. На каждом озере силился только один гном. Сейчас на горе живут 2014 гномов. Какое количество рек надо проплыть Тиму, чтобы попасть в гости к последнему поселившемуся гному.
Схему волшебного города можно представить в виде двоичного дерева. В качестве узлов рассматриваются озёра, с построенными на них домами, в качестве входящих и исходящих рёбер – протоки. Корнем дерева ( выделенной вершиной) является озеро с домом Тима. Очевидно, что в двоичном дереве число узлов, до которых расстояние от корня равно F не превосходит 2F.На расстоянии один может находиться не более двух узлов, на расстоянии 2 – 4-х узлов и т. д.В таблице приведены значения максимального количества домов на расстоянии F.
Правила застройки города гарантируют появление нового дома на расстоянии F+1 в том и только в том случае, если все возможные места на расстоянии F уже заполнены. При этом число домов, находящихся не далее, чем на расстоянии F равно 1+2+4+…+2F=2F+1– 1.
В нашем случае могут быть вакантные места для строительства на расстоянии F, поэтому должно выполняться неравенство 2F+1– 1≥ 2014. Очевидно, что при F=9 выполнено неравенство 210– 1< 2014, а при F=10 –211– 1 ≥ 2014. Таким образом, максимальное количество протоков, которое надо проплыть до самого дальнего дома равно 10.
