Гнилые помидоры (сложная)!

[Инна]

Многим знакома байка про мужика, евшего гнилые помидоры. Он купил килограмм помидоров, увидел, что один помидор подгнил, и съел его. На следующий день еще один помидор подгнил, он съел его. Он ел ровно по помидору в день, и в итоге питался исключительно гнилыми помидорами.

А теперь задача (придумалосб вчера).

Есть N помидоров, они гниют ровно по помидору в день, например, вечером. Гниение происходит одномоментно, перед этим никаких признаков начинающегося гниения нет, все помидоры одинаковы. Каждому помидору суждено сгнить в свой день, если он будет съеден раньше, в этот день никакой помидор не сгниет.
Мужик ест только свежие помидоры, выбирает один и ест, каждый день, утром, по помидору. А сгнивший (если такой есть) выкидывает. Для определенности считаем, что первым утром все помидоры свежие.

Вопрос: каково матожидание M(N) числа съеденных помидоров? То есть
интересно чему равен предел отношения M(N)/N?

Ясно, что M(N) больше N/2, так как половину помидоров он съест в любом случае (если он съел еще меньше N/2 помидоров, то остались несъеденные и несгнившие помидоры из второй половины, можно продолжать есть). В идеальном для него случае (с вероятностью 1/N!) он съест все помидоры (в каждый день он ест тот, который должен сгнить именно в этот день).

Что-то сразу не получается вывести общую формулу.

[Dendr]

Так можно и запутаться...
Попробуем дискретизировать задачу. Пусть это не помидоры, а ящик с шариками с номерками внутри.
Пусть в полдень мужик достает из ящика случайный шарик и кладет его на полку, "обезвредив" его. А в 6 часов вечера шарик с номером, который совпадает с номером текущего дня - он должен быть наименьшим, что важно - взрывается (не повреждая остальные, однако). Шарики на полке не взрываются, ибо "обезврежены".

Пример 1. N=2. Будем "именовать" варианты буквами, даже рядами букв, если потребуется.
День 1. 12:00.
А. мужик достал шарик с номером 1. Остался шарик №2
Б. мужик достал шарик №2. Остался шарик №1
День 1. 18:00. Должен взорваться шарик №1.
А. Взрыва не происходит. Остался шарик №2.
Б. Взрывается единственный шарик. Ничего не осталось.
День 2. 12:00
А. Мужик достает шарик №2. Ничего не остается. На полке 2 шарика.
Б. В ящике пусто. На полке 1 шарик.
Среднее число шариков - 1.5. Относительное - 0.75. Дейтствительно, больше 0.5

Пример 2. N=3.
День 1. 12:00
А. Вынут 1. Осталось 2,3.
Б. Вынут 2. Остались 1,3.
В. Вынут 3. Остались 1,2.
День 1. 18:00. Должен взорваться 1.
А. Взрыва нет. Осталось 2,3.
Б. Взрыв. Остался 3.
В. Взрыв. Остался 2.
День 2. 12:00.
АА. Вынут 2. Остался 3.
АБ. Вынут 3. Остался 2.
Б. Вынут 3. Не осталось ничего. На полке два шарика.
В. Вынут 2. Не осталось ничего. На полке два шарика.
День 2. 18:00. Должен взорваться 2.
АА. Взрыва нет. Остался 3.
АБ. Взрыв. Не осталось ничего. На полке два шарика.
Б. На полке два шарика.
В. На полке два шарика.
День 3. 12:00.
АА. Вынут 3. Не осталось ничего. На полке три шарика.
АБ. На полке два шарика.
Б. На полке два шарика.
В. На полке два шарика.
Видно, что 4 варианта. 2+2+2+3 / 4 = 2.25 вынуто в среднем. Относительно - 2.25/3=0.75.

Для N=4 не буду подробно расписывать тут. Напишу сводку.
2 случая - два вынутых шарика.
7 случаев - три вынутых.
1 случай - 4 вынутых.
В среднем: (2*2+7*3+1*4)/10=2.9.
Относительно: 0.725.

В общем случае, видимо, распределение будет следующим:
Один случай - когда все шарики вынуты (это если доставать все по порядку).
Ммножество случаев - когда вынута ровно половина (это если доставать в произвольном порядке шарики с большими. Это (N/2)! случаев.
Будут и промежуточные, но их оценить сложнее... Да еще максимум посередине... Интуитивно - стремится к 2/3.

Кажется, есть параллели с гномами...
А может, с сумасшедшей старушкой

[Гном]

Кажется, есть параллели с гномами...
А может, с сумасшедшей старушкой

Я пАпрАшу!
Что за параллели с гнилыми помидорами и сумасшедшими старушками?

[Dendr]

Кажется, есть параллели с гномами...
А может, с сумасшедшей старушкой

Я пАпрАшу!
Что за параллели с гнилыми помидорами и сумасшедшими старушками?

Э-э-э... В смысле, недавняя задачка про то, как гномы героически спасались из комнаты с сундуками.
А старушка - так, к слову пришлась.

[Инна]

Для небольших получается:
М(2)=3/2,
М(3)=13/6
М(4)=67/24
М(5)=411/120 (это не перепроверяли).

[Dendr]

Для небольших получается:
М(2)=3/2,
М(3)=13/6
М(4)=67/24
М(5)=411/120 (это не перепроверяли).

Тьфу... Про вероятности забыл.

Да, для М(5) действительно 411/120: 3 помидора (шарика) с вероятностью 70/120, 4 - 49/120, 5 - 1/120.

Вообще, что точно можно сказать - N будет с вероятностью 1/(N!)

[molch64]

Эх, чо-та я совсем думать разучился...
Уже как что - открываю Exel и пишу макрос...
Эээх...

P.S> 1,2,3,4,5 - подтвержаю вышеприведенные резалты.
В скобках - M(N)/N

M(6)=2921/720 (0,676157407)
M(7)=23633/5040 (0,669869615)
M(8)=214551/40320 (0,66515067)
M(9)=2160343/362880 (0,661480685)
M(10)=23897269/3628800 (0,65854467)
M(11) не посчитал ибо долго а оптимизировать прогу лень;)

Upd:
M(11)=288102189/39916800 (0,656142479) - 10 минут считалось;)\

Вывод - ответ не 2/3

Ради шутки: pi/4=0,636619772

[Инна]

Спасибо. Жаль, что не две трети. Мне, как и Дендру, интуитивно тоже так казалось. Но все-таки интересно, что за число в пределе получается, именно формула. Ну никак не выводится.
Вот какая идея.
Рассмотрим П1 - помидор, сгниющий первым, П2 - вторым и т.д..
р(Пк) - пусть вероятность того что к-й помидор будет съеден.
Нетрудно убедиться, что при достаточно больших N
р(П1)=1/N - первому помидору быть съеденным с вероятностью 1/N
p(П2)=1/N+1/(N-1)
p(П3)=1/N+1/(N-1)+1/(N-2)
.....
Вроде, какое-то время эта формула работает, а потом перестает.
.....
р(П(N-1))=1-1/N!
р(ПN)=1 - последний помидор будет съеден всегда.

Эти формулы могут пригодиться, так как, вроде
M(N)=р(П1)+р(П2)+...+р(ПN)

[Инна]

Обработали на компьютере.
Предел получился равным

M(N)/N --> 0.6243299...
Все цифры верные. Но что это за число?

[Antananarivu]

http://mathworld.wolfram.com/Golomb-Dic ... stant.html
http://en.wikipedia.org/wiki/Golomb-Dickman_constant
Дальше сами разбирайтесь )) И мне расскажите! Кстати ничего об этой константе на русском языке не нашел... ужас! Насколько я понял это предел числа перестановок An к n (при n стремящемся к бесконечности), только что такое n я не понял, вроде как не просто число элементов. Русского аналога для мат.понятия cycle я не нашел, поэтому жду ваших объяснений. Не удивлюсь если эта константа как раз после решения похожей (или этой же самой задачи ) и получила свое название и место в мат. мире.

[Инна]

Браво, Antananarivu.
Это - действительно оно. Число, означающее матожидание длины наибольшего цикла, деленное на размер перестановки.
Но как эту модель построить на нашей задаче?

[Antananarivu]

Ясно. Жаль что я совсем забыл высшую математику и теорию вероятностей в частности... ничем не могу вам помочь.

[molch64]

Итак, пусть M(N)/N - это матожидание съеденных помидоров
Обозначим как A(N)/N - матожидание наибольшего цикла.

Ну, N отбросим чтоб не мешалось и будем выписывть первые значения.

1: M(1)=A(1)=1
2: M(2)=A(2)=3
3: M(3)=A(3)=13
4: M(4)=A(4)=67
5: M(5)=A(5)=411

Гипотеза понятна?



А вот фиг!!!!

6: M(6)=2921 A(6)=2911 delta=10
7: M(7)=23633 A(7)=23563 delta=70
8: M(8]=214551 A(8]=213543 delta=1008
9: M(9)=2160343 A(9)=2149927 delta=10416
10: M(10)=23897269 A(10)=23759791 delta=137478

Так что обламывается моделька пока что

P.S> прощу прощения M(11) было посчитано неверно, ща пересчитываю. Все остальное - верно (массив недоопределил до 11 бблин)

P.P.S> Это несоответствие A(N) и M(N), начиная с N=6, я так же завтра на свежую голову перепроверю.

P.P.P.S> 2Инна Как предел численно нашла?

[Инна]

P.P.P.S> 2Инна Как предел численно нашла?

Вывели несколько рекуррентных соотношений для частных случаев. Обобщили на общий случай без строгого доказательства, и рассчитали M(N) до 10 000.

[molch64]

Вывели несколько рекуррентных соотношений для частных случаев. Обобщили на общий случай без строгого доказательства, и рассчитали M(N) до 10 000.

А поподробней можна?

З.ы. и совпадают ли значения M(6)...M(10) c моими, которые я считал брутфорсом?