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

Распишем в хорошем для нас виде

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

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

Пример
Рассмотрим три соседние грани и поделим каждую на квадрата . Далее в трех квадратах, указанных на рисунке, поставим ладьи на одной из главных диагоналей.

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

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

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

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

Далее заметим, что по лемме о трезубце для треугольников и получаем, что и соответственно. Подставляя в последнее равенство, получаем, что

откуда Но нам известно, что перпендикулярен биссектриссе угла Тогда из параллельности биссектриса перпендикулярна и

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

Доказательство
Индукция по числу прогрессий. База для прогрессий очевидна. Докажем переход от к Не умаляя общности (и по индукционному предположению) можно считать, что прогрессии начинаются с нуля. Пусть Поскольку прогрессии имеют общую точку, мы можем считать, что первый член прогрессии равен (где — некоторое натуральное число). А поскольку прогрессии и тоже пресекаются, прогрессия должна содержать число вида . Если то мы нашли общую точку всех прогрессий. В противном случае прогрессия содержит все числа вида

По китайской теореме об остатках существует число которое делится на НОД и имеет остаток 1 при делении на
НОД При таком соответствующий член прогрессии делится и на и на т.е. принадлежит множеству значений всех прогрессий.
Покажем, как из леммы следует утверждение задачи. Зафиксируем пару точек и и запустим отсчет времени с момента какой-нибудь их встречи. Пусть в следующий раз они встретились через секунд, тогда далее все их встречи будут происходить в моменты времени где Для каждой точки моменты ее встреч с парой образуют арифметическую прогрессию (здесь — момент их первой совместной встречи, — интервал между двумя последовательными встречами, ). По условию точки и встретятся вместе, поэтому прогрессии и пересекаются для любой пары точек и Тогда, согласно лемме, у всех таких прогрессий есть общая точка Значит, в момент времени все точки встретятся вместе.

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

Допустим, что среди туристов имеется (или более) «богачей». Нарисуем граф: вершины — это города, из каждого города проведем самый дорогой выходящий путь. Тогда этот граф представляет собой лес, в каждом дереве которого все ребра направлены к корню, за исключением единственного ребра, выходящего из корня, — это ребро в дереве как бы двустороннее. Возьмем богача, который расположен ближе всего к корню своего дерева. Этот богач будет в течение ходов самым близким к корню. Значит, он проедет по городам, в которых еще не было других богачей. Это может быть только если граф — это путь из вершин, богачи занимают первые вершин этого пути (т. е. половину) и гуськом движутся по этому пути в сторону второй половины. Отсюда следует, что богачей не может быть больше а также что количество переездов тоже не превосходит

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

Обозначим города Допустим, что путь

составлен из самых дорогих авиалиний, для определенности пусть цена перелета равна рублей. А «бедный путь» пусть сначала проходит по городам с большими четными номерами, потом — по городам с большими нечетными, а далее — с малыми: сначала с четными, потом с нечетными:

Цены этих авиалинии пусть убывают от до рубля при движении вдоль этого пути. Цены остальных авиалиний назначим произвольно в диапазоне от до рублей.

Нам понадобится следующая стандартная лемма.

Лемма. Предположим, что — вещественные числа, причем и многочлен степени удовлетворяет равенству Тогда где

Доказательство. Положим Тогда

Приравнивая в полученном уравнении коэффициенты при степенях видим, что все они, кроме коэффициента при равны

Ясно, что многочлен удовлетворяет условию при любом а многочлен, равный ненулевой константе, не удовлетворяет условию ни при каком Пусть теперь степень многочлена равна и

Сделаем несколько наблюдений, не пользуясь соображениями целочисленности из условия задачи. Будем считать, что (для рассуждения аналогичны). Рассмотрим равенство

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

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

Положим (для этого значения коэффициент при равен ).

Мы утверждаем, что существует

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

Для больших для которых аналогично получаем, что имеет некоторый конечный предел

Рассмотрим теперь большое натуральное Среди чисел два имеют одинаковый знак. Если, например, и отрицательны, то

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

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

Отметим на биссектрисе угла точку — точку пересечения биссектрис треугольника

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

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

Пусть тогда по свойству биссектрисы,

Тогда

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

Поскольку и — биссектрисы углов и угол между прямыми и равен

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