https://t.me/mathtabletalks/4292

коллега Клепцын обратил внимание на то, что в задаче 5 IMO-2023 на удивление хорошо работает вероятностная оценка:

будем выбирать случайный путь, делая шаг вправо-вниз из k-го круга на n-м этаже с вероятностью¹ k/(n+1) — тогда на каждом этаже вероятности попасть в любой из кругов одна и та же (проверьте!)

тогда матожидание числа задетых красных кругов равна 1+1/2+1/3+…+1/n, т.е. примерно ln(n) — значит, для любого треугольника существует путь, который проходит через ~ln(n) красных кругов

и эта оценка не далека от точной: разделим этажи на группы, в каждой группе этажи с номерами 2^(m-1),…,2^m-1, красным отмечены шары с номерами 1, 3, 5… — тогда любой путь проходит в каждой группе максимум по одному красному кругу, т.е. всего через ~log(n) красных кругов

===

¹ Такой случайный процесс — это урна Пойа (в начале в урне один шар «L» и один шар «R», на каждом шаге мы вытаскиваем из урны случайный шар, делаем в соответствии с ним ход, возвращаем в урну две копии такого шара). Про нее, и про другие модели с подкреплением рассказывал В.Клепцын на ЛШСМ-2018, https://mccme.ru/dubna/2018/courses/kleptsyn.html