Каким же образом вы сможете получить любую требуемую сумму от 0 долларов до 100? Используя первые шесть коробок, вы можете выплатить любую сумму от 0 до 63 долларов (чтобы выплатить 0 долларов, вы «передаете» ноль коробок!!!).
А что если вам нужно выплатить 64 доллара? Сначала вы отдаете седьмую коробку, в которой 37 долларов. Затем вычитаете 37 долларов из 64 долларов, и остается 27 долларов. Эту сумму вы можете выплатить, используя первые шесть коробок, суммы в которых соответствуют степеням числа 2. В данном конкретном случае вы отдаете коробки, сумма денег в которых равна 37, 16, 8, 2 и 1 доллару. Аналогичный принцип можно использовать для любой суммы в пределах 100 долларов.
Когда интервьюер спрашивает вас об «ограничениях» для b и n, он имеет в виду: «Каким образом вы можете определить, будет ли данный план работать для конкретных значений b и n?». Например, очевидно, что, если у вас есть миллион долларовых банкнот и всего одна коробка, такой план работать не будет. У вас недостаточно коробок для такой суммы. Обратите внимание, что обратная проблема вас не должна беспокоить: если у вас мало долларов и много коробок – все в порядке.
Вам нужно найти общую формулу, которая связывает b и n. Набросайте таблицу, показывающую, какую сумму вы можете выплатить, если у вас есть данное количество коробок.
b n
1 до 1 доллара
2 до 2 + 1 = 3 долларов
3 до 4 + 2 + 1 = 7 долларов
4 до 8 + 4 + 2 + 1 = 15 долларов.
Уже с первого взгляда видно, что добавление каждой новой коробки примерно удваивает количество денег, которое вы можете выплатить. Для двух коробок максимальная сумма 3 доллара, для трех коробок – 7 долларов. Если давать точный ответ, то b коробок достаточно для 2b 1-долларовых банкнот. Для того чтобы схема работала, n не должно превосходить 2b – 1.
Это приемлемый ответ. Он будет выглядеть немного более изящно, если вы добавите по 1 к правой и левой части: n + 1 < 2b. Это аналогично утверждению, что n должно быть меньше или равно 2b.
Как бы ни отражала эта загадка «цифровой дух нашего времени», она использовалась в той или иной форме еще со времен Ренессанса. Обычно ее называют задачей на взвешивание Баше, потому что она была упомянута в книге Клода Каспара Баше «Приятные и восхитительные задачи» (Problemes plaisans et dekctables), опубликованной в 1612 году. Баше спрашивал, какое минимальное количество гирь необходимо для того, чтобы уравновесить любой вес от 1 до 40 фунтов. Еще более ранняя версия этой задачи, тоже о взвешивании, была опубликована в трактате об измерениях Николо Тартальи в Венеции в 1556 году. Ответ, конечно, – 1, 2, 4, 8, 16 и 32 фунта. Для ренессансных гуманистов необходимость использования степеней числа 2 была гораздо менее очевидной, чем для интервьюеров из Microsoft, привычных к использованию двоичной системы счисления.