Задача

Есть два стеклянных шарика и 100-этажный дом. Вы бросаете шарик с разных этажей этого дома, чтобы выяснить, на каком этаже шарик начинает разбиваться от падения (например, на пятом уже разбивается, а на четвёртом ещё нет). Вопрос: какое точное минимальное количество шагов понадобится для того, чтобы точно узнать на каком именно этаже шарики начинают разбиваться?

Примечание

• Шаг — это один бросок одного шарика.
• Шарик начинает разбиваться с определённого этажа.
• При решении задачи нужно понимать, что необходимо найти точно этаж. А это значит, что решение с бисекциями не подходит: нельзя допустить, чтобы оба шара разбились, пока этаж точно не найден.

Решение

1. Если бросать шарик подряд, начиная с 1-го этажа и до 100-го, то получим допустимое, но не оптимальное решение. Думаем, как его улучшить.

2. У нас ведь есть два шарика! Т.е., один можно разбить, получив с этого какую-то информацию. Например, если бросить его с 50-го этажа, то можно сразу узнать, какую половину здания дальше рассматривать. Это хорошо, но всё еще не оптимально.

3. А что если бросать шарик через какие-то промежутки? Например, бросать его на 10, 20, 30м этаже? Как только он разобьётся, мы будем знать, на каком промежутке искать дальше. Таким образом можно сократить количество бросков до 19ти. Но и этого нам мало.

4. Мы заметили, что если бросать с промежутком в 10, то если шарик разобьётся сразу, то вторым шариком мы сможем обнаружить нужный этаж гораздо раньше. Т.е., мы могли бы бросать сразу не с 10го этажа, а выше, и в итоге быстрее добрались бы до верха. Допустим, что мы решили бросать с N-го этажа. Тогда, очевидно, что если первый шарик разобьётся сразу, то нам понадобится еще max N-1 шагов, чтобы узнать нужный этаж. Т.е., в случае, если шарик разбивается сразу, нам нужно всего 1+N-1=N бросков. Ну, а что будет, если шарик сразу не разобьётся?

5. Первым броском мы отсекли N этажей. Т.е., мы можем перейти к той же задаче, что и раньше, только этажей стало меньше. На каком же этаже нужно бросить шарик еще раз? Очевидно, что на N-1(считая от отсечения). Действительно, если шарик разобьётся получим: 1(первый неудачный бросок)+1(бросок на N+N-1 этаже)+N-2(бросаний второго шарика) - количество бросаний, нужное для определения этажа, если шарик разобьётся в первую или во вторую попытку.

6. Продолжаем заниматься отсечением. Размеры отсечений у нас получаются N,N-1,N-2 и т.д. Логично, что отсечения когда-то должны закончится. Значит, случится, что сумма всех отсечений будет больше высоты здания. Т.е. N+N-1+N-2. По известной ф-ле суммы арифметической прогрессии, это будет равно N*(N+1)/2. Для того, чтобы сумма отсечений покрывала весь дом, достаточно N=14(а N=13 недостаточно).

7. Вот так. Можно проверить и убедиться.