Однажды юная Глория из Арканзаса отправилась в Калифорнию. Ей необходимо было снять на неделю номер в гостинице.

Портье в гостинице встретил ее весьма нелюбезно.

Портье. Могу предложить только номер за 20 долларов в сутки. Плата наличными.

Глория. Простите, сэр, у меня нет при себе денег. Есть только этот золотой браслет. Каждое из его 7 звеньев стоит дороже 20 долларов.

Портье. Так и быть, давайте сюда ваш браслет.

Глория. Не торопитесь. Я попрошу какого-нибудь ювелира распилить браслет и буду отдавать вам по 1 звену в день, а к концу недели, когда мне пришлют из дому деньги, отдам браслет в починку.

После долгих споров портье согласился. Но перед Глорией встала задача: как распилить браслет?

Глория. Торопиться не следует. Ведь ювелир потребует с меня плату за каждое распиленное и вновь запаянное звено браслета.

Поразмыслив, Глория поняла, что ей вовсе не нужно распиливать все звенья, поскольку отдельные части браслета можно комбинировать так, чтобы число оставшихся у портье звеньев каждый раз соответствовало плате за номер. Сколько звеньев вы бы приказали распилить на месте Глории?

Достаточно распилить лишь одно-единственное звено: третье с любого конца цепи. Браслет распадется на 3 части длиной в 1 звено, 2 звена и 4 звена. Отдавая их в необходимой комбинации портье и получая предыдущие, Глория сможет оставлять у портье каждый день на 1 звено больше, чем накануне.

Решающее звено

Чтобы решить эту задачу, необходимо принять во внимание два соображения. Во-первых, понять, что наименьший набор отрезков золотой цепочки, позволяющий оставить у портье любое число звеньев от 1 до 7, состоит из 3 отрезков длиной в 1, 2 и 4 звена. Как мы уже знаем из решения предыдущей задачи, эти числа — не что иное, как последовательные степени числа 2, положенные в основу двоичной системы счисления.

Во-вторых, необходимо понять, что разделить браслет на части длиной в 1, 2 и 4 звена можно распилив одно-единственное звено.

Задача допускает обобщение на случай, когда браслет или цепочка состоят более чем из 7 звеньев. Например, пусть у Глории имеется с собой золотая цепочка из 67 звеньев, которую необходимо распилить с той же целью, что и злосчастный браслет, — для уплаты за проживание в гостиничном номере от 1 до 67 суток по 1 звену за сутки. Оказывается, что в этом случае достаточно распилить лишь 3 звена. Вы знаете, какие именно? Может быть, вы можете предложить общий метод решения задачи, позволяющий распиливать минимальное число звеньев цепи произвольной длины?

Интересный вариант этой задачи возникает в том случае, если первоначально концы n-звенной цепочки соединены так, что цепочка превратилась в замкнутую петлю. Например, предположим, что у Глории есть золотая цепочка из 79 звеньев. Сколько звеньев необходимо распилить, чтобы Глория могла оплатить от 1 до 79 суток пребывания в гостинице из расчета по 1 звену за сутки?