Вероятностный метод (усреднение)

Турнир задается выбором ориентации ребер, которых . Поэтому всего турниров . Рассмотрим вероятностное пространство, элементами которого будут все турниры на вершинах, причем для различных ребер их ориентации независимы. Это означает, что все турниры равновероятны.

Для каждой из ! перестановок вершин рассмотрим случайную величину , равную единице, если вершины турнира образуют гамильтонов путь именно в этом порядке и 0 в противном случае.

Математическое ожидание равно вероятности того, что она равна 1 , т.е. , как произведение вероятностей независимых событий с вероятностью каждое.

Число гамильтоновых путей в случайном турнире - тоже случайная величина, равная сумме по всем возможным перестановкам , поэтому его математическое ожидание в ! раз больше, т.е. равно . С другой стороны, математическое ожидаение в данном случае - среднее значение числа гамильтоновых путей в турнире, поэтому существуют турниры, в которых не меньше гамильтоновых путей.