Гнилые помидоры (сложная)!
Модераторы: Азарапетыч, Администрация
-
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Гнилые помидоры (сложная)!
Многим знакома байка про мужика, евшего гнилые помидоры. Он купил килограмм помидоров, увидел, что один помидор подгнил, и съел его. На следующий день еще один помидор подгнил, он съел его. Он ел ровно по помидору в день, и в итоге питался исключительно гнилыми помидорами.
А теперь задача (придумалосб вчера).
Есть N помидоров, они гниют ровно по помидору в день, например, вечером. Гниение происходит одномоментно, перед этим никаких признаков начинающегося гниения нет, все помидоры одинаковы. Каждому помидору суждено сгнить в свой день, если он будет съеден раньше, в этот день никакой помидор не сгниет.
Мужик ест только свежие помидоры, выбирает один и ест, каждый день, утром, по помидору. А сгнивший (если такой есть) выкидывает. Для определенности считаем, что первым утром все помидоры свежие.
Вопрос: каково матожидание M(N) числа съеденных помидоров? То есть
интересно чему равен предел отношения M(N)/N?
Ясно, что M(N) больше N/2, так как половину помидоров он съест в любом случае (если он съел еще меньше N/2 помидоров, то остались несъеденные и несгнившие помидоры из второй половины, можно продолжать есть). В идеальном для него случае (с вероятностью 1/N!) он съест все помидоры (в каждый день он ест тот, который должен сгнить именно в этот день).
Что-то сразу не получается вывести общую формулу.
А теперь задача (придумалосб вчера).
Есть N помидоров, они гниют ровно по помидору в день, например, вечером. Гниение происходит одномоментно, перед этим никаких признаков начинающегося гниения нет, все помидоры одинаковы. Каждому помидору суждено сгнить в свой день, если он будет съеден раньше, в этот день никакой помидор не сгниет.
Мужик ест только свежие помидоры, выбирает один и ест, каждый день, утром, по помидору. А сгнивший (если такой есть) выкидывает. Для определенности считаем, что первым утром все помидоры свежие.
Вопрос: каково матожидание M(N) числа съеденных помидоров? То есть
интересно чему равен предел отношения M(N)/N?
Ясно, что M(N) больше N/2, так как половину помидоров он съест в любом случае (если он съел еще меньше N/2 помидоров, то остались несъеденные и несгнившие помидоры из второй половины, можно продолжать есть). В идеальном для него случае (с вероятностью 1/N!) он съест все помидоры (в каждый день он ест тот, который должен сгнить именно в этот день).
Что-то сразу не получается вывести общую формулу.
-
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
Так можно и запутаться...
Попробуем дискретизировать задачу. Пусть это не помидоры, а ящик с шариками с номерками внутри.
Пусть в полдень мужик достает из ящика случайный шарик и кладет его на полку, "обезвредив" его. А в 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.
Кажется, есть параллели с гномами...
А может, с сумасшедшей старушкой
Попробуем дискретизировать задачу. Пусть это не помидоры, а ящик с шариками с номерками внутри.
Пусть в полдень мужик достает из ящика случайный шарик и кладет его на полку, "обезвредив" его. А в 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.
Кажется, есть параллели с гномами...
А может, с сумасшедшей старушкой
-
- Акула пера
- Сообщения: 5768
- Зарегистрирован: 17 сен 2003, 00:07
- Откуда: СПб
-
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
Э-э-э... В смысле, недавняя задачка про то, как гномы героически спасались из комнаты с сундуками.Гном писал(а):Я пАпрАшу!Dendr писал(а):Кажется, есть параллели с гномами...
А может, с сумасшедшей старушкой
Что за параллели с гнилыми помидорами и сумасшедшими старушками?
А старушка - так, к слову пришлась.
-
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
-
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
Тьфу... Про вероятности забыл.Инна писал(а):Для небольших получается:
М(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!)
-
- Литератор-любитель
- Сообщения: 266
- Зарегистрирован: 08 июн 2006, 11:05
- Пол: Мужской
Эх, чо-та я совсем думать разучился...
Уже как что - открываю 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
Уже как что - открываю 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
Последний раз редактировалось molch64 03 дек 2007, 14:41, всего редактировалось 1 раз.
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!
-
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Спасибо. Жаль, что не две трети. Мне, как и Дендру, интуитивно тоже так казалось. Но все-таки интересно, что за число в пределе получается, именно формула. Ну никак не выводится.
Вот какая идея.
Рассмотрим П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)
Вот какая идея.
Рассмотрим П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)
-
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
-
- Популярный автор
- Сообщения: 2338
- Зарегистрирован: 24 сен 2007, 16:35
- Пол: Мужской
- Откуда: Мытищи
http://mathworld.wolfram.com/Golomb-Dic ... stant.html
http://en.wikipedia.org/wiki/Golomb-Dickman_constant
Дальше сами разбирайтесь )) И мне расскажите! Кстати ничего об этой константе на русском языке не нашел... ужас! Насколько я понял это предел числа перестановок An к n (при n стремящемся к бесконечности), только что такое n я не понял, вроде как не просто число элементов. Русского аналога для мат.понятия cycle я не нашел, поэтому жду ваших объяснений. Не удивлюсь если эта константа как раз после решения похожей (или этой же самой задачи ) и получила свое название и место в мат. мире.
http://en.wikipedia.org/wiki/Golomb-Dickman_constant
Дальше сами разбирайтесь )) И мне расскажите! Кстати ничего об этой константе на русском языке не нашел... ужас! Насколько я понял это предел числа перестановок An к n (при n стремящемся к бесконечности), только что такое n я не понял, вроде как не просто число элементов. Русского аналога для мат.понятия cycle я не нашел, поэтому жду ваших объяснений. Не удивлюсь если эта константа как раз после решения похожей (или этой же самой задачи ) и получила свое название и место в мат. мире.
Последний раз редактировалось Antananarivu 03 дек 2007, 21:32, всего редактировалось 3 раза.
Летим на Марс!
-
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
-
- Популярный автор
- Сообщения: 2338
- Зарегистрирован: 24 сен 2007, 16:35
- Пол: Мужской
- Откуда: Мытищи
-
- Литератор-любитель
- Сообщения: 266
- Зарегистрирован: 08 июн 2006, 11:05
- Пол: Мужской
Итак, пусть 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Инна Как предел численно нашла?
Обозначим как 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Инна Как предел численно нашла?
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!
-
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
-
- Литератор-любитель
- Сообщения: 266
- Зарегистрирован: 08 июн 2006, 11:05
- Пол: Мужской
А поподробней можна?Инна писал(а): Вывели несколько рекуррентных соотношений для частных случаев. Обобщили на общий случай без строгого доказательства, и рассчитали M(N) до 10 000.
З.ы. и совпадают ли значения M(6)...M(10) c моими, которые я считал брутфорсом?
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!