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

[ViGOur]

У Мегамозга есть два одинаковых стеклянных шарика. За какое минимальное число бросков можно гарантированно определить, начиная с какого этажа 100-этажного здания шарики разбиваются? 1 и 2 правильными ответами не являются! Пишите решение.

[scoute]

Ухх ... чисто практически подобрал кое-что, возможно ошибаюсь , поправьте.

Значит 100 этажей лежат между рядами {1+2+3+..+13}(=91) <100<{1+2+3+..+14}(=105). ==> 91<100<105
То есть за 14 бросков можно осилить вплоть до 105 этажа.
Как же дело обстоит с 3 шариками, тут покруче ))

3 шарика за 9(!) бросков осиливают 100 этажный дом ... Итак, найдено подбором:
37,66,88,100. ... потом любое окно по 1-му методу. В этом случае 100 этажей не дают полной картины, т.к ряд немного длиннее:
37,66,88,104,115,122,126,128,129.
Однако вывести зависимость и построить ряд мне так и не удалось.
Если первый ряд геометрически похож на
 5_12.png ( 3.21 килобайт ) Кол-во скачиваний: 2

то есть для 12 этажей понадобится минимум 5 бросков. Что касается 3х шаров, представление типа
 5_13.png ( 1.07 килобайт ) Кол-во скачиваний: 1

катит, но с некоторыми нюансами. Допустим у нас 3 шара и 100 этажей.
Тогда в объёмную пирамиду
*10 ступени - влезет 220 шаров,
*9 ступени - влезет 165 шаров,
*8 ступени - влезет 120 шаров.
*7 ступени - влезет 84 шара.
Казалось бы, раз число 100 находится между 84 и 120, ответ - минимум надо 8 бросков. ОДНАКО
Но тут затаился один нюанс. Из числа шаров, которые влезают в объёмную пирамиду, надо вычесть
число шаров, которые влезают в ПЛОСКУЮ пирамиду, построенной на ступени "минус 1 шар",
поэтому ответ будет не 8, а 9.

Привожу ряды

1) 1,   2,   3,   4,   5,   6,   7,   8,   9,  10 - просто по порядку.
2) 1,   3,   6,  10,  15,  21,  28,  36,  45,  55 - числа для плоской пирамиды.
3) 1,   4,  10,  20,  35,  56,  84, 120, 165, 220 - числа для объёмной пирамиды.

4) 1,   3,   7,  14,  25,  41,  63,  92, 129, 175 - результат для 3х шаров.

Обратили внимание?
Каждый новый ряд получается путём прибавления к текущему числу следующего элемента предыдущего ряда, то есть:
 posled.png ( 1.81 килобайт ) Кол-во скачиваний: 4

А наш искомый ряд получается дополнительным вычитанием из текущего числа предыдущего элемента предыдущего ряда, то есть:
 posled2.png ( 2.03 килобайт ) Кол-во скачиваний: 4

Однако ПОЧЕМУ надо из объёмного ряда вычитать плоский, да ещё и со смещением, этого я, увы, объяснить не могу.
Есть предположения, что когда шара 3 а броска 2, то получается переизбыток шаров, который влияет на дальнейший ряд.
Видимо надо рассматривать больше примеров с большим количеством шаров, бросков и этажей.



Ещё есть идея про треугольники. Представим 2 треуголника в виде холма (пока без фиолетового маленького)
 geo1.png ( 1.15 килобайт ) Кол-во скачиваний: 7

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

Третий (фиолетовый) треугольник я пририсовал(но туда ли?) в надежде выявить зависимость для N количества шариков.
Единственное, что мне не нравится в треугольниках, это дробные числа в решении, которые потом надо округлять до целых, +1.
Вариант с шариками гораздо нагляднее и проще.

Возможно это ещё дифференциалами решается ... типо f(x)=f'(x)=f''(x)

Сообщение отредактировал scoute - 28.12.2009, 13:44