Форум умных людей

A теперь намного более сложная задача (сам придумал):
Идёт посадка в самолёт, на который проданы все N билетов.
Где-то в очереди - сумасшедшая старушка, которая садится на свободное место случайным образом и где-то в очереди Джо... Каждый пассажир кроме старушки старается сесть на своё место, но если оно занято, садится на свободное случайным образом.
Какова вероятность что Джо сядет на своё место?

Если Джо - последний пассажир, то вероятность 1/2 ?

при N=2 - 3/4
N=3 - 7/9

Да, конечно.

Да.
Но надо - в общем случае :)

Да понятно :)

Спасибо, значит я правильно понял условие.

Будем решать :)

да тут дикая формула получится как на мое ИМХО

вер. = 1/2 + 1/2 * ( дикая формула )

Думаю вероятность всегда больше чем 1/2..

Половина случаев припадает на ситуацию, когда Джо впереди бабки на посадке и точняк займет свое место

Если пытаться решать в лоб - формула действительно дикая :)
А если подойти творчески? :)

в смыысле - у пассажира нет диареи??

Если он последний, то уже никаких случаев, когда он впереди бабки.
Мне кажется, я понял, о чем вы:
в ответе на данную задачу вероятность существенно (относительно N) больше 1/2.

последний он или нет - это частные случаи, а итоговый результат, вы правильно поняли - больше 1/2

Думаю, последним пассажиром теперь стоит считать человека в очереди перед Джо.
+ разобраться с положением бабки относительно Джо (вроде тоже 1/2 впереди-сзади, так ведь?)

Моя 1/2 как раз и учитывает положение Джо относительно бабки )) А другие версии задачи я не изучал, там где последний пассажир - главный герой, и происхождение тамошних 1/2 мне не известно))

N=4 - 19/24
N=5 - 321/400

а для Боинга 747?? :crazy:

N=4 - 115/144
N=5 - 263/300

Ну так как? Какие будут соображения?  :tianchik:

с диареей??

Наболело? :zzz:

Можно уже было и заменить знак припинания.

Мне кажется, что задача в усложнённом варианте достаточно интересна и даёт почву для творчества.
Впрочем, никому ничего я не навязываю.

умные все



просто расклад такой


сели почти все и вот только тут диарея

Я вижу, она Вас окончательно замучила :(

действительно, интересная)
мне кажется, чтобы не строить сумасшедших формул нужно постараться просто отбросить всё лишнее, и останется то, что нужно ;)
впрочем, это не так уж и просто))

Надо сначала решить более простую задачу. Но тоже в общем случае :)

Может автор уже даст свое решение?
У меня вообще получилось для

4 - 115/144
5 - 163/200

хотя считал примерно, в уме и без проверки на бумаге. Где правда?

не пойму, как получилась вероятность 7/9 для Джо при 3 пассажирах ???
у меня получается вероятность для Джо 3/4 как при N=2, так и при N=3,
а именно (для N=3):
всего вариантов размещения старушки (С) между Джо (Д) и пассажиром (П) имеется шесть:
1)2)3) ДСП/ДПС/ПДС - это варианты, когда С размещается позади Д и для Д вероятность в этих случаях равна 1 или суммарно 1/2 для 3 вариантов из 6 возможных
4) СДП - вероятность для Д равна (1/2*1/3)*(2/3)=1/9 - т.к. С может с вероятностью 2/3 занять либо свое место (1/3), либо место П (1/3), т.о. вероятность в этом случае для Д занять свое место будет аналогичной (2/3)
5) ПСД - вероятность для Д равна (1/2*1/3)*1/2=1/12 - где 1/2 - вероятность для С занять свое место, либо место Д
6) СПД - вероятность для Д равна (1/2*1/3)*2/3*1/2=1/18, где 1/2 - вероятность для П занять место С, либо место Д, при условии, что С заняла место П

зы: возможно где-то накосячил в расчетах.. :wall:

нашел ошибку: в 6) варианте вер-ть 1/12, т.о. суммарная - 7/9, все верно

если рассматривать 14 РАВНОВЕРОЯТНЫХ (?) событий, благоприятных - 6:
P(3) = 6/14= 3/7

по другому:
если рассмотреть 6 РАВНОВЕРОЯТНЫХ (!) последовательностей вариантов входа в самолёт:
P(3) = 1/6 * (1/4 + 1/2 + 1/2 + 1 + 1 + 1/4)  = 7/12

Голосую за ответ:  P(3) = 7/12

willi, мне кажется, что имеет место лишь три различных события:
1) Д впереди С (вероятность 1/2 - для половины всех N! возможных вариантов перестановок)
2) Д последний (вероятность1/2 - для N!/N вариантов)
3) Д не в конце, но где-то позади С (вероятность можно посчитать как-то тоже через N! (подумаю) - для ((N!/2)-(N!/N)) вариантов)

зы: вот как-то так..

Даю совет.
Показать скрытый текст

Суровая старушка переполошила все аэропорты мира

Варианты: ДСП и ДПС
ДСП:
тогда С на своём месте с вероятност'ю 1/2 (удачно сели)

ДПС:
тогда П на своём месте с вероятност'ю 1 (удачно сели)

Итого 1) 1/2 * (1/2 + 1) = 3/4

Варианты: СПД и ПСД
СПД:
тогда С на своём месте с вероятност'ю 1/3 (удачно сели)
и С не на своём месте с вероятност'ю 2/3 (не удачно сели)

ПСД:
тогда С на своём месте с вероятност'ю 1/2 (удачно сели)

Итого 2) 1/2 * (1/3 + 1/2) = 5/12

тол'ко вариант: СДП подходит

тогда С на своём месте с вероятност'ю 1/3 (удачно сели)
и С не на своём месте с вероятност'ю 2/3 (не удачно сели)

Итого 3) 2/3

Не хватает варианта ПДС.
его вероятност' 1/6

Не знаю зачем Вы об'единили некоторые варианты, а некоторые оставили поразен'.

по моему моя табличка намного удобнее показывает все возможные варианты и все возможные вероятности.

вилли, я рассматриваю усложненный вариант, предложенный букой. надеюсь, ты тоже?
если да, то тогда в любом варианте ДПС или ДСП вероятность для Д сесть на свое места составляет 1, и не важно, что там дальше происходит между С и П. т.е., в 3 вариантах из 6 вероятность 1, а в целом - 1/2 для половины всех возможных случаев.
 
зы: или я чего-то не понимаю в твоем комментарии..

бука, спасибо за совет, но пока что я только еще более запутался, может завтра соберу мысли в кучу :roll:

вилли, при ПДС вероятность такая же, как при ДСП и ДПС, т.е.1) событие, т.к. С идет уже за Д и никак не может ему помешать сесть на свое место. равно как и П не мешает Д.
на счет удачно/неудачно сели - завтра вчитаюсь, сегодня просто нет ни сил, ни времени. кстати, и табличку рассмотрю внимательнее ;)

Я могу дать дальнейшие подсказки

бука, просто чуть времени не хватает, и не все складывается
например, для Джо при 3 я считал так:
1/3*1+(1/3*1/2*1+1/3*1/2*2/3)+1/3*1/2=1/2+1/6+1/9=14/18=7/9
а для 4 если считать аналогично, то у меня не получается:
1/4*1+(1/4*1/2*1+1/4*1/2*3/4)+(1/4*1/2*1+1/4*1/2*2/3)+1/4*1/2=чему-то, но не 115/144.
хотя, если считаю аналогично через количество вариантов, то получаю:
1/2+(2*3/4+4*2/3)*(1/24)+1/8=115/144
не понимаю, где ошибаюсь..
что до вопроса  - какой будет вероятность конкретно для предпоследнего пасажира, то имхо 2/3

но проблема даже не в расчетах. для каждого конкретного N возможно так или иначе просчитать. но пока не получается свести все расчеты в единую формулу. т.е., для Джо первый - 1/N, для Джо последний - 1/2, а для Джо от (2) до (N-1) не понятно пока как устаканить.. :roll: :beer:

зы: пока что пытаюсь играться стаканами.. :girldrink:

(http://mathurl.com/4kxcngl.png)
Вроде так, если не ошибся.
Это вероятность, что Джо НЕ займет свое место.

Димыч, вопрос в том - какая вероятность, что займет..  ;)

зы: а что есть k? или вы о размещениях ведете речь?

Не, вероятность что займёт равна 1 - вероятность, что не займёт :)
Я формулы скрупулёзно не проверял, но судя по подходу в параллельной теме, ответ правильный.
Но вся прелесть имхо - не в ответе, а в рассуждениях :)

k - это переменная для вычисления регулярной дискретной последовательности, в данном случае суммы от k равно 1 до N-1 где слагаемые - функции от этого k

buka, так вероятность что сядет, или что не сядет (займет/не займет)?? вы уж определитесь, плз :)
и как вероятность того, что джо займет свое место может быть равна 1?  ???
зы: запутали вы меня совсем.. >:(  :D

Смит, какая разница?
Если вы нашли одно, то другое будет разностью 1 и этого числа, о чем вам и сообщил buka

прошу прощения, я просто ступил. прочел фразу, написаную букой, примерно как: "Не.. Вероятность того, что сядет равна 1, - Нужно найти вероятность, что не сядет". просто не проснулся в тот момент, вероятно.
но это мелочи, дело не в этом. я полагал, и полагаю, что формула должна позволять напрямую посчитать вероятность для Джо. при, например, 257 пассажирах.
но мне нужна помошь - где я не правильно считаю для Джо (сядет) при 4-х пассажирах:
1/4*1+(1/4*1/2*1+1/4*1/2*3/4)+(1/4*1/2*1+1/4*1/2*2/3)+1/4*1/2 не равно 144 :(
здесь 1/4 - вероятность того, что Джо войдет первым, вторым третьим или четвертым, 3/4 2/3 и 1/2 - вероятности, что Джо сядет, если старушка войдет впереди него, а 1 - что джо сядет если войдет первым.
если победю для 4 и 5 и совпадет с букой ответы - думаю я смогу вывести функционально более простую формулу, но пока вот с этим засада((

Даю решение.
//скрытый текст, требуется сообщений: 100//

Димыч, можете решить для Джо при 4-х пассажирах? или показать ошибку в моих вычислениях. рассуждений у меня самого выше крыши  :)
нужно конкретно: для 4 и 5. потом - универсальная формула. потом Занавес. :laugh:

Смит, вероятности что старушка войдет до/после Джо не равны 1/2, а зависят от того, каким он войдет.

Димыч, у вас есть решение для 4?
я думал над тем, что не равны. тогда как распределяются, для 4 например? 1/4 что Джо войдет первым, и с вероятностью 1 сядет на свое место, ТАК?
1/4, что Джо войдет вторым, тогда с вероятностью (какой?) он войдет после старухи и с вероятностью 3/4 сядет на свое место. либо с вероятностью (какой??) войдет впереди С и сядет на свое место с вероятностью 1.
так?

Вероятность должна стремиться к единице с возрастанием N

А что, Вакула - это Смит?
Димыч правильно решил, но мне кажется, что не всем его решение понятно.
Если будут желающие получить более детальное объяснение, я дам.

нет, но тоже кузнец ;)

1/2 + [1/2*(N!/N)+2/3*k1+3/4*k2+...+((n-1)/n)*kn]/n!
при:
2 - 3/4 (k1=k2=...=kn=0)
3 - 7/9 (k1=1; k2=...=kn=0)
4 - 115/144 (k1=4; k2=2; k3=...=kn=0)
5 - 163/200 (k1=18; k2=12; k3=6; k4=...=kn=0)
...
N - xz? ???

с серединкой пока не разобрался, но спать стал уже лучше, ночью дроби почти не снятся :)

а вы как думаете?  :-\

бука, можно узнать Ваше решение в общем виде? похоже больше вариантов не будет

подожди :)


если что - под спойлер.

Димыч дал формулу, респект и все такое, но она скорее описательная, что ли - как по ней считать, и можно ли - мне непонятно  :tormoz:

ОК, сегодня-завтра выложу.

1. Определим вероятность того, что в N-местном самолёте, где все места проданы, предпоследний (в очереди на посадку) пассажир (Д) сядет не на своё место при наличии в очереди сумасшедшей старушки (С).
1.1 Старушка может в очереди быть на одном из N-1 мест.
Вероятность того, что она за Д Рдс = 1/(N-1), а что перед Д: Рсд = (N-2)/(N-1)
1.2. Если старушка за Д, то Д сядет на своё место безусловно,
поэтому определим условную вероятность Рн того, что Д не сядет на своё место в ситуации СД
Где бы С не была бы в очереди перед Д, вероятность того, что место Д будет занято в два раза меньше вероятности того, что С займёт своё место или последнего.
А если старушка займет какое-то другое, промежуточное место кроме перечисленных (Х), то это автоматически (с вероятностью = 1) означает, что появится "аналогичная старушка" с тем же поведением и с тем же соотношением вероятностей (СВ), равным 1:2.
Поэтому промежуточные состояния не интересны - они не меняют СВ и к конечному состоянию КС (Место Старушки или Место Джо или Место Последнего) мы придём с вероятностью = 1.
Следовательно, Рн = 1/(1+2) = 1/3, а общая вероятность Р = Рсд * Рн = (N-2)/(N-1) * 1/3
2. Если таким же образом решить задачу для пред-предпоследнего пассажира, получим:
P = (N-3)/(N-1)*1/4
3. Если решить эту задачу для К-го с конца пассажира (последний - 1-й с конца, предпоследний - 2-й и т.д.), получим:
P = (N-K)/(N-1)*1/(K+1)
4. Tеперь остаётся решить нашу задачу, учитывая, что наш Д может с равной вероятностью 1/N быть последним, предпоследним,...,К-ым с конца,...,первым, просто просуммировав N членов типа 1/N * (N-K)/(N-1)*1/(K+1)
Займёмся суммированием. Но я не умею, как Димыч, изображать сигму и потому буду где не могу обходиться как-то по-другому, надеюсь, поймёте.
4.1 Постараемся преобразовать наш К-й член, чтобы суммировать было легче.
Итак, P_K = 1/N * (N-K)/(N-1)*1/(K+1) = 1/(N*(N-1)) *(N-K)/(K+1) =
= 1/(N*(N-1)) *(N-K+1-1)/(K+1) = 1/(N*(N-1)) *((N+1)-(K+1))/(K+1) =
= 1/(N*(N-1)) *((N+1)/(K+1) - 1)
А это, в свою очередь, тоже можно преобразовать, раскрыв скобки и перегруппировав:
1/(N*(N-1)) *((N+1)/(K+1) - 1) = (N+1)/(N*(N-1))*1/(K+1) - 1/(N*(N-1))
В таком виде просто легче суммировать: надо получить отдельно сумму вычитаемых, затем вычитателей и из первой суммы вычесть вторую.
Сумма вычитателей находится банально просто - сумма N одинаковых членов 1/(N*(N-1)) равна 1/(N-1) - здесь всё просто.
4.2 Теперь - о сумме вычитаемых.
Нам надо получить сумму N последовательных обратных величин от 2 (К = 1) до N+1 (K=N).
При больших N: 1/1 + 1/2 + 1/3 + ... + 1/(N+1) стремится к ln(N+1), значит наша сумма стремится к (ln(N+1) - 1)
Таким образом, общая (суммарная) вероятность:
 Рс =~ (ln(N+1)-1)*(N+1)/(N*(N-1) - 1/(N-1) ~< lnN/N -> 0.
Значит, вероятность того, что Джо не сядет на своё место с ростом N стремится к нулю, т.е. то, что он сядет на своё место стремится к достоверности. :)

обдумываю это  :wall:
и вообще - все вами написанное. где-то несогласен, или не понял (или просто неудовлетворен). где - пока не знаю. в любом случае интересно и спасибо за удовольствие  :show_heart:

солидарны с buka'й?

зы: кстати, все, кому интересно

Я так полагаю, что это решение не исходной задачи, а опубликованной где-то по середине. Можете условие переписать

да. момент

а, так, сорри, топик уже подредактировали, и теперь собственно весь топик - это обсуждение той самой задачи. о которой последний сабж буки. ну и вообще все об этом.

зы: изначально в задаче спрашивалось - какая вероятность последнему пассажиру 9любому) сесть на свое место при наличии сумасшедшей старушки

зызы: там было доказано 1/2

У меня получилась вот такая формула

[1/2 + 2/3 + 3/4 + 4/5 + ... + (N - 1)/N]*(1/N)*(1/2) + 1/2

А с каких N работает эта формула?

Да. Немножко наврал
[1/2 + 2/3 + 3/4 + 4/5 + ... + (N - 1)/N]*(1/(N-1))*(1/2) + 1/2

та все равно
У меня без всяких формул при N=3 - 7/9
А по формуле - 19/24

Да. Она ещё позаковырестей
1/2 + 1/(N*(N-1))*[1/2*(N-1)+2/3*(N-2)+3/4*(N-3)...+(N-1)/N*1]

zhekas, у меня тоже есть варианты
http://nazva.net/forum/index.php/topic,5227.msg122824.html#msg122824
или 1/2 + [1/2*(N!/N)+2/3*k1+3/4*k2+...+((n-1)/n)*kn]/n!

вопрос в том - согласны ли Вы с изложением решения буки? я - не уверен здесь:
то ли неверно высказывание, то ли не верно. что это высказывание определяет решение задачи (небыло времени разобраться пока, но имхо что-то тут не так)

просчитайте вашу формулу для 3, 4, 5... сходится с моими данными, приведенными здесь:

http://nazva.net/forum/index.php/topic,5227.msg122824.html#msg122824

кроме 4. там у меня  115/144

у меня там тоже 115/144, то описка в той ссылке, что я дал, уже исправил... теперь вопрос в номинальном решении в общем виде
зы: бука дал.. ???

вообще, это его (буки) задача, и если он считает что она решена - это его право. просто мне интересно - есть ли общая формула для расчета вероятнсти для Джо при любом N

Хорошо, давайте рассуждать.
Старушка зашла в самолёт. У неё - куча возможностей. Из всех этих возможностей выделим следующие группы мест: место Джо (Д), места пассажиров, которые в очереди после Джо (ПД), место старушки (С) и места пассажиров, которые в очереди впереди Джо, но после старушки (ВДПС) - согласитесь, мы перечислили ВСЕ возможности для старушки.
Допустим теперь, что все ВДПС куда-то испарились - тогда вероятность того, что Джо не сядет на своё место:
P_-= Д/(ПД + Д + С) = 1/(ПД + 1 + 1)
С этим, надеюсь Вы согласны. При этом заметьте, что на какое бы место из Д, ПД и С старушка бы не села, - по отношению к Джо всё оканчивается, т.е. ПД,Д,С - конечное состояние для Джо.
Но ВДПС никуда не испаряется и старушка может сесть и на одно из мест из ВДПС. Но тогда - с вероятностью 1, то есть неминуемо появится ещё одна "старушка" - тот пассажир, из ВДПС, чьё место заняла старушка и перед ним/ней будет та же задача и т.д., то есть вероятность того, что в этой цепочке на каком-то этапе будет выбор из ПД,Д,С равен 1 независимо от того, испарились ВДПС или нет.
Поэтому ВДПС нас вообще не интересуют :)

Я дал эту формулу.
Сумма гармонического ряда не имеет элементарного выражения, как, например, в случае с арифметической и геометрической прогрессией :)
1 + 1/2 + 1/3 + 1/4 + ... + 1/K + ... + 1/N нельзя получить как элементарную функцию от N, но для больших N она близко подходит к lnN (или lnN + 1, уже не помню :) )