Обезьяна и орехи

Сколько бросков потребовалось бы обезьяне, если бы у нее был только один орех?

А сколько бросков обезьяне нужно, если в доме всего один этаж? Два этажа? Три этажа? Четыре этажа?

Возможно, предлагаемое решение покажется вам чересчур подробным, но в нем нарочно сделана попытка показать, как вообще нужно строить рассуждения и какие нужно пытаться ставить вопросы, решая нестандартные задачи. Такие «слишком подробные» места выделены мелким шрифтом и их можно пропускать, если вы торопитесь узнать ответ.

Сначала решим задачу, предполагая, что в распоряжении обезьяны есть только 1 кокосовый орех. Ее действия в этом случае предопределены: сначала она должна бросить орех с 1-го этажа, затем, если он не разбился, — со 2-го этажа, если он снова не разбился — с 3-го этажа и так далее. Тот этаж, при броске с которого кокосовый орех разобьется, и будет искомым.

Спросим себя, может ли обезьяна действовать иначе? Допустим, первый бросок она совершила не с 1-го этажа, а с 3-го. Если кокосовый орех не разбился, то это означает, что он не разбился бы и при бросках с 1-го и 2-го этажей; для более высоких этажей результат неизвестен, и обезьяне нужно продолжить свои изыскания. Но что означает, что орех разбился? Ясно, что тогда он разбился бы и при броске с 4-го, 5-го, ..., 15-го этажей. Но разбился бы орех, если бы обезьяна скинула его с 1-го или со 2-го этажа? Это остается невыясненным, а проверить возможности не представляется, поскольку единственный кокосовый орех уже расколот, а больше орехов у обезьяны нет.

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

Таким образом, если в распоряжении обезьяны всего 1 кокосовый орех, она должна бросать его последовательно с 1-го этажа, 2-го этажа, 3-го этажа и так далее до тех пор, пока орех не разобьется (или пока этажи не закончатся). Ясно, что в самом худшем случае — если орех попался достаточно твердый — обезьяне потребуется совершить 15 бросков.

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

Итак, чтобы гарантированно удовлетворить свое любопытство, обезьяне понадобится столько же бросков, сколько в доме этажей. Для удобства сформулируем этот результат в виде леммы.

Лемма 1. Если в доме n этажей, а у обезьяны 1 орех, то нужно n бросков.

Вернемся к исходной задаче. Зададимся таким вопросом: что будет, если первым броском свой первый кокосовый орех обезьяна скинет, скажем, с 10-го этажа? Имеется два возможных исхода. Либо орех расколется, и тогда у обезьяны останется только один кокосовый орех и естественное любопытство, с какого самого низкого из первых девяти этажей его нужно бросить, чтобы он разбился. Как мы уже знаем из леммы 1, для этого надо совершить 9 бросков. Либо орех останется целым, а значит, у обезьяны в наличии по-прежнему будет 2 ореха, но проверке теперь будут подлежать лишь последние 5 этажей.

Следовательно, бросок ореха с 10-го этажа сводит исходную задачу к двум другим: «1 орех, 9 этажей» и «2 ореха, 5 этажей». Вычислив количество необходимых бросков в каждой из этих задач, нам нужно будет взять максимум из этих двух чисел, а затем прибавить к нему единицу. Так мы получим ответ для исходной задачи при условии, что первый бросок был совершен с 10-го этажа. Точно так же, если первой попыткой обезьяна скидывает свой орех с 5-го этажа, это приводит ее либо к ситуации «1 орех, 4 этажа» (если орех разбился), либо к ситуации «2 ореха, 10 этажей» (если орех остался целым). И вообще, бросок с k-ого этажа естественным образом дробится на два случая: «1 орех, (k − 1) этаж» и «2 ореха, (15 − k) этажей».

Все вышесказанное приводит нас к необходимости последовательно найти решение для ситуаций «2 ореха, 1 этаж», «2 ореха, 2 этажа», «2 ореха, 3 этажа», ..., «2 ореха, 14 этажей». Исследуем их подробнее.

Ясно, что если в доме лишь 1 этаж, то достаточно всего одного броска. Если в доме 2 этажа, то необходимо совершить 2 броска. В самом деле, если обезьяна скинет орех с 1-го этажа, а он не разобьется, то второй попыткой ей придется сбрасывать его со 2-го этажа. Если же обезьяна скинет орех со 2-го этажа и он разобьется, то останется невыясненным, раскололся бы орех при броске с 1-го этажа или нет. Для ответа на этот вопрос нужно скинуть с 1-го этажа второй орех.

Интереснее ситуация, когда в доме 3 этажа. Ясно, что в этом случае одним броском обезьяне не обойтись. Однако оказывается, что двух попыток вполне достаточно. Именно, первый бросок надо совершить со 2-го этажа. Далее, если орех не разбился, его нужно скинуть с 3-го этажа. А если разбился, то надо взять второй орех и скинуть его с 1-го этажа.

Как теперь быть, если в доме 4 этажа? Сколько попыток обезьяне понадобится? С одной стороны, очевидно, что не меньше, чем в том случае, когда этажей было 3, то есть как минимум 2 попытки. С другой стороны, если первый бросок обезьяна совершит с 1-го этажа, то в удачном случае (орех разбился) делать больше ничего не придется, а в неудачном (орех не разбился) задача сведется к уже известной «2 ореха, 3 этажа», которая решалась в 2 броска. Таким образом, 3 бросков обезьяне заведомо достаточно. Весь вопрос теперь заключается в том, всегда ли в неудачном случае обезьяне понадобится 3 броска или же можно гарантированно обойтись двумя. Оказывается, двух попыток, вообще говоря, недостаточно. Ведь если первый бросок обезьяна совершит с 1-го или 2-го этажа, а орех не расколется, то останутся непроверенными как минимум 2 верхних этажа, что требует еще 2 попытки. Если же после первого броска, совершенного с 3-го или 4-го этажа, орех разобьется, то опять же останется как минимум два непроверенных этажа (на этот раз нижние), снова требующие хотя бы 2 попытки. То есть ответ в задаче «2 ореха, 4 этажа» — 3 броска.

Как мы видим, увеличение на 1 количества этажей в доме изменяет число необходимых бросков не более чем на 1. Однако иногда количество попыток увеличивается, а иногда остается прежним. Таким образом, нам нужно понять закономерность: в каких случаях при увеличении этажности ответ будет меняться, а в каких — нет. Чтобы определить эту закономерность, разберем случаи, когда у обезьяны два кокосовых ореха, а этажей в доме 5, 6 и 7.

Итак, если в доме 5 этажей, то скидывание первого ореха с 1-го этажа, как мы уже понимаем, приводит к ситуации «2 ореха, 4 этажа» с известным результатом — 3 броска, то есть всего понадобится 4 попытки. А вот если обезьяна скинет орех уже со 2-го этажа, то задача сведется к двум таким: «1 орех, 1 этаж» и «2 ореха, 3 этажа». Они решаются за 1 и 2 попытки соответственно, максимум из этих двух чисел равен 2, а значит, всего обезьяне понадобится 3 броска. То есть задачи «2 ореха, 4 этажа» и «2 ореха, 5 этажей» имеют одинаковый ответ: 3 броска.

Аналогичная ситуация обнаруживается при разборе задачи «2 ореха, 6 этажей». Если первое скидывание проводится с 1-го этажа, то задача сводится к ситуации «2 ореха, 5 этажей» с результатом 3 броска и общим ответом 4 броска. Если первое скидывание обезьяна производит со 2-го этажа, то задача сводится к случаям «1 орех, 1 этаж» и «2 ореха, 4 этажа». Для их разрешения необходимо совершить 1 и 3 броска соответственно, максимум этих чисел — 3, а значит, общим результатом будут 4 броска. Если же первое скидывание произошло с 3-го этажа, то задача разделяется на «1 орех, 2 этажа» и «2 ореха, 3 этажа». В каждой из полученных подзадач получается 2 броска, поэтому всего нужно сделать 3 броска.

Наконец, если в доме 7 этажей, а у обезьяны 2 кокосовых ореха, то первый бросок, произведенный с 1-го этажа, приводит к ситуации «2 ореха, 6 этажей» и общему результату 4 броска. Первый бросок, произведенный со 2-го этажа, сводит задачу к случаям «1 орех, 1 этаж» и «2 ореха, 5 этажей» с общим ответом 4 броска. Первый бросок, произведенный с 3-го этажа, приводит к случаям «1 орех, 2 этажа» и «2 ореха, 4 этажа»; общим ответом снова оказывается «4 броска». Дальнейшее увеличение номера этажа, с которого обезьяна совершает первое скидывание, бессмысленно. И правда, по лемме 1 задача «1 орех, k этажей» решается за k бросков, а значит, при k > 3 нам понадобится слишком много попыток. Итого, для решения задачи «2 ореха, 7 этажей» обезьяне понадобится 4 броска.

Последнее соображение наводит на важную мысль: поскольку задача «2 ореха, 6 этажей» решалась за 3 попытки, для решения задачи «2 ореха, 7 этажей» осмысленно рассматривать возможность совершения первого броска сразу с 3 этажа. Действительно, чем выше этаж, с которого обезьяна делает первый бросок, тем меньше надо будет бросков в том случае, если орех после этого броска не расколется. Однако совершать бросок с 4 этажа уже невыгодно, поскольку если орех разобьется, то для удовлетворения любопытства всего обезьяне потребуется, вообще говоря, не меньше 4 бросков.

Пусть теперь мы знаем, что задача «2 ореха, (n − 1) этаж» решается за m попыток. Тогда при решении задачи «2 ореха, n этажей» первый бросок надо совершить с m этажа. В том случае, если орех расколется, задачу «1 орех, (m − 1) этаж» мы решим за (m − 1) бросок, а значит, все сведется к случаю, когда орех останется целым, то есть к задаче «2 ореха, (n − m) этажей». Делать первый бросок с более высокого этажа неразумно, поскольку если орех разобьется, то согласно лемме 1 мы заведомо не узнаем ответ на интересующий нас вопрос быстрее, чем за (m + 1) попытку. А кидать первой попыткой орех с более низкого этажа невыгодно, так как тогда нам надо будет решать более сложную задачу в том случае, если он не расколется.

Итог этих рассуждений подведем в лемме.

Лемма 2. Пусть для решения задачи «2 ореха, (n − 1) этаж» нужно m бросков. Тогда для решения задачи «2 ореха, n этажей» также нужно m бросков тогда и только тогда, когда задача «2 ореха, (n − m) этажей» решается не более чем за (m − 1) бросок.

Проиллюстрируем работу леммы 2 на примерах. Как мы выяснили выше, задача «2 ореха, 7 этажей» решается за 4 броска. Значит, для решения задачи «2 ореха, 8 этажей» также нужно 4 попытки. В самом деле, это следует из леммы 2, так как 8 − 4 = 4, а задача «2 ореха, 4 этажа» решается за 3 броска. Аналогично, трех попыток достаточно для 5 и 6 этажей, откуда следует, что за 4 броска обезьяна удовлетворит свое любопытство в задачах «2 ореха, 9 этажей» и «2 ореха, 10 этажей». А вот для 7 этажей нужно уже 4 попытки, а значит, в задаче «2 ореха, 11 этажей» потребуется 5 бросков.

Проводя такие рассуждения, легко убедиться, что 5 бросков хватит, если в доме 12, 13, 14 или 15 этажей.

Таким образом, ответ на основную задачу легко найти, последовательно применив лемму 2 к домам все более высокой этажности. Если в доме 1 этаж, то обезьяне нужен 1 бросок. Когда дом двухэтажный или трехэтажный, достаточно 2 бросков. Если этажей 4, 5 или 6, то нужно 3 броска. Если в доме от 7 до 10 этажей, то требуется уже 4 броска. Наконец, для домов с 11–15 этажами (как в нашем случае) необходимо 5 бросков. При этом последовательность бросков для 15-этажного дома однозначно определена схемой, представленной ниже. На схеме в белых квадратах указаны этажи, с которых обезьяна должна в очередной раз скинуть кокосовый орех, красная стрелочка соответствует случаю, когда орех раскололся, а синяя — случаю, когда орех остался цел. Первый бросок следует сделать с 5 этажа, дальнейшие броски нужно совершать согласно схеме. Тогда число в желтом квадрате, к которому в итоге обезьяна придет, и будет ответом на ее вопрос.

Итак, ответ: 5 бросков.

Естественным образом возникающий после решения задачи вопрос заключается в том, как изменится результат, если обезьяне удастся раздобыть не 2, а, скажем, 3, 5 или 10 кокосовых орехов, а бросает она их не из 15-этажного дома, а из 100-этажной или даже 1000-этажной башни. Иными словами, вопрос заключается в том, каким будет ответ в общем случае, пусть даже нам удастся вывести его лишь приблизительно.

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

Ясно, что при n = 1 достаточно одного броска, сколько бы орехов у обезьяны ни было. При увеличении значения n на 1, как мы могли видеть ранее, число необходимых бросков либо также увеличивается на 1, либо остается неизменным. Например, при переходе от n = 1 к n = 2 (и от n = 3 к n = 4) оно увеличивается, а при переходе от n = 2 к n = 3 — нет (если только k ≠ 1, конечно). Ключевой момент, таким образом, состоит в определении закономерности, когда это число увеличивается, а когда — нет.

Рассмотрим набор функций g_k(m) натурального аргумента m, заданных согласно следующему правилу: g_k(m) = n в том случае, если n — это максимальное количество этажей в доме, для которого обезьяне гарантированно хватит m бросков, чтобы удовлетворить любопытство (при условии, что в распоряжении обезьяны имеется ровно k кокосовых орехов). Иными словами, равенство g_k(m) = n означает, что задача «k орехов, n этажей» решается за m бросков, а задача «k орехов, (n + 1) этаж» — уже за (m + 1) бросок. Наша ближайшая цель — попытаться найти формулу для g_k(m) при всех возможных k.

Как легко видеть, из леммы 1 вытекает, что g₁(m) = m. Для других значений k выписать явный вид функции оказывается не так просто, однако удается получить некоторое рекуррентное соотношение. При этом помогает то же самое соображение, что и в доказательстве леммы 2: если задача «(k + 1) орех, n этажей» решалась за (m + 1) бросок, то при решении задачи «(k + 1) орех, (n + 1) этаж» первый бросок стоит совершить с (g_k(m) + 1)-го этажа. Действительно, тогда исходная задача распадется на две: «k орехов, g_k(m) этажей» (решается за m бросков) и «(k + 1) орех, (n − g_k(m)) этаж». Последняя задача решается за m бросков в том случае, когда n − g_k(m) ≤ g_k+1(m). Следовательно, оптимальным значением будет n = g_k+1(m) + g_k(m), что в свою очередь означает, что g_k+1(m + 1) = n + 1 = g_k+1(m) + g_k(m) + 1. Учитывая, что g_k(1) = 1 для всех k, найденную формулу можно переписать следующим образом:

Ввиду важности полученных результатов, оформим их в виде леммы.

Лемма 3. а) g_k+1(m + 1) = g_k+1(m) + g_k(m) + 1.
б) g_k+1(m + 1) = (g_k(1) + g_k(2) + ... + g_k(m)) + (m + 1).

Теперь, когда в нашем распоряжении имеются рекуррентные соотношения для g_k(m), найти явные формулы для этих функций оказывается посильной задачей. Действительно,

Аналогичным образом, по индукции, можно доказать следующие формулы более общего вида:

При выводе этих формул помогают следующие соображения:

и то же самое в общем случае:

Обладая формулами для g_k(m), мы можем дать удовлетворительный ответ на поставленный нами вопрос. В самом деле, нам нужно узнать по числу этажей n количество необходимых бросков m. Функция g_k(m) в определенном смысле осуществляет обратную операцию: с ее помощью по заданному числу бросков m мы можем определить промежуток, для любого числа этажей n из которого ответ на задачу «k орехов, n этажей» будет составлять ровно m бросков. Так как при каждом k функция g_k(m) представляет собой многочлен степени k, то при больших значениях m она ведет себя примерно как m^k/k!. Это означает, что для достаточно большого числа этажей n обезьяна, обладающая k кокосовыми орехами, удовлетворит свое любопытство примерно за бросков.

Напротив, для малых значений n наблюдается совершенно другая картина. Если орехов достаточно много для того, чтобы обезьяна могла не бояться, что они кончатся в самый неподходящий момент, то можно спокойно воспользоваться идеей двоичного поиска. В этом случае обезьяне оказывается достаточно ([log₂ n] + 1) бросков.