Уильям Паундстоун - Как сдвинуть гору Фудзи

У.У. Раус Болл упоминает эту головоломку в своем сборнике Mathematical Recreations and Essays («Математические досуги и эссе», 1892 год), популярном в викторианскую эпоху. Болл считал, что эту головоломку придумали в средние века.

Хотя Льюис Терман использовал более простую версию этой задачи в своем первом тесте IQ, он сообщал, что две трети «обычных взрослых людей» не успевали решить эту задачу за отведенные на это пять минут. «Если читателю покажется, что для решения этой задачи от него требуется слишком много изобретательности, — писал Терман, — стоит напомнить читателю, что в истории человечества важные изобретения не рождались неожиданно, подобно Минерве [*], но делались постепенно, шаг за шагом». [143]

Минерва-Шминерва — версия задачи, использованная Терманом, действительно легкая. Это может отражать долговременную тенденцию увеличения «среднего» балла IQ (которую можно отметить, если вы используете для тестирования интеллекта тот же набор вопросов, что использовался в прошлом). В отличие от ожиданий Термана, среда оказывает существенное влияние на балл IQ.

Более трудная версия этой задачи, применявшаяся Microsoft, была использована в фильме Die Hard with a Vengeance («Крепкий орешек», 1995 год). В этом фильме коварный преступник так настроил бомбу, что она должна была взорваться, если бы Брюс Уиллис и Сэмюель Л. Джексон не решили бы эту задачу. В их распоряжении был фонтан в парке и два пластмассовых ведра указанных размеров. Отмеренную воду нужно было поставить на весы. Они не могли гадать и действовать приблизительно, потому что бомба взорвалась бы даже если бы они ошиблись всего на одну унцию (28,3 грамма). Они не могли и просто уйти, потому что у бомбы был «детектор близости цели». Уиллис и Джексон смогли найти решение, да еще и дружески переругивались при этом («Я тебе не нравлюсь, потому что я белый!» / «Ты мне не нравишься, потому что я из-за тебя могу взлететь на воздух!»).

Один из ваших работников настаивает на том, чтобы ему платили золотом каждый день…

Вам нужен один кусок золота, чтобы заплатить вашему работнику за первый день. Очевидный способ — отрезать один кусок от конца золотого слитка. Менее очевидный способ: отрезать этот кусок в середине слитка, использовав для этого оба разрешенных вам разреза. Попробуйте сначала очевидный план (оставив за собой право пересмотреть свое решение). Вы отрезаете один кусок от конца бруска и отдаете его работнику.

Это оставляет вам слиток, состоящий еще из шести кусков, и один-разрез.

На второй день вы можете отрезать еще один кусок на конце слитка, но тогда у вас останется слиток из пяти кусков, а отрезать от него уже больше ничего нельзя. Вам нечем будет платить работнику на третий день.

Альтернативное решение — отрезать сегмент, состоящий из двух кусков. Тогда в конце второго дня вы можете отдать его работнику и получить от него назад один кусок как сдачу (при этом вы должны надеяться на то, что работник этот кусок еще не потратил).

Это оставит вас со слитком, состоящим из четырех кусков, одним куском, который вы получили как сдачу, а разрезов больше вы уже делать не можете. На третий день вы отдаете работнику один кусок. На четвертый день вы отдаете ему то, что осталось от слитка, то есть четыре куска, а два меньших он вам возвращает как сдачу. Затем вы аналогичным образом используете их, чтобы заплатить работнику на пятый, шестой и седьмой день.

У вас есть b коробок и n банкнот в один доллар…

Основная идея решения аналогична той, что использовалась в задаче о золотом слитке. Вы используете бинарную систему счисления. Положите в первую коробку 1 доллар, во вторую 2, в третью — 4 и т. д. Любую нужную сумму можно представить как сумму различных степеней числа 2.

Отличие от приятной загадки с золотым бруском заключается в том, что данная головоломка проверяет, как вы «справляетесь с исключениями». Одна из сложностей связана с тем, что не все n оказываются суммой последовательных степеней числа 2. У вас, вероятно, образуется какой-то «остаток» денег после того, как вы разложите по коробкам все возможные для данного n последовательные степени числа 2. Еще одна проблема — вам может не хватить коробок.

Допустим, у вас 100 долларов. У вас будут коробки, в которые вы положите 1, 2, 4, 8,16, 32… доллара, но у вас окажется недостаточно денег для того, чтобы в следующую коробку положить 64 доллара, поскольку вы уже положили в предыдущие коробки 1 + 2 + 4 + 8 + 16 + 32 = 63 доллара. Это значит, что у вас есть остаток в 37 долларов, а это число — нечетное и никак не может быть степенью двойки.

Каким же образом вы сможете получить любую требуемую сумму от 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 долларов.

Это приемлемый ответ. Он будет выглядеть немного более изящно, если вы добавите по 1 к правой и левой части: n + 1 < 2 b . Это, аналогично утверждению, что n должно быть меньше или равно 2 b.

Как бы ни отражала эта загадка «цифровой дух нашего времени», она использовалась в той или иной форме еще со времен Ренессанса. Обычно ее называют задачей на взвешивание Баше, потому что она была упомянута в книге Клода Каспара Баше Problemes plaisans et dekctables (фр. «Приятные и восхитительные задачи»), опубликованной в 1612 году. [144]Баше спрашивал, какое минимальное количество гирь необходимо для того, чтобы уравновесить любой вес от 1 до 40 фунтов. Еще более ранняя версия этой задачи, тоже о взвешивании, была опубликована в трактате об измерениях Николо Тартальи в Венеции в 1556 году. Ответ, конечно, — 1, 2, 4, 8, 16 и 32 фунта. Для ренессансных гуманистов необходимость использования степеней числа 2 была гораздо менее очевидной, чем для интервьюеров из Microsoft, привычных к использованию двоичной системы счисления.