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

[neo66]

Brukvalub писал(а):

neo66 писал(а):

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

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

Вывернем задачу "наизнанку". А именно: будем предполагать, что у нас есть $k$ ипытаний, и мы хотим проверить максимальное количество этажей - $N$. Пусть первый раз мы бросаем с этажа $a_1$, тогда, если первый шар разобьется, то вторым мы должны проверять все этажи подряд с 1_го до $a_1-1$. Поэтому
$a_1 \le k$.
Если он не разбивается, то у нас остается k-1 попытка, и для следующей попытки мы имеем
$a_2 \le k + (k-1)$. (где $a_2$ - номер этажа с которого делается вторая попытка).
И так далее по индукции:
$a_k \le k + (k-1) + (k-2) \dots + 1$
То есть $ N \le \frac{k(k+1)}{2}$
В нашем случае $N = 100$ и $k \ge 14$, так как $\frac{13(13+1)}{2} = 91 < 100$.

[Brukvalub]

Спасибо.

[bot]

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

$m=[\frac{\sqrt{8N+1}+1}{2}]$

Для двух шариков ответ хотя и похожий, но не совсем такой - округлять ведь нужно вверх, а не вниз. Если сам не сбился, то так:
$m=-[\frac{1-\sqrt{8N+1}}{2}]$

neo66 писал(а):

Вывернем задачу "наизнанку".

В общем случае ответ у меня есть в терминах "вывернутой наизнанку" задачи. Чтобы привести ответ в целых частях, нужно решить в целых числах неравенство n-й степени.

neo66 писал(а):

Что касается обобщений - это уже чистая техника и ничего нового не привносит.

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

Цитата:

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

Это отсюда вытекает: $2^6 < 100 < 2^7.$

[Руст]

bot писал(а):

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

$m=[\frac{\sqrt{8N+1}+1}{2}]$

Для двух шариков ответ хотя и похожий, но не совсем такой - округлять ведь нужно вверх, а не вниз. Если сам не сбился, то так:
$m=-[\frac{1-\sqrt{8N+1}}{2}]$

neo66 писал(а):

Вывернем задачу "наизнанку".

В общем случае ответ у меня есть в терминах "вывернутой наизнанку" задачи. Чтобы привести ответ в целых частях, нужно решить в целых числах неравенство n-й степени.

Всё верно, в случае n=2 обращение $C_{m+n-2}^n<N<=C_{m+n-1}^n$ имеет такой вид. В общем случае, я думаю получится неудобоваримое выражение для m.

[bot]

В общем случае обращать надо будет не это, но оно и без обращения красиво.

bot писал(а):

neo66 писал(а):

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

Это отсюда вытекает: $2^6 < 100 < 2^7.$

Э-э-э, чувствовал, что не совсем то отвечаю.
Надо так:
Минимизирует число испытаний 5 шариков.За 6 испытаний не справиться даже при неограниченном запасе шариков, а для 7 испытаний достаточно 5 шариков, причём 4-х шариков чуть-чуть не хватает.

[maxal]

См. также http://elementy.ru/problems/843/Obezyana_i_orekhi

[iancaple]

Известен такой простой ответ и решение: За $m$ ходов c помощью $n$ шаров нужный этаж среди $N$ этажей гарантированно определяется тогда и только тогда, когда
$C^0_m+...+C^n_m>N$
http://e-science.ru/comment/348456#comment-348456
Ближе всех к нему был

Руст в сообщении #79798 писал(а):

Тогда вычисляем максимальное значение N для которого достаточно m ходов как сумму C(m,n)+C(m-1,n)+...=C(m+1,n).

,только написанное в конце равенство неверно