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

Пример.

Одну из сторон разобьём на отрезков длины а другую — на отрезков длины и оставшийся отрезок длины . Тогда только прямоугольников с узкой стороной длины имеют площадь меньше
Оценка.

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

По неравенству Коши-Буняковского-Шварца оно не превосходит

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

Первое решение.

Подберём таким образом, чтобы выполнялось равенства Тогда Следовательно,

Второе решение.

Найдём значение выражения Для этого достаточно найти значение его квадрата, а потом извлечь корень. Но квадрат этого выражения равен

Подставим вместо преобразуем и получим выражение

Следовательно, откуда и находим ответ.

Пусть они не простые. Тогда и имеют общий простой делитель Рассмотрим произведение чисел и и преобразуем

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

Пусть имеется способов выбрать граммов без использования гири в г и способов набрать граммов с использованием гири в г.

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

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

Следовательно, (при нечётном появляется ещё один способ взять гири вне этого алгоритма, поэтому знак больше или равно).

Сложив полученные два неравенства, имеем требуемое.

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

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