задача дня-15

[falcao]

Вот хорошая, на мой взгляд, вероятностная задача.

Проводится турнир по кубковой системе среди n участников. Ничьих нет, проигравшие выбывают. Все игроки считаются примерно равными по силе, то есть при встрече между собой каждый выигрывает с вероятностью 1/2. При чётном количестве игроков, они случайным образом разбиваются на пары, встречаются

Comments

[lj_frank_bot]

Hello!
LiveJournal categorization system detected that your entry belongs to the category: Спорт.
If you think that this choice was wrong please reply this comment. Your feedback will help us improve system.
Frank,
LJ Team

[falcao]

Нет, это совсем не про спорт!

[lj_frank_bot]

Хм...

[109]

Но это же зависит от того, насколько хорошо Андрей и Борис играют. Если это Андрей Агасси и Борис Беккер, то вероятность гораздо выше, чем для других андреев и борисов.

[falcao]

У меня было пропущено важное условие, что игроки считаются одинаковыми по силе. Я внёс исправление.

[glukanat]

вроде очевидно...
2/(n(n-1))

[falcao]

Разве? У них даже в первом туре вероятность сыграть между собой будет больше.

[mathclimber]

Это вероятность того, что они сыграют в финале; в задаче спрашивают вероятность, что они вообще сыграют между собой.

[rus4]

Если они и сыграют, то только раз, так что эта вероятность равна математическому ожиданию X числа игр между ними. Из симметрии процесса тому же числу X равно математическое ожидание числа игр между любой парой участников, а тогда математическое ожидание общего числа игр равно X*n(n-1)/2. Но общее число игр равно n-1 (каждый кроме чемпиона проигрывает ровно один раз), откуда X=2/n.

[falcao]

Я рассуждал чуть иначе, но суть примерно та же.

[mathclimber]

Всего для определения победителя надо n-1 игр (поскольку каждая игра сокращает количество участников на единицу), т.е. будет 2(n-1) "участий в игре". Следовательно, по симметрии, в среднем каждый игрок сыграет 2(n-1)/n игр. Если Андрей сыграл К игр, вероятность встретиться с Борисом K/(n-1), тоже в силу симметрии. Значит, по формуле полной вероятности ( P(A)=E(P(A|K)) ) oтвет получается 2/n.

[falcao]

На мой взгляд, несколько длинновато, но работает.

[mathclimber]

Moжно ещё так: очевидно, достаточно посчитать вероятность события {Андрей встретится с Борисом, и проиграет} (тогда искомая вероятность в два раза больше). Равновероятные события {Андрей встретится с Х, и проиграет} (где Х пробегает множество остальных игроков) не пересекаются, и сумма их вероятностей равна (n-1)/n (т.е., вероятности того, что Андрей не выиграет турнир). Отсюда сразу получается ответ.

[falcao]

Вот это уже почти дословно совпадает с моим решением!