Question

Есть 10-этажное здание. Есть обезьянка. У обезьянки есть два кокоса. Она может залезть на любой этаж и скинуть один кокос. Если этаж высокий – кокос разобьется и его нельзя будет больше кидать. Как, потратив не больше 4 бросков, гарантированно установить, начиная с какого этажа кокосы начинают разбиваться?

Answer 1

1. Первый кокос бросаем с 4 этажа. Если он разбивается, то вторым кокосом последовательно проверяем 1, 2, 3 этаж - итого, не более 4 бросков.

2. Если кокос на броске (1) не разбился, то производим следующий бросок с 7 этажа. Если кокос разбивается, то вторым кокосом последовательно проверяем 5, 6 этаж - итого, не более 4 бросков.

3. Если кокос на бросках (1, 2) не разбился, то производим следующий бросок с 9 этажа. Если кокос разбивается, то вторым кокосом проверяем 8 этаж - итого 4 броска.

4. Если кокос на бросках (1, 2, 3) не разбился, то производим следующий бросок с 10 этажа. Итого 4 броска.

Answer 2

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

Шаги:

1. Первый бросок: Пусть обезьяна бросает один из кокосов с середины (пятого) этажа.

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

3. Второй бросок: Как только обезьяна найдет этот этаж, она будет бросать второй кокос с этого этажа.

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

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