Смотрю на задачу 5: умею доказывать отличающиеся в константу раз оценки снизу и сверху.

Оценка снизу — верхней целой частью n-й частичной суммы гармонического ряда
H_n = 1+1/2+…+ 1/n.

Дело в том, что на возможных путях ниндзя есть случайное распределение, при котором на любом уровне все возможные круги посещаются равновероятно. Если поверить в то, что оно есть, то дальше среднее значение количества красных кругов на пути как раз равно 1+1/2+…+1/n (потому что вклад каждого уровня k равен 1/k). Ну и верхняя целая часть — потому что при таком среднем где-то будет хотя бы столько.

Построить такой путь можно двумя способами. Во-первых, взять равновероятно круг на самом нижнем уровне, и после этого выбрать идущий в него путь ниндзя равновероятно из всех возможных (и это не то же самое, что просто равновероятный выбор из всех 2^(n-1) путей ниндзя в треугольнике). И тогда оказывается, что на предыдущих уровнях распределение тоже равномерное.

Во-вторых, можно рассмотреть вот какой процесс: берём урну с одним красным и одним синим шаром, и раз за разом достаём из неё случайный шар -- возвращая его и ещё один такой же. И количества шаров и будут координатами -- иными словами, можно считать, что на красном шаре написано R, а на синем L.
Этот процесс называется "урна Пойя" -- можно сказать, что это самая простая модель раздела более-менее одинаковыми компаниями свежепоявившегося рынка: каждый новый покупатель спрашивает у случайного друга, чем тот пользуется, и берёт себе гаджет той де фирмы.

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

Хорошее упражнение -- это и убедиться в этом, и проверить, что эти две конструкции эквивалентны.