Решение задачи про лапшу

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

Во всех остальных случаях кольцо не образуется, а число кусочков лапши просто уменьшается на единицу. Заметим, что и при создании кольца, число кусочков тоже уменьшается на единицу. Таким образом на следующем шаге уже будет (N-1) кусочек.

Общее число колец - это сумма по всем шагам. По линейности матожидания (очень популярная тема для задач!) то же самое можно сказать и про матожидание числа колец. Поэтому ответ на задачу - это сумма 1/(2i-1) по i=1..100; это примерно половина частичной суммы гармонического ряда, то есть что-то около половины логарифма двухсот.

Если эту сумму вычислить, получится примерно 3.28, а исходно интуиция подсказывала, что должно если не 50, то хотя бы 10. Поэтому и пришлось написать симуляцию.

Ссылка на код симуляции и точного вычисления: https://pastebin.com/Bkc0He62

У многих из вас интуиция намного точнее оказалась - про логарифм (и даже половину логарифма) написали несколько человек достаточно быстро.

#хеджфонды
@rybasharp