турнир-теорвер

Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 24 18:58:52 по местному времени:

Привет, Alexander!

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

AН> Только что проводил гостей, было не до детских задачек, решали
AН> взрослую: сочиняли датчик противопожарной сигнализации. Если
AН> интересно, могу рассказать.

А мне было любопытно :-). Доказал, что вероятность выиграть первые k партий не меняется с увеличением числа участников. Оказалось самой интересной частью задачи ...

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)

Alexander Hohryakov написал(а) к Sergei Nickolaev в Apr 24 17:53:34 по местному времени:

Здpавствуй, Sergei!

Суббота 06 Апреля 2024 18:58, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+66117266:

SN> А мне было любопытно :-). Доказал, что вероятность выиграть первые k
SN> партий не меняется с увеличением числа участников. Оказалось самой
SN> интересной частью задачи ...

Что-то меня переклинило. Как оно доказывается строго и без "не, это и так понятно"? :-)


С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 24 14:52:06 по местному времени:

Привет, Alexander!

SN>> А мне было любопытно :-). Доказал, что вероятность выиграть
SN>> первые k партий не меняется с увеличением числа участников.
SN>> Оказалось самой интересной частью задачи ...

AН> Что-то меня переклинило. Как оно доказывается строго и без "не, это и
AН> так понятно"? :-)

Может твоей внучке пригодится, таки не только ответ, но и решение :-). Кстати, не очень частый вариант, когда правильно сначала найти ответ, а потом и решение.
Здесь как-то не очень получается изображать всяческие верхние и нижние индексы, для нормальной классической записи тебе придется восстановить из моих ухищрений.
Число сочетаний из n по k буду записывать как C(n,k). Нижний (в классическом обозначении) индекс - первый, верхний - второй.
Итак, поехали:
Тот факт, что вероятность выиграть первые k партий в ситуации k+1 участников равна 1/(k+1), ты уже благополучно доказал. Это будет базой для доказательства по индукции. Для индукционного перехода нужно доказать, что если вероятность выиграть первые k партий равна 1/(k+1) в турнире с n участниками (n >= k+1), то эта вероятность такая же в турнире с n+1 участником.
Обозначим P(n,k) вероятность выиграть первые к партий в турнире с n участниками. Петр выигрывает первые k партий, если первые k соперников имеют рейтинг меньший, чем у Петра. Это возможно, если рейтинг Петра (больше умение - выше рейтинг, мне так удобнее) больше k. События "рейтинг Петра равен i" несовместимы для разных i, вероятности для разных i можно складывать. Вероятность для рейтинга i равна "вероятность рейтинга i", равная 1/n, умноженная на отношение "число вариантов получить первые k соперников с рейтингом меньше i" к "число вариантов для первых k соперников, независимо от рейтингов". Получается C(i, k)/(n*C(n-1, k).
Итого, вероятность равна сумме по i для i от i=k до i=n-1 C(i,k)/(n*C(n-1,k).
То, что от i не зависит, вынесем из суммы, получается:
P(n,k)=(1/(nC(n-1,k))(C(k,k)+ ... +C(n-1,k)).
Для n+1 выражение получается, соответственно,
P(n+1,k)= (1/((n+1)C(n,k)))(C(k,k)+ ... +C(n-1,k)+C(n,k)).
Для индукционого перехода нужно показать, что если P(n,k) = 1/(k+1), то P(n+1,k) = 1/(k+1).
Соотношение C(n,k)=(n/(n-k))*C(n-1,k) доказывается из классической формулы для C(n,k).
Сумма C(k,k)+ ... C(n-1,k)+C(n,k) в выражении для P(n+1,k) отличается от соответствующей суммы в выражении для P(n,k) одним дополнительным слагаемым.
Получаем:
P(n+1,k)=((n-k)*P(n,k))/(n+1)+1/(n+1), подставляем сюда P(n,k)=1/(k+1), получаем P(n+1,k)=1/(k+1).
Надеюсь, что не наделал опечаток, делающих доказательство невоспроизводимым :-)

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)