2019-04-01
Мартышка поднимается на один из 100 этажей небоскрёба и бросает вниз кокос. Она пытается выяснить, с какого наименьшего этажа нужно бросить кокос, чтобы тот разбился. Каково минимальное число попыток, достаточное для этого, если у мартышки всего два кокоса?
Решение:
Решим сначала следующую задачу: какой наибольшей высоты может быть здание, чтобы для него за $k$ бросаний можно было выяснить то, что спрашивается в исходной задаче. Наибольший этаж, который соответствует первой попытке, равен $k$. Ведь если кокос разобьётся, у нас останется всего один кокос и $k - 1$ попыток. В этих условиях мы вынуждены проверять последовательно все этажи, начиная с первого. Если же первый кокос не разбился, то бросаем его с этажа $k +(k - 1)$. По аналогии с предыдущим проверяется, что это наибольший возможный этаж, ведь если теперь первый кокос разобьётся, у нас останется всего $k - 2$ попыток, и мы вынуждены будем проверять этажи последовательно по возрастанию, начиная c $(k +1)$-го этажа. Если же первый кокос не разбился при бросании с этажа $k + (k - 1)$, то бросаем его с этажа $k + (k— 1) + (k - 2)$ и т. д. Поэтому наибольшая высота здания для нашего «эксперимента» с к попытками равна $k + (k - 1) + \cdots + 1 = \frac {k(k+1)}{2}$. Для решения исходной задачи достаточно найти наименьшее натуральное $k$, для которого $\frac {k(k+1)}{2} \geq 100$. Отсюда получаем, что выяснить наименьший этаж, с которого кокос разбивается, можно минимум за 14 попыток.