Задача достаточная простая. Интересно, насколько просто (коротко) можно изложить решение.

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

Имеется М штук одинаковых тарелок и здание высотой N этажей, при броске с крыши которого тарелка заведомо разбивается. Можно неограниченное число раз бросать тарелку с любого этажа, пока она не разбилась. Требуется найти минимальное число бросков для определения номера максимального этажа, при броске с которого тарелка не разбивается.

задан 1 Сен '13 22:33

изменен 1 Сен '13 22:33

А зачем дано ограничение на число тарелок? Вдруг их не хватит?

Я что-то подобное решала, поищу...
Вот, нашла. У меня есть решение для M от 1 до 3. Но там не так просто. Через рекуррентную формулу.

(1 Сен '13 23:45) DocentI

Их хватит. Если осталась лишь одна тарелка - ее можно бросить сначала с первого этажа, потом со второго... Когда разобьется, будем знать ответ.

(1 Сен '13 23:49) chameleon

Через рекуррентную формулу.

Ну да. Рекуррентную. Она мгновенно обобщается на N и М тарелок.

(2 Сен '13 0:02) behemothus
10|600 символов нужно символов осталось
2

Пусть $%f(N)$% -- искомое минимальное число бросков для $%N$%-этажного здания. Ясно, что $%f(1)=1$%, так как требуется проверить, разбивается ли тарелка при бросании с первого этажа. Удобно также положить $%f(0)=0$%.

Пусть $%N > 1$%, и первый раз тарелку бросили с $%k$%-го этажа. Если она не разбилась, то проверке подлежат $%N-k$% этажей, расположенных выше. Если разбилась, то $%k-1$% этажей, расположенных ниже. Одно из этих чисел не меньше $%\lceil\frac{N-1}2\rceil$%, где скобки означают округление до ближайшего целого в сторону увеличения. По смыслу задачи ясно, что функция $%f$% является неубывающей, откуда вытекает неравенство $$f(N)\ge1+f\left(\left\lceil\frac{N-1}2\right\rceil\right).$$ Отсюда по индукции нетрудно вывести неравенство $%f(N)\ge\lceil\log_2(N+1)\rceil$%. При $%N=1$% это очевидно, а при $%N > 1$% выполнено двойное неравенство $%2^{d-1}\le N < 2^d$%, где $%d=\lceil\log_2(N+1)\rceil$%, и при этом $%d\ge2$%. Из свойств неравенств легко следует, что $%2^{d-2}\le\lceil\frac{N-1}2\rceil < 2^{d-1}$%, откуда по предположению индукции получаем $%f(N)\ge1+(d-1)=d$%.

С другой стороны, для чисел вида $%N=2^d-1$% хватает $%d$% бросаний, если первую тарелку сбросить со среднего этажа. Отсюда следует, что полученная выше оценка точна, то есть при всех $%N$% имеет место равенство $%f(N)=\lceil\log_2(N+1)\rceil$%.

ссылка

отвечен 1 Сен '13 23:43

А как Вы учитываете число тарелок? Их может не хватить!

(1 Сен '13 23:46) DocentI

Да-да, без ограничения на кол-во тарелок эта задача становится слишком легкой.

(1 Сен '13 23:48) chameleon

falcao. Тепло. Но все проще.
Вы где-то не учитываете, либо то, что что тарелку можно использовать повторно, если она не разбилась, либо наоборот, считате, что можно бросать разбитую. Лениво искать, где вы "находите"или "теряете" единицу, но делить надо явно не пополам.

Если она не разбилась, то проверке подлежат N−k этажей, расположенных выше.

С этого момента - индукция и рекурсия.

(2 Сен '13 0:08) behemothus

Прошу прощения: я неправильно истолковал условие задачи. При ограничении на количество имеющихся тарелок всё обстоит, конечно, иначе.

(2 Сен '13 0:19) falcao

Да без проблем. Скажите лучше, что именно ввело Вас в заблуждение. Если действительно неоднозначность в условии - уточнения принимаются. Я писал с листа, уточняя "бытовуху".
Хотя то, что у Вас в решении М не присутствовало вовсе, меня сразу насторожило.

(2 Сен '13 0:27) behemothus

@behemothus: у Вас условие сформулировано совершенно корректно. Если меня что-то и сбило с толку, то характеристика задачи как "достаточно простой". Я подумал, что речь идёт о бинарном поиске, а вопрос состоял только в оформлении. Для общего случая задача с двумя параметрами, на мой взгляд, достаточно нетривиальна. Я, кстати, позже вспомнил, что для случая M=2 и какого-то конкретного N типа 100 когда-то с ней сталкивался.

(2 Сен '13 0:41) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
2

Мы давали вариант этой задачи на студенческой олимпиаде в 2010 году. Только у нас были стеклянные шарики. Я обрабатывала решения для издания (все олимпиады по 2010 г). Беру оттуда, не меняя:

Задача. Имеется k одинаковых стеклянных шариков. Их кидают с некоторых этажей 1000 этажного дома. Требуется за наименьшее число бросаний X определить самый нижний этаж, при бросании с которого шарики разбиваются (или убедиться, что таких этажей в доме нет). Вычислить X а) для k = 2; б) для k = 3.

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

Обозначим через $%p(k, n)$% максимальную этажность дома, для которого это можно сделать k шарами за $%n$% бросаний. Можно считать, что $%p(k, 0) = 0$%.
Рассмотрим сначала случай $%k = 1$%. Если мы бросим шарик хотя бы со второго этажа и он разобьется, то мы не узнаем, можно ли его было бросить с первого. Итак, один шарик надо бросать с 1-го, 2-го и так далее этажей, пока он не разобьется. Значит, $%p(1, n) = n$%.

Пусть теперь шариков больше, чем 1. Бросим первый шарик с этажа $%s_n$%. Если он разбился, то у нас остается $%k – 1$% шарик, $%n – 1$% бросок и $%s_n – 1$% непроверенных этажей. Значит, $%s_n – 1\le p(k –1, n – 1)$% и максимальное $%s_n = p(k –1, n – 1) + 1$%. В частности, $%s_1 = p(k –1, 0) + 1 = 1$%. Более высокие, чем $%s_n$%, этажи проверять не надо, так что $%p(k, n) \ge s_n$%.

Если же при первом бросании шар остался цел, то мы имеем в распоряжении еще $%(n – 1)$% попытку и снова $%k$% целых шара. За $%n – 1$% попытку мы можем проверить $%p(k, n – 1)$% этажей, начиная с номера $%s_n + 1$% (все более низкие проверять уже не надо). Поэтому мы можем определить нужный этаж во всем интервале от 1 до $%s_n + p(k, n – 1)$%.

Итак, $$p(k, n) = s_n + p(k, n – 1) = s_n + s_{n–1} + p(k, n – 2) = … = \sum_1^{n}s_i$$ Как мы показали выше, $%s_n = p(k –1, n – 1) + 1$%.

а) Пусть у нас есть два шарика. Имеем $%s_n = p(1, n – 1) + 1 = n$%. Тогда $%p(2, n) = \sum_1^n i =\frac{n(n+1)}{2}$%. Итак, за 44 броска можно проверить не более 990 этажей, а за 45 – уже 1035. Значит, 45 бросков хватит.

б) Для трех шариков имеем $%p(3, n) = \sum_1^n s_i $%, где $%s_i = p(2, i – 1) + 1 = \frac{i(i-1)}{2} + 1$%. Суммируя по i от 1 до n, получим $%p(3, n) = \frac16 (n^3 + 5n)$%. Поскольку $%\frac16(183 + 5\cdot 18) < 1000 < \frac16(193 + 5\cdot 19)$%, то $%X = 19$%.

Думаю, из этого решения легко сделать обще, для произвольных M и N.

ссылка

отвечен 2 Сен '13 0:28

изменен 2 Сен '13 0:36

Кстати, если кому интересно, вот ссылка на пособие по олимпиадам, там pdf-файл.

(2 Сен '13 0:32) DocentI

Гм... А в одну строчку можете написать? Идею алгоритма хотя бы? Если нет, я дам свое решение, за которое меня закидали тухлыми яйцами, а Вы оцените, насколько оно "зачотное", ОК?

(2 Сен '13 0:36) behemothus

Ключевая фраза - "Попробуем решить обратную задачу: по числу бросков найти этажность, для которой гарантированно можно определить самый нижний этаж разбития шаров.". Если Вы шли по тому же пути, то ваше решение "зачотное" ;)

(2 Сен '13 0:39) chameleon

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

Думаю, основная идея - оценивать число этажей через число бросков, а не наоборот. Ну, а формула рекуррентная выписана: $$p(k,n)=\sum_{i=1}^n(p(k-1,i-1)+1) = \sum_{i=1}^{n-1}p(k-1,i)+n$$ Я в этой задаче шла от чужого решения (отчасти). Может, с чистого листа получилось бы по-другому. Пишите ваше решение, посмотрим, интересно.

(2 Сен '13 0:41) DocentI

Чего им не понравилось? Объяснение или ответ? (или, может, у вас были до этого натянутые отношения? впрочем, меня это не касается)

Только то, что это был я. ))) На самом деле я совершенно равнодушен к славе (до мазохизма им. Перельмана), но вот собственная самооценка у меня резко выросла - и тут мне никто не помешает. Гордыня - страшный грех, но в моем положении это как глоток воздуха воздуха... Жить захотелось. Ладно, проехали. )))
Я никак не могу понять, как это вам удается так лихо с редактором формул управляться. Может и я теперь смогу?

(3 Сен '13 1:45) behemothus
10|600 символов нужно символов осталось
1

У этой задачи есть два варианта решения: житейский и математический.
Житейский: потребуется $%0$% бросков. Тарелка разобьется при броске с первого этажа. Ну ясно же :)
Математический: представим ответ в виде функции $%f(N,M)$%. После того, как бросим тарелку с $%k$%-го этажа, она либо разобьется и мы продолжаем поиск с $%(M-1)$%-й тарелкой среди $%(k-1)$% этажей, либо она не разобьется и поиск продолжим с $%M$% тарелок среди $%(N-k)$% этажей. То есть, $$f(N,M)=\min_k(1+\max(f(k-1,M-1),f(N-k,M)))$$ Функция $%f$% - неубывающая по $%N$%, следовательно оптимальное $%k$% - то, при котором $%f(k-1,M-1)=f(N-k,M)$%.
С одной тарелкой единственный выбор - бросать тарелку с нижнего этажа (нижнего из оставшихся), пока она не разобьется: $%f(N,1)=N$%.
Когда тарелок хватает на бинарный поиск, то это и есть оптимальный путь (см. решение @falcao): $%\left(M\ge\lceil\log_2(N+1)\rceil\right) \rightarrow \left(f(N,M)=\lceil\log_2(N+1)\rceil\right)$%.

Такое активное обсуждение, разговоры про рекуррентную формулу, поэтому отправляю пока это незаконченное решение. Пища для ума, так сказать.

ссылка

отвечен 2 Сен '13 0:09

Да. Вот это по первым строкам похоже на правильное решение.

Осталось сократить текст до необходимого минимума - и написать реккурентную формулу. Из неё следует алгоритм.

(2 Сен '13 0:14) behemothus

Ну, рекуррентная формула, можно считать, готова. $$f(N,1)=N$$ $$f(1,M)=1$$ $$f(N,M)=\min_k(1+\max(f(k-1,M-1),f(N-k,M)))$$ Но я всё ещё надеюсь, что от этого k можно избавиться :) У меня самого мозги уже немного сварены для этого.

(2 Сен '13 0:29) chameleon

Минимумы Вам зачем вообще? Запишите формулу для максимальной высоты здания, которую можно "решить" за М тарелок и К бросков.

(2 Сен '13 0:40) behemothus

Да, умная идея, но она уже записана выше, мне незачем пересчитывать это заново.

(2 Сен '13 0:47) chameleon
10|600 символов нужно символов осталось
0

Пусть N(K,M)- максимальная высота здания, которую можно "решить" за К бросков М тарелок.

После первого броска остается найти либо N(K-1,M) либо N(K-1,M-1), Отсюда

N(K,M)=N(K-1,M)+N(K-1,M-1)+1.
(Вырожденные случаи очевидны).

Всё. Если я, конечно, не выжил из ума...

Просто я "решил" эту задачу раньще чем дочитал (забыл только "в уме" единицу - и показалось, что там ряд Фиббоначи). Был на 100% уверен, что именно это и требовалось по задумке. Но то, что тут (и не только тут) понаписали, несколько поколебало мое самомнение... Но я таки не вижу, что тут не так...

ссылка

отвечен 2 Сен '13 1:03

изменен 2 Сен '13 2:02

Да, это правильно, только надо в рекуррентной формуле подправить второе слагаемое. Для величины $%N(k,m)$% справедлива при этом следующая формула: $$N(k,m)=C_k^1+C_k^2+\cdots+C_k^m.$$ А если мы знаем только $%N$% и $%M$%, то для числа $%k$% уже, скорее всего, не будет какой-то хорошей явной формулы.

(2 Сен '13 1:42) falcao

А зачем что-то подправлять? Логика нарушена? Если нет, то не вижу причин делать из простого сложное.
А зная N(К,M) для всех К,M, найти K(n,M) для конкретных n,M труда не составляет.

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


А! Там -1 была пропущена. Но это понятно, я поправил.
N(K,M)=N(K-1,M)+N(K-1,M-1)+1.
А вот откуда там выборки "из k по всё" - не понимаю.

(2 Сен '13 1:49) behemothus

Имелось в виду, что там была описка. Формула в виде суммы сочетаний сразу следует из приведённой Вами рекуррентной формулы, если рассуждать по индукции. Там надо использовать свойство треугольника Паскаля: $%C_k^m=C_{k-1}^{m-1}+C_{k-1}^m$%. Оно отличается отсутствием добавочного слагаемого, равного 1.

(2 Сен '13 2:08) falcao

А какая необходимость в таком упрощении? Никто ведь не ставит задачу довести до конкретного числа. Алгоритмическое решение за конечное число ходов... При желание можно, конечно и через сумму записать, но зачем? И если "упрощать" то оба слагаемых.... А, Вы хотите вообще без рекурсии записать, через сумму? Тогда да. И там действительно треугольник Паскаля. Это я ступил. Но я не ставил такой задачи. Вопрос был, будет ли понятно решение, записанное в две строчки. Спасибо, короче. Но если есть еще, что-то "вкусненькое" - давайте.

(2 Сен '13 2:16) behemothus

А численно ваша формула совпадает с другими предложенными?

Вообще эта задача очень странная, как задумаешься - в голове звон начинается. Пока не могу понять, почему два числа надо именно складывать, хорошо бы добавить какие-то слова.

(2 Сен '13 14:13) DocentI

@DocentI: да, формула совпадает с ответом. Получается нечто вроде треугольника Паскаля, но к двум соседним числам предыдущей строки добавляется ещё 1. Возникают суммы сочетаний. В Вашем решении было сначала $%k=С_k^1$% (при $%M=1$%), потом $%k(k+1)/2$% (при $%M=2$%), что есть $%C_k^1+C_k^2$%, а при $%M=3$% будет $%C_k^1+C_k^2+C_k^3$%, что как раз и есть $%k(k^2+5)/6$%. И так далее. Складываются числа потому, что находится максимальная этажность, а она равна максимальной этажности снизу и сверху, плюс один этаж, с которого бросили. Это максимум, которого можно достичь.

(2 Сен '13 15:20) falcao

DocentI, Не знаю, что тут еще добавить... Ну давайте так. Пусть в указанных обозначениях известна оптимальная стратегия. Делаем первый бросок с этажа L.

Пусть шарик разбился. Это значит, что осталось М-1 тарелка на К-1 бросков и k-1 этажей, которые ниже этажа L. Отсюда
L-1=N(K-1,M-1)....(1).

Пусть шарик не разбился. Это значит, что осталось М тарелок на К-1 бросков и N(K-1,M-1)-L этажей, которые выше этажа L. Отсюда
N(K,M)-L=N(K-1,M)....(2).
Исключая из (1) и (2) L, находим требуемое.

(2 Сен '13 15:25) behemothus

Хорошо! Жалко только, поздно исправлять уже изданный вариант пособия. Ну ладно, может будет переиздание, учту Ваше решение.

(2 Сен '13 16:16) DocentI

Не, вот это не обязательно.
На меня на русфорасе накинулись аки псы цепные за это решение, так что я их всех уже послал, выражений не выбирая. Так что меня уже всё вполне устраивает. О цвете розы со слепыми не спорят.

(2 Сен '13 16:44) behemothus

Чего им не понравилось? Объяснение или ответ? (или, может, у вас были до этого натянутые отношения? впрочем, меня это не касается)

(3 Сен '13 0:42) DocentI
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×317

задан
1 Сен '13 22:33

показан
2655 раз

обновлен
3 Сен '13 1:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru