2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 
Сообщение27.09.2007, 20:56 
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$.

 
 
 
 
Сообщение27.09.2007, 21:02 
Аватара пользователя
Спасибо.

 
 
 
 
Сообщение28.09.2007, 09:19 
Аватара пользователя
Руст писал(а):
$m=[\frac{\sqrt{8N+1}+1}{2}]$

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

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

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

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

 
 
 
 
Сообщение28.09.2007, 11:10 
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.

 
 
 
 
Сообщение28.09.2007, 11:48 
Аватара пользователя
В общем случае обращать надо будет не это, но оно и без обращения красиво.
bot писал(а):
neo66 писал(а):
Забавно, правда, что 7 шариков (для 100 этажей) - минимизирует число испытаний

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

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

 
 
 
 Re: Стеклянные шарики
Сообщение07.09.2015, 20:59 
Аватара пользователя
См. также http://elementy.ru/problems/843/Obezyana_i_orekhi

 
 
 
 поддержим некропостинг)
Сообщение08.09.2015, 00:28 
Аватара пользователя
Известен такой простой ответ и решение: За $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).
,только написанное в конце равенство неверно

 
 
 [ Сообщений: 22 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group