Несложная логическая задачка

[vak]

Мне тут надысь задачку подсунули, которую я слёту не смог решить. Дано: небоскрёб высотой 100 этажей и две бутылки водки. Требуется определить этаж, с которого бутылка, выброшенная в окно, разбивается. За минимальное количество попыток, естественно.

Есть верные решения от maugletta, trustix, chtovimenitebe, skolk, ircicq, denis_iv. А parovoz и dadv дали общую формулу для N этажей.

spamsink предложил идею решения для N этажей и K бутылок.

Comments

[kondybas.livejournal.com]

Да начать с первого и подниматься. Пока бутылка не бьется - ее можно "повторно использовать"(с)
Как разобьется - вторую с горя оприходовать.

[vak]

Это ж сколько вверх-вниз бегать, да еще с грузом за пазухой. :)

[kondybas.livejournal.com]

Самое смешное то, что схожий случай линейной оптимизации я когда-то основательно штудировал и даже статьи публиковал...

Мы имеем O(n)=(100/m/2)+(m/2)=(100+m^2)/2m
Производная O'(n)=1/2 * (-100+m^2) / m^2
Производная обращается в ноль при m=10

Эрго, минимальное количество проб будет при тестировании первой бутылки с шагом в 10 этажей, а второй - с шагом в один этаж. Матожидание будет где-то так примерно сэм-восэм десять проб...

[vak]

Это при равномерном шаге оптимально 10. Но можно идти с уменьшающимся шагом.

[kondybas.livejournal.com]

А вот здесь самое время проанализировать матожидание количества попыток при уменьшающемся шаге!
При равномерном шаге мы получим вполне себе симметричную гауссиану в интервале от 1 до 18. А вот при уменьшающемся шаге распределение будет существенно асимметричным вправо, и в каком положении окажется мода я затрудняюсь навскидку сказать. При равномерном она оказывается равной не 10 (это я ошибся) а 9. Без учета асимметрии переменный шаг якобы дает моду=7, но что-то я сомневаюсь...

Надо будет на досуге посчитать.