Задача 1: p и q – простые числа, такие, что p² + 1 делится на q, а q² – 1 делится на p. Докажите, что p + q + 1 – составное число.

(А.~Голованов)

Решение: Так как (q + 1)(q – 1) делится на p, то одно из чисел q + 1 или q – 1 делится на p. Если q + 1 делится на p, то и p + q + 1 делится на p. Если же q – 1 делится на p, то q = kp + 1 для некоторого натурального k ≤ p. По условию, p² + 1 делится на q, значит, p² + 1 – q = p² – kp = p(p – k) делится на q, значит, p – k делится на q. Следовательно, k = p (иначе 0 < p – k < q), то есть q = p² + 1. Но тогда p + q + 1 = p² + p + 2 – четное число, большее двух.

Задача 2: На плоскости даны две пересекающиеся окружности. Точка A – одна из двух точек пересечения этих окружностей. В каждой окружности проведен диаметр, параллельный касательной в точке A к другой окружности, причем эти диаметры не пересекаются. Докажите, что концы этих диаметров лежат на одной окружности.

(С.~Берлов )

Решение: Обозначим диаметры BC и DE, а центры соответствующих окружностей – O₁ и O₂, и проведем из центров окружностей перпендикуляры к соответствующим диаметрам. Пусть эти перпендикуляры пересеклись в точке F (см. рисунок). Докажем, что F – центр искомой окружности.

Заметим, что O₁F\|AO₂, т. к. O₁F и AO₂ перпендикулярны BC. Аналогично O₂F\|AO₁. Значит, AO₁FO₂ – параллелограмм. Отсюда FO₂ = AO₁ = BO₁, а FO₁ = AO₂ = DO₂. Теперь из равенства треугольников BO₁F и FO₂D получаем, что FB = FD. Кроме того, точка F, по построению, лежит на серединных перпендикулярах к BC и DE, а значит, FC = FD = FB = FE, что и требовалось.

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

Задача 3: На плоскости дано 1995 точек, некоторые пары точек соединены отрезками. Точки первоначально раскрашены в два цвета. Каждую минуту (одновременно) те точки, которые соединены с четным количеством точек такого же цвета, меняют свой цвет. Докажите, что исходная раскраска не сможет снова получиться через нечетное число минут.

(С.~Берлов)

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

Задача 4: d₁, d₂,…,d_k – все возможные натуральные делители некоторого натурального числа N, выписанные в порядке возрастания. Оказалось, что d₂ – d₁, d₃ – d₂, d₄ – d₃, …, d_k – d_k – 1 – также все возможные делители какого-то натурального числа (не обязательно в порядке возрастания). Найдите все N, для которых такое может быть.

(А.~Голованов)

Решение: Число, набор делителей которого образуют разности d_i + 1 – d_i, – это наибольшая из разностей, то есть d_n – d_n – 1. Среди разностей d_i + 1 – d_i должна быть единица, поэтому по крайней мере один делитель N четен, так что N четно. Значит, d_n – 1 = N/2, d_n – d_n – 1 = N – N/2 = N/2. Итак, число делителей N/2 ровно на 1 меньше числа делителей N, т. е. все делители N, кроме самого N, являются делителями N/2. Отсюда N – степень двойки, так как если N делится на нечетное число k > 1, то N/2 не может делиться на N/k. Легко проверить, что все степени двойки действительно удовлетворяют условию.

Задача 5: В Цветочном городе живут 1995 коротышек. У них имеется 995 10-копеечных монет и неограниченный запас пятаков (монет по 5 коп.). Иногда коротышки меняются монетами: один дает другому монету в 10 копеек, а тот ему – два пятака. Как-то вечером каждый из коротышек заявил: «Сегодня я отдал ровно 10 монет». Докажите, что кто-то из них ошибся.

(К.~Кохась)

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

Докажите, что если у коротышек было 1329 десятикопеечных монет, то все равно, кто-то из них ошибся.

Задача 6: H – ортоцентр остроугольного треугольника ABC; D – середина стороны AC. Прямая, проходящая через H перпендикулярно отрезку DH, пересекает стороны AB и BC в точках E и F. Докажите, что HE = HF.

(С.~Берлов)

Решение: Пусть AL и CK – высоты  ∆ ABC. Продолжим отрезок HD за точку D и отложим отрезок DH′ = HD. Тогда четырехугольник AHCH′ – параллелограмм, так как его диагонали делятся точкой пересечения пополам. Отсюда следует, что H′A\|CK, а значит,  ∠ H′AB = 90. Четырехугольник AEHH′ – вписанный, так как  ∠ H′AE =  ∠ EHH′ = 90, поэтому углы H′EH и H′AH равны. Аналогично  ∠ H′CH =  ∠ H′FH. Но  ∠ H′AH и  ∠ H′CH равны как противоположные углы параллелограмма, значит,  ∠ H′EH =  ∠ H′FH. Таким образом  ∆ EH′F равнобедренный, и его высота H′H является медианой, то есть, EH = HF.

Решение 2. Пусть L – основание высоты, опущенной из вершины A. Тогда  ∠ AHD = 90 –  ∠ AHE = 90 –  ∠ LHF =  ∠ LFH =  ∠ BFH. Кроме того,  ∠ HAD =  ∠ FBH = 90 –  ∠ C. Следовательно,  ∆ AHD ∽  ∆ BFH. Аналогично доказывается, что  ∆ CHD ∽  ∆ BEH. Значит,

(То, что D – именно середина стороны, использовалось только в самом последнем равенстве.)

Решение 3 (найдено одним из участников олимпиады). Через точку A проведем прямую, параллельную EF, пусть она пересекает сторону BC в точке M (Если она пересекает продолжение стороны BC, то сделаем аналогичное построение для вершины C). Тогда AM ⊥ HD. Пусть высота BG (проходящая через точку H) пересекает отрезок AM в точке N. Достаточно доказать, что AN = NM, тогда результат задачи будет следовать из теоремы Фалеса. Для этого, в свою очередь, достаточно проверить, что прямая DN совпадает со средней линией  ∆ ABC, или просто что DN || BC. Но прямая DN проходит через точку пересечения высот  ∆ AHD. Поэтому DN ⊥ AH, а прямая AH – это высота  ∆ ABC, так что DN || BC.

Утверждение задачи является также простым следствием теоремы о бабочке (См. Г. Коксетер, С. Грейтцер «Новые встречи с геометрией»; Д.О.Шклярский, Н.Н.Ченцов, И.М.Яглом «Избранные задачи и теоремы планиметрии», задача 122.).

Задача 7: Найдите все простые p и q, для которых p² – p + 1 = q³.

(А.~Голованов)

Решение: Ответ: p = 19, q = 7. Вычтем из обоих частей уравнения единицу: p(p – 1) = (q – 1)(q² + q + 1). Поскольку p – простое, один из множителей справа делится на p. Но q – 1 не может делиться на p, так как q < p. Значит, q² + q + 1 = kp и p – 1 = k(q – 1) для некоторого натурального k. Выражая p из второго равенства и подставляя в первое, получаем уравнение k²(q – 1) + k = q² + q + 1. Из него следует, что k² > q + 1 (иначе k²(q – 1) + k ≤ q² + k – 1 < q² + q + 1) и k² < q + 3 (иначе k > 2 и k²(q – 1) + k ≥ q² + 2q + k – 3 > q² + q + 1). Следовательно, k² = q + 2, q² + q + 1 = (q + 2)(q – 1) + k = q² + q + k – 2, откуда k = 3. Значит, q = k² – 2 = 7, p = k(q – 1) + 1 = 19.

Условие простоты q в приведенном решении не использовалось.

Задача 8: На доске написаны числа . Разрешается к любому из этих чисел прибавить разность двух других, умноженную на произвольное рациональное число. Можно ли такими операциями получить числа ?

(С.~Иванов)

Решение: Все числа, получаемые в процессе выполнения операций, имеют вид , где a и b – рациональные числа, причем представление числа в таком виде единственно, поскольку  – иррациональное число. Поставим числу в соответствие точку (a,b) на координатной плоскости и будем следить за треугольником, полученным таким способом из трех написанных на доске чисел. Прибавление к одному из чисел разности двух других, умноженной на рациональное число r, соответствует переносу одной из вершин треугольника на вектор противолежащей стороны, умноженный на r. При такой операции площадь треугольника не изменяется. Числам соответствует треугольник площади 1/2, а числам  – треугольник площади 1. Значит, получить второй набор из первого невозможно.