@MSGID: 2:6035/3.17 661bdbcd
@REPLY: 2:6035/3.8 661807be
@CHRS: CP866 2
@TZUTC: 0300
@TID: hpt/w32-mgw 1.4.0-sta 30-03-12
   Привет, Alexander!

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

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

 Может твоей внучке пригодится, таки не только ответ, но и решение
:-). Кстати, не очень частый вариант, когда правильно сначала найти ответ,
а потом и решение.
 Здесь как-то не очень получается изображать всяческие верхние и
нижние индексы, для нормальной классической записи тебе придется восстановить
из моих ухищрений.
 Число сочетаний из 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/(n*C(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)
 * Origin: В начале было слово. В конце будет ориджин. (2:6035/3.17)
SEEN-BY: 46/49 50/8 109 221/6 301/1 452/28 463/68
467/888 4500/1 5000/111
SEEN-BY: 5001/100 5005/49 5015/46 5019/40 5020/113
290 329 400 570 715 828
SEEN-BY: 5020/830 846 848 1042 1668 2992 4441
5452 12000 5023/24 5030/49 115
SEEN-BY: 5030/1081 1474 5034/13 5035/64 5036/26
5049/1 3 5053/55 58 5054/8
SEEN-BY: 5055/73 5057/19 5058/104 5060/900 5061/133
5068/45 5083/1 444 6035/3
SEEN-BY: 6035/66 6078/80
@PATH: 6035/3 5020/715 1042 4441