Задачка о швырянии шаров

[akry]

Kavychka подкинула мне интересную задачку.

У вас есть небоскрёб в 100 этажей. Есть 2 биллиардных шара. И 19 попыток, чтобы выяснить, брошенные начиная с какого этажа шары будут разбиваться вдребезги. Этаж может быть любым, задача — разработать алгоритм определения этажа с учётом вводной.

Kavychka передала мне, что есть три варианта решения, из которых только один является оптимальным.

В простом виде задача решается за несколько минут. Предлагаю вам тоже развлечься.

А дальше начинается интересное. Похоже, что решений не три, а гораздо больше.

Кто решил задачу или замучался её решать, заглядывайте под кат. Обсудим.

 

 

Итак, простейший вариант решения. На него наводит волшебное число 19 = 10+9. Бросаем шары каждые 10 этажей, начиная с 10-го. Как шар разбивается, откатываемся на -9 этажей и бросаем шары, поднимаясь каждый раз на один этаж. Итого, в самом крайнем случае, для 99-го этажа у нас уходит как раз 19 бросков. И два шара.

Решение, которое возможно оптимально. Бросаем с 19 этажа, наращивая каждый раз по 10 этажей. Как шар разбивается, возвращаемся на -9 этажей и как в предыдущем пункте. Возможно я не догоняю, но мне не вполне ясно, оптимальное ли это решение, и если да, то почему. Конечно вероятность того, что нужный этаж окажется в промежутке 1-19 примерно равна 1/5, ну и что? Или дело в экономии электроэнергии лифта, потому что спускаться легче, чем подниматься? В общем, кто знает, просветите.

Вот мы и подошли к интересному. Несложные расчёты показывают, что мы можем бросать и по 9 шаров, начиная с 9 этажа. И по 8, начиная с 8-го. И бросать по сложным схемам с шагом между этажами типа 19 - 18 - 17 - 16… А начинать бросать можем с этажа в диапазоне от 7-го по 19 этаж.

В общем, принцип похоже такой:

1. Для каждого следующего броска количество оставшихся «больших» шагов и количество «малых» (по 1 этажу) должно быть меньше оставшегося числа попыток. Это верно для любого количества этажей и любого количества попыток.
2. Кидаем сначала «большими шагами» по F этажей, как только шар разбивается, возвращаемся на F-1 этаж и бросаем шары, увеличивая этаж на один с каждым броском.
3. Первый самый высокий этаж, с которого можно начинать бросать, равен количеству попыток (в силу п.1).
4. Первый самый малый этаж, с которого можно начинать бросать — не знаю какой. UPD. Затмение нашло — конечно см. п1.
5. Предел попыток для N этажей (и двух шаров) будет равен сумме десятков (округлённой в меньшую сторону) + 9 для N >= 10. То есть, в случае 105 этажей, попыток должно быть 10+9 = 19. А для 128 этажей — 12 + 9 = 21 попытка.

В случае если мы используем больше двух шаров, тоже возможны разные варианты стратегий кидания. Можно сделать не две, а три «нарезки». Например, вначале бросать каждые 30 этажей, потом каждые 7 этажей, потом по одному этажу. Принцип остаётся тот же.

Мне кажется выгодным каждый дополнительный шар использовать для того, чтобы поделить искомое пространство пополам. Например, в случае со 100 этажами и 3 шарами, первый шар бросаем с 50-го этажа. Он или разбивается, или нет. Если разбивается, значит наша половина — от 1 по 49 этаж. Если не разбивается, то ищем уже в диапазоне от 51 до 100 этажа.

Если появляется ещё один, четвёртый шар, просто делим пространство этажей пополам два раза. В пределе у нас будет log2(N) попыток. Нужный этаж для стоэтажного небоскрёбика мы найдём максимум за 7 бросков. И 6 шаров.

В итоге, даже для вводных в начале задачки (100 этажей, 19 попыток и 2 шара) возможно больше трёх вариантов решения. Какой из них самый оптимальный, и как определить оптимальность, я не знаю.

UPD. Нашёл оптимальное решение — за 14 попыток. Бросать с N=14 этажа с шагом N-1.