теория - Вероятность события

Явный пример такого турнира привести довольно сложно, поэтому надо ограничиться доказательством его существования. Это делается при помощи вероятностного аргумента.

Рассмотрим турнир с достаточно большим числом участников, равным $%n$%. Пусть результаты всех игр выбраны независимо и случайно с равной вероятностью. Оказывается, что из чисто статистических соображений, то событие, о котором здесь говорится, происходит с ненулевой вероятностью. Отсюда следует факт существования указанного турнира. Более того, можно доказать (это будет сделано ниже), что при $%n\to\infty$% вероятность желаемого события не просто ненулевая, а даже стремится к единице.

Рассмотрим 10 команд, и возьмём для них какую-то одну из $%n-10$% оставшихся. Какова вероятность того, что она выиграла у каждой из десяти при условии случайности исхода? Очевидно, она равна $%1/2^{10}$%. Вероятность того, что это условие нарушается, равна $%1023/1024$%, то есть близка к единице.

Теперь зададим вопрос, какова вероятность того, что для каждой из $%n-10$% команд происходит такой случай, который нам не подходит? Поскольку исходы всех игр независимы, вероятность равна $%(1023/1024)^{n-10}$%, то есть она довольно быстро стремится к нулю. Отсюда пока ещё ничего не следует, так как мы рассмотрели фиксированные 10 команд и пришли к выводу, что отсутствие команды, выигравшей у всех десяти, очень мала. Но нам надо, чтобы для каждого набора из 10 команд нашлась выигравшая у них команда. А таких наборов всего имеется $%C_n^{10}$%. Значит, вероятность не устраивающего на события не превосходит $%C_n^{10}(1023/1024)^{n-10}$%. При этом используется то соображение, что вероятность объединения событий (в количестве $%C_n^{10}$%) не превосходит суммы этих вероятностей, каждая из которых равна $%(1023/1024)^{n-10}$%.

Осталось заметить, что число сочетаний растёт полиномиально (скажем, можно дать очень грубую, но верную оценку $%C_n^{10} < n^{10}$%. Можно при этом ещё и разделить на $%10!$%, но для нас это не так важно. Эта величина делится на $%a^{n-10}$%, где $%a=1024/1023 > 1$%, то есть на экспоненциально растущую. Из курса матанализа нам известно, что экспонента растёт быстрее любого полинома, то есть $%\lim\limits_{n\to\infty}\frac{n^{10}}{a^n}=0$%. Множитель $%a^{10}$% при этом так же не влияет, как и $%10!$%. Таким образом, вероятность нежелательного для нас события стремится к нулю при $%n\to\infty$%, откуда следует существование турнира из условия.