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

Отметим все стрелок на одном циферблате. Заметим, что минимальное время будет заведомо достигаться в начальном положении одной из стрелок (если мы все стрелки сдвинули по часовой стрелке, то можно уменьшить время перевода на часов, уменьшив время перевода для каждой стрелки на час).

Наши шесть стрелок разбили циферблат на 6 секторов. Пронумеруем наши стрелки числами от до и обозначим через размер сектора, идущего после -ой стрелки (в часах). Если все стрелки мы перевели в положение то первую стрелку мы не переводили, вторую мы перевели на часов, …, шествую перевели на часов. Тогда суммарное время перевода в этом случае будет равно

Если мы проделаем аналогичные рассуждения для других пяти положений а потом сложим, то в сумме получится

Тогда для какого-то из положений сумма будет не больше, чем часов. То есть можно выбрать такое положение, что суммарное время перевода будет не больше, чем часов.

Осталось привести пример, показывающий, что эта оценка достигается. Можно поставить стрелки через каждые часа (то есть первые часы на часов, вторые — на часа, …, шестые — на часов). Из нашей оценки минимальное время перевода будет в одном из этих положений. Но легко видеть, что в каждом положении суммарное время перевода действительно равно часам.

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

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

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

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

Рассмотрим все кружки размера Никакие два из этих множеств не пересекаются по двум элементам. В каждом множестве пар элементов, а всего пар элементов Значит, всего кружков размера не более Значит, всего множеств не более

что и требовалось доказать.

Пусть в графе вершин и ребер. Рассмотрим все расскаросок графа в цветов. Предположим противное, то есть в каждой раскраске больше, чем одноцветных ребер.

Посчитаем количество одноцветных ребер во всех раскрасках. С одной стороны их хотя бы Теперь посчитаем в скольки раскрасках наше ребро одноцветное, для этого обе вершины должны быть одного цвета, тогда раскрасок, где ребро одноцветное ровно суммируя по всем ребрам получим — противоречие, так как мы показали, что их больше, значит, изначальное предположение неверно, то есть вершины любого графа можно покрасить в цветов так, чтобы доля ребер с одноцветными концами была не более

Рассмотрим все раскрасок чисел от до в цвета. Найдем количество “плохих” раскрасок, если это число окажется меньше, чем то искомая раскраска существует.

Посчитаем количество арифметических прогрессий длины состоящих из натуральных чисел, не превосходящих Для задания арифметической последовательности длины достаточно определить первое и последнее число, так чтобы их разность делилась на то есть у выбраных чисел совпадали остатки при делении на тогда искомое количество равно

Для каждой арифметической прогрессии существует ровно “плохих” расскрасок. Действительно саму прогрессию можно покрасить в один из цветов, а остальные числа как угодно.

Тогда общее количество “плохих” раскрасок не превышает что меньше, чем значит, “хорошие” раскраски существуют.

Будем считать, что в группе может быть людей. Пусть прошло недель. Рассмотрим произвольное разбиение всех учеников на групп. Всего существует ровно способов так сделать. Посчитаем количество плохих разбиений, то есть тех, где найдется дежурство, в котором принимали участие ученики из одной группы. Возьмем этих учащихся, они принадлежат одной из групп, дежурили они вместе в одну из недель, а остальных можно распределить по группам способами. Тогда плохих распределений не более Значит, найдется хорошее распределение по группам.

Пусть — множество всех цветов в наборах. Рассморим всевозможные разбиения на непустые группы: первую и вторую. Тогда если удастся найти разбиение, такое что у всех вершин из первой доли будет цвет из первой группы, а у второй — из второй, то мы сможем выбрать цвета правильным образом. Далее будем доказывать, что такое разбиение существует.

Очевидно, что каждый цвет побывает в первой и второй группе поровну раз, поэтому вероятность того, что цвет в определенной группе составляет Пусть какое-то разбиение не подошло, значит, существует вершина, все цвета которой попали в другую группу, вероятность такого события составляет где — количество цветов в списке вершины. В силу того, что список состоит более чем из цветов, то данная вероятность строго меньше Суммируя по всем вершинам, получим число меньшее единицы, значит, существует правильная раскраска вершин графа

Переведём задачу сразу на язык графов так, что человек — вершина, а рёбра(антирёбра) — знакомство(незнакомство). Заметим, что при задача очевидна, поэтому будем считать, что Рассмотри число которое меньше, чем Тогда всего графов на вершинах Идея доказательства следующая: если графов, содержащих клику, (аналогично для антиклик), то существует граф, в котором нет ни того, ни другого, а значит Всего графов на вершинах, содержащих клику на данных вершинах, Следовательно, всего графов размера содержащих клику:

Последнее выражение меньше, чем если Легко доказать (по индукции например), что при Поэтому можно взять так, как

А значит и что и требовалось.

(a) Пусть и  – положения конца минутных стрелок часов с номером в моменты и минут,  – центр -х часов, а  – центр стола.

Лемма. для любого

Доказательство. Рассмотрим треугольник с вершинами Ясно, что  – его медиана. Как известно, медиана треугольника не превосходит полусуммы прилежащих к ней сторон (достаточно достроить треугольник до параллелограмма и применить неравенство треугольника к ).

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

Ясно, что в таком случае либо либо
Тогда сумма расстояний от центра стола до концов минутных стрелок будет гарантированно больше, чем сумма расстояний до центров часов либо в момент , либо в момент

(b) Зафиксируем момент времени 0 – начало отсчета. Рассмотрим произвольные часы (с номером ). Из леммы в пункте ), в частности, следует, что среднее за один час расстояние от конца минутной стрелки до строго больше Докажем, что существует момент времени такой, что для любого среднее расстояние от конца минутной стрелки до за время от 0 до больше, чем Пусть  – время, которое занимает один полный оборот -ых часов. Введем еще переменную Пусть  – разность между средним расстоянием от конца минутной стрелки до за один полный оборот и (по замечанию, ). И, наконец, пусть есть среднее расстояние от конца минутной стрелки до за время от 0 до Нетрудно понять, что ограничено снизу одной и той же константой для всех Обозначим ее как (при этом вполне может быть отрицательным). Например, по неравенству треугольника ясно, что длины минутной стрелки, поэтому больше либо равно, чем

С помощью введенных обозначений, легко выразить разность между средним расстоянием за время от 0 до от конца минутной стрелки до и для произвольного

Объясним эту формулу. Разобьем время на максимальное число полных оборотов () и то что осталось – интервал от до Поскольку  – разность между средним расстоянием от конца минутной стрелки до за один оборот часов и то за оборотов средняя разность будет равна а суммарная разность . Ясно, что среднее расстояние от конца минутной стрелки до за время от 0 до равно среднему расстоянию за время от до поэтому средняя разность расстояния от конца минутной стрелки до и за это время равно а суммарное – Итак, в числителе стоит суммарная разность за время и ее мы делим на чтобы получить среднюю.

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

Вернемся к нескольким часам. Выберем наибольшее из всех и обозначим его Рассмотрим теперь разность суммы расстояний от концов минутных стрелок всех часов до и Рассмотрим среднее этой величины за время . Оно является суммой по всем разности между средним расстоянием (за время ) от конца стрелки до и По выбору все слагаемые этой суммы положительные. Итак, у нас есть некоторая величина, среднее значение которой положительно – значит и в некоторой точке значение этой величины положительно. Эта некоторая точка и является моментом времени, в котором сумма расстояний от концов минутных стрелок до центра стола больше, чем сумма расстояний от центров часов до центра стола. Именно это и требовалось получить.

Будем решать чуть более общую задачу – пусть число ребер в графе не превосходит Рассмотрим отдельно случай Пусть в графе вершин и ребер. Пусть в нем также ровно изолированных вершин. Если то задача уже решена. Выделим все изолированные вершины в отдельное независимое множество. Будем обозначать граф, из которого удалили все изолированные вершины, как Если то поскольку в вершин и ребер, в нем существует висячая вершина. Добавим ее в независимое множество, и удалим из графа ее соседа со всеми исходящими из него ребрами. Ясно, что после этого преобразования множество осталось независимым. После этого действия число вершин в графе сократилось на а ребер – хотя бы на поэтому разница между числом вершин и ребер сократилась не более чем на 1. Будем повторять эту операцию пока в графе вершин больше чем ребер. Ясно, что мы гарантированно сможем ее провести раз. В результате мы сформировали независимое множество размера хотя бы что и требовалось.

Теперь перейдем к случаю произвольного Оценим среднее количество ребер в подграфе на вершин. Достаточно найти сумму количества ребер во всех таких подграфах и поделить на их количество: А первое можно вычислить альтернативным способом: как сумму по всем ребрам числа подграфов размера его содержащих. Это число не превосходит Если ребро фиксировано, то чтобы дополнить его до подграфа размера необходимо выбрать ровно среди оставшихся Итак,

Существует подграф размера в котором количество ребер не превосходит среднего, то есть Покажем, что в этом графе всегда можно выбрать хотя бы половину вершин так, чтобы они образовывали независимое множество. В базе мы доказали именно то, что в графе, в котором ребер хотя бы в два раза меньше чем вершин, всегда можно выбрать независимое множество размером хотя бы в половину от числа вершин. Осталось убедиться в том, что

Просуммируем по всем раскраскам графа количество одноцветных копий графа Эту сумму можно вычислить вторым способом, как сумму по всем подграфам входящим в раскрасок, в которых данный подграф является одноцветным. А такое число, разумеется, равно

 – количество способов выбрать подграф  – количество способов выбрать цвет  – количество способов раскрасить оставшиеся ребра.

По принципу Дирихле, существует раскраска графа, в которой число одноцветных подграфов составляет хотя бы

что и требовалось доказать.

Первоначально покрашенных кубиков меньше, чем количество покрашенных граней. Таких граней поэтому первоначально покрашенных кубиков меньше половины. Испачканных кубиков не больше, чем покрашенных граней, то есть что не больше половины всех кубиков. Поэтому останется хотя бы один чистый кубик.