Частичная сумма гармонического ряда ведёт себя как ln n (плюс константа \gamma, если хочется точнее). А сверху можно устроить оценку двоичным логарифмом: в каждой "группе горизонталей" ниндзя может зацепить максимум один красный шар b:
b
b.
..b
b...
..b..
....b.
......b
(Коллеги об этом уже написали аккуратнее)
Post #4293
2.44K
Математические байки Смотрю на задачу 5: умею доказывать отличающиеся в константу раз оценки снизу и сверху. Оценка снизу — верхней целой частью n-й частичной суммы гармонического ряда H_n = 1+1/2+…+ 1/n. Дело в том, что на возможных путях ниндзя есть случайное распределение…