ПитерГор - задачи по годам → .04 ПитерГор 2017

Выберем учеников из первого кружка, рассадим их в разные кабинеты. Выберем других человек из второго кружка и рассадим их, и так далее.

_________________________________________________________________________________________________________________________________________________________________________________

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

Рассмотрим комнат, где число определим позже. Посадим каждого школьника в одну из этих комнат, выбирая ее случайно (все комнаты равновероятны). Назовем комнату подозрительной, если в ней оказались представители не всех кружков. Предположим, что случилась УДАЧА: оказалось не более чем подозрительных комнат. Тогда имеется неподозрительных комнат, мы можем назвать их кабинетами, и искомая рассадка найдена. УДАЧА заведомо иногда случается, если математическое ожидание числа подозрительных комнат меньше Заметим, что равно количеству комнат умноженному на вероятность того, что конкретная комната подозрительна. Эта вероятность, в свою очередь, не превосходит Итак, если

то при таком требуемая рассадка существует. Уже при получается экспоненциальное по выражение, наилучшего результата — около — можно добиться при

Пусть — середина стороны — середина дуги лежащая на отрезке — точка, симметричная точке относительно медианы

Предположим противное. Тогда и

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

Заметим, что

Следовательно,

Стало быть, интересующая нас сумма всегда не меньше С другой стороны, если и то

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

при достаточно большом Противоречие.

Заметим, что так что точки лежат на одной окружности. Пусть — точка пересечения прямых и Имеем

последнее равенство выполнено в силу того, что прямая — касательная к сфере с диаметром а — секущая.

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

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

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

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

Мы проверили, что при всех Тогда по формуле т. е. граф оказался неконтрпримером.