Обезьяна и кокосы.

Что даёт один бросок? Если кокос не разбился, значит искомый этаж выше текущего и можно отбросить все этажи ниже. Если кокос разбился - значит искомый этаж ниже или равен текущему и можно отбросить все этажи ниже. Но есть одна проблема - разбитый кокос уже нельзя использовать дальше. Т. е. второй своим разбиванием уже должен точно указать на нужный этаж.

Пойдём в рассуждениях от самого тупого. Пусть кокос один. Как найти ответ гарантированно? "Гарантированно" - значит, что надо совершить последовательность действий так, чтобы при любом исходе каждого действия можно было прийти к точному ответу даже при самом неудобном развитии событий. А наиболее длинная цепочка действий (т. е. худший случай) и будет нашим наименьшим числом бросков.

Так вот. Если кокос один, нам обезьянке пришлось бы кидать его сначала с первого этажа, потом со второго, потом с третьего и т. д. Т. к. как только он разбит, мы уже не сможем проверить непроверенные этажи ниже и у нас отсеятся только этажи выше. Значит наименьшее количество шагов тут 100.

А у нас кокоса два. Значит к первому можно применить более быстрый алгоритм поиска.
Тут надо заметить, что следует нахождение этой критической высоты на любом этаже равновероятной. Никакой информации a priori не известно. Поэтому строить алгоритм, например, на предположении что "скорее всего разобьётся ближе к низу" не получится. Хотя в реальных условиях он мог бы быть довольно быстрым.

Итак, первым кокосом надо сузить область поиска. Напрашивается предложенный в предыдущем ответе метод дихотомии. Сначала исключим 50 этажей, потом, если повезёт, ещё 25. Потом ещё 13, ну а когда разьбъётся - надо вторым снова по-одному пройтись по выявленной границе снизу вверх. Однако какое количество шагов может понадобиться? В худшем случае 50. Если кокос разбился на 50-м этаже, значит придётся проверять 1-й, 2-й, 3-й, ..и, в худшем случае, 49-й.

Это лучше чем 100, конечно, но как-то кажется, что можно и меньше.

А пусть обезьяна сделает так. Первым кокосом будет проверять этажи через каждые N штук снизу. Тогда найдётся интервал от (k-1)*N до kN, в котором точно будет искомый этаж. И его надо будет пройти снизу вверх вторым кокосом.
Первым кокосом надо будет сделать максимум 100/N шагов, а вторым N. Тогда 100/N + N надо минимизировать.
Взяв производную и приравняв нулю находим, что N = 10.
Итак, проверям 10-й, 20-й, 30-й и т. д. этажи пока первый кокос не бьётся. А затем вторым находим нужный этах из неотсеявшихся 10. Итого получается 20 бросков.

Смутно кажется, что и это не предел. К примеру, если сначала испытать 25-й этаж, потом 25+1/4*(100-25), потом снова текущий + четверть от оставшихся, то должно получиться лучше чем те же 50. Только надо рассчитать когда шаги станут слишком малыми, чтобы оправдывать себя и перейти к перебору или даже сделать ещё шажок дихотомией. Ну и начальный этаж такой, чтобы до него перебором было меньше 20 шагов. Но вот посчитать непосредственно что-то не получается. Если я правильно записал, то получаются выражения не очень поддающиеся аналитическим рассчётам, а с численными возиться неохота.

А что было бы, если бы запас кокосов был неограничен? Тогда разбитый кокос ничем бы не мешал и каждый бросок давал бы нам по 1 биту информации. Если применять дихотомию (положим, что критический этаж первый) : 50, 25, 13, 7, 4, 2, 1 - 7 бросков, 7 бит. и действительно, 100 лежит между 64 и 128, равными 2^6 и 2^7 соответственно. Значит, чтобы закодировать информацию об одном этаже из ста действительно потребовалось бы 7 бит. И 7 бросков - теоретический предел, ниже которого уже не опуститься.

>^.^<

зависит от того, с какого всё же этажа они начинают разбиваться.... условие неполное!! ! какой этаж нужно вычислить?

хотя.... не меньше 2, кокосы то кончатся!!!!

условие вполне полное: залазием на средину здания (50 этаж) и кидаем. ну допустим разбилось (или нет, без разницы) . если на 50 бьются - значит спускаемся на 25 (опять середина) и опять кидаем - опять разбилось, ладно.. . делим 25 на лапопам - 12,5 (между этажами можно кидаться? ну если нет - округляем и кидаем с 13) в общем таким макаром мы выясним "критическую высоту" в случае 100-этажки с. . э.. . с 5 попытки

за 1, наверное. собственно от нижнего этажа кидать и пока не разобьется)

С 5 этажного .