Стеклянные шарики

[neo66]

Вспомнилась симпатичная задача на нахождение оптимальной стратегии:

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

Одна попытка - это одно бросание одного шарика с какого-то этажа. Если шарик после бросания не разбился, то он сохраняет все свои свойства и его можно использовать в дальнейшем; разбившийся шарик из игры выбывает. Если шарик разбивается при бросании с этажа номер n, то он разобьется и при бросании с этажа номер n+1. Шарики могут оказаться и небьющимися.

[Руст]

Можно за 19. Пробуем бросать с 10-гоб 20-го, c 100-го (с шагом 10). Если шарик разбился, на 10k, то бросаем второй с 10k-9,10k-8,... (c шагом 1).

[Brukvalub]

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

Добавлено спустя 14 минут 55 секунд:

И что означает эта фраза:

neo66 писал(а):

Шарики могут оказаться и небьющимися.

?

[neo66]

19 - много.
Небьющиеся - означает: неразбивающиеся никогда

[maxal]

Старая задача. По слухам с интервью в Microsoft.

А правильный ответ здесь: 14.

[Brukvalub]

neo66 писал(а):

Небьющиеся - означает: неразбивающиеся никогда

Спасибо, сейчас запишу, а то я все время забываю смысл этого термина.

[bot]

Есть и обобщение: N этажей и n шариков.

[Руст]

maxal писал(а):

Старая задача. По слухам с интервью в Microsoft.

А правильный ответ здесь: 14.

Более оптимально стратегия, m, 2m-1, 3m-3,...(k+1)(m-k/2)>N. Отсюда максимальное количество ходов m>(N/(k+1)+k/2). Минумум по k получается $m=[\frac{\sqrt{8N+1}+1}{2}]$

[neo66]

Эта задача предлагалась в свое время на вступительных экзаменах в НМУ. Хороша, а?

[Руст]

Для n шариков ответ получается - количества шагов равна m, где C(m,n)<=N<C(m+1,n) начиная с некоторого N>N0.

[bot]

Нет, не так, но ключ у Вас есть.

[Руст]

bot писал(а):

Нет, не так, но ключ у Вас есть.

Почему не так. При n=1, очевидно, что m=N, согласуется с указанной формулой. Оно согласуется и при n=2 (хотя для индукции это не обязательно).
Докажем по индукции. Пусть это верно для N>C(2n,n)=N0 для всех n, что минимальное число ходов определяется из указанного свойства. Тогда вычисляем максимальное значение N для которого достаточно m ходов как сумму C(m,n)+C(m-1,n)+...=C(m+1,n).
Правда здесь надо биномиальные коэффициенты надо заменить функциями f(m,n) удовлетворяющим условиям f(1,n)=1, n>=1, f(m+1,n)=f(m,n-1)+f(m,n).

[neo66]

Руст писал(а):

maxal писал(а):

Старая задача. По слухам с интервью в Microsoft.

А правильный ответ здесь: 14.

Более оптимально стратегия, m, 2m-1, 3m-3,...(k+1)(m-k/2)>N. Отсюда максимальное количество ходов m>(N/(k+1)+k/2). Минумум по k получается $m=[\frac{\sqrt{8N+1}+1}{2}]$

Это не более оптимальная стратегия, а просто оптимальная.
Что касается обобщений - это уже чистая техника и ничего нового не привносит. Забавно, правда, что 7 шариков (для 100 этажей) - минимизирует число испытаний.

[Руст]

neo66 писал(а):

Что касается обобщений - это уже чистая техника и ничего нового не привносит. Забавно, правда, что 7 шариков (для 100 этажей) - минимизирует число испытаний.

То, что k шариков минимизирует (для 2^{k-1}<=N<2^k этажей) очевидна делением попалам.
Общий ответ для количества шагов m получается из условия
$f(m-1,n)<N<=f(m,n),$ где

$$f(m,n)=C_{m+n-1}^{n}.$$

[Brukvalub]

neo66 писал(а):

Это не более оптимальная стратегия, а просто оптимальная.

А как это доказать?