Многоэтажка со стекляшками

[iad58]

Вы все, наверное, эту головоломку знаете, это я не очень бываю в других соцсетях, но sabadel подсмотрела и мне рассказала:

Дан дом в 100 этажей и 2 яйца одинаковых стеклянных шарика. Каким наименьшим числом испытаний можно определить, какой самый высокий такой этаж, что шарик, сброшенный с него, уцелевает (соответственно самый низкий такой, что шарик, сброшенный с него, бьется)?

В числе 100, конечно, нет ничего примечательного, лучше решать задачу в общем случае.

Мне стало интересно также, с какого самого нижнего и с какого самого верхнего этажа можно сбросить первый шарик совершить первое сбрасывание шарика; для одного из этих чисел (но, похоже, только для одного) есть очень элегантная формула.

P.S. Еще, как подсказывают в комментах, интересно обобщить задачу на произвольное заданное количество шариков. Например, если в доме 2^k−1 этажей, а в руках k шариков, ответ находится за k попыток, причем первый шарик кидается с середины дома. А если в руках те же k шариков, но в доме 2^2k−1 этажей, ответ находится за 2k+1 попытку.

Лучше, пожалуй, задать задачу наоборот: если есть k шариков, какая наибольшая высота Ψ_k(n) дома, для которого за n попыток можно определить, где граница между зоной жизни и зоной смерти? Рекурсивный ответ:

Ψ_k(n) = 1 + Ψ_k−1(n−1) + Ψ_k(n−1), причем Ψ_k(1) = 1 ∀k, Ψ₁(n) = n ∀n.

Ψ1(n) = n	1	2	3	4	5	6	7	8	9	10	11	12
Ψ2(n) = n(n+1)/2	1	3	6	10	15	21	28	36	45	55	66	78
Ψ3(n) = n(n²+5)/6	1	3	7	14	25	41	63	92	129	175	231	298
Ψ4(n) = n(n+1)(n²-3n+14)/24	1	3	7	15	30	56	98	162	255	385	561	793
	1	3	7	15	31	62	119	218	381	637	1023	1585
	1	3	7	15	31	63	126	246	465	847	1485	2509
	1	3	7	15	31	63	127	254	501	967	1815	3301
	1	3	7	15	31	63	127	255	510	1012	1980	3796
	1	3	7	15	31	63	127	255	511	1022	2035	4016
	1	3	7	15	31	63	127	255	511	1023	2046	4082
	1	3	7	15	31	63	127	255	511	1023	2047	4094
	1	3	7	15	31	63	127	255	511	1023	2047	4095

Или Ψ_k(n) = n + ∑Ψ_k−1(1 : n−1).

Comments

[lj-frank-bot.livejournal.com]

Hello!
LiveJournal categorization system detected that your entry belongs to the category: Мода (https://www.livejournal.com/category/moda?utm_source=frank_comment).
If you think that this choice was wrong please reply this comment. Your feedback will help us improve system.
Frank,
LJ Team

[iad.livejournal.com]

Мода? Гм … с чего бы это?

[lj-frank-bot.livejournal.com]

Отлично

[chhwe.livejournal.com]

триггер: элегантная [формула]

[iad.livejournal.com]

А, вот оно что. Забавная тема — козлиное восприятие языка.

[linraen.livejournal.com]

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

[a-konst.livejournal.com]

Можно яйца заменить на одинаковые стеклянные шарики.

[iad.livejournal.com]

Хорошая мысль. Заменил.

[a-konst.livejournal.com]

Вы отдыхаете от филологии, занимаясь математикой?
Круто.

[a-konst.livejournal.com]

Второй вопрос странно поставлен. В каком смысле "можно"? и в каком смысле "первое"? Первую попытку?
Есть примерно один оптимальный алогритм, насколько я понимаю.
Он детерминирован - ну с точностью до того, что мы не знаем ответа заранее :)
В нем мы кидаем первое яйцо, пока оно не разобьется, потом кидаем второе - тоже, практически. пока не разобьется.
В рамках этого алгоритмся самый нижний этаж, скоторого мы начнем кидать первое, вычисляется - уж не знаю, насколько формула элегантна, но она есть.
Самый верхний, с которого нам, возможно, придется кидать первое яйцо - 100 этаж, максимльный. Тоже, конечно, очень элегантная формула :)

[iad.livejournal.com]

«Можно» в том смысле, что ищется стратегия, гарантирующая, что граница между верхним этажом жизни и нижним этажом смерти будет найдена, причем за наименьшее количество попыток. При этом может оказаться, что шарик бьется, даже будучи сброшенным с первого этажа, или уцелевает, даже падая с последнего.

Стратегия будет выглядеть так: первое сбрасывание шарика совершаем с такого-то этажа (или с одного из таких-то этажей), и если он бьется, дальше то-то, если нет — дальше то-то; так мы узнаем истину самое большее за столько-то попыток.

[a-konst.livejournal.com]

Спасибо, но я понимаю условие задачи, давно знаю саму задачу, и столь же давно ее решил.
Я уточнял формулировку второго вопроса.

[(Anonymous)]

Интересно еще решить задачу, когда шариков не два, а больше.