Е. Р. Байсалов, да. ЕлиусизовМатематические олимпиады
 Скачать 2.18 Mb.
|
|
Рис. 29 Решения задач АТМО все. . . , дважды и касается r 1 и r 2𝑛 . Значит обладает указанными свойствами. Задача 5 . Ответ два семейства решений: (а) a 𝑛 = c(n + 2)n! для всех n ¾ 1 и a 0 = c + 1 для некоторого целого ¾ б c(n +2)n! для всех n ¾ 1 и a 0 = c −1 для некоторого целого ¾ Пусть последовательность натуральных чисел, удовлетворяющая указанным условиям. Можно переписать условие 2 как (n + 1)a 𝑛 + h 𝑛 , где {−1, 1}. Заменяя n на n − 1, получаем na 𝑛 −1 + h 𝑛 −1 , где {−1, 1}. Заметим, что a 𝑛 +1 = s 𝑛 +1 + поэтому существует такое {−2, 0, 2}, что (n + 1)a 𝑛 + na 𝑛 −1 + Также имеем 2a 1 | = 1, что приводит к неравенству 3a 1 − a 2 ± 1 ¶ следовательно a 0 /3 ¾ 671. Подставляя n = 2 в формулу (1), находим. Поскольку, получаем, что+ откуда 223. Используя формулу (1), получаем, что a 𝑛 ¾ 223 для всех ¾ Лемма 1. Для n ¾ 4 справедливо соотношение (n + 1)(n + Доказательство. Если n ¾ 3, то na 𝑛 −1 + (n − 1)a 𝑛 −2 + δ 𝑛 −1 > na 𝑛 −1 + Используя неравенство (2) и заменяя на n − 1, получаем, что для ¾ 4 выполняются неравенства na 𝑛 −1 + (n − 1)a 𝑛 −2 + δ 𝑛 −1 < < na 𝑛 −1 + (a 𝑛 −1 − 3) + δ 𝑛 −1 < (n + В силу соотношения (1) мы можем переписать a 𝑛 +2 в терминах a 𝑛 и a 𝑛 −1 , что вместе с неравенством (2) приводит к следующему соотношению для ¾ 3: a 𝑛 +2 = (n + 3)(n + 1)a 𝑛 + (n + 2)na 𝑛 −1 + (n + 2)δ 𝑛 + δ 𝑛 +1 < < (n + 3)(n + 1)a 𝑛 + (n + 2)na 𝑛 −1 + 3(n + 2) < (n 2 + 5n + 5)a 𝑛 Решения задач АТМО 2015 К тому же для ¾ 4 имеем (n + 3)(n + 1)a 𝑛 + (n + 2)na 𝑛 −1 + (n + 2)δ 𝑛 + δ 𝑛 +1 > > (n + 3)(n + 1)a 𝑛 + na 𝑛 = (n 2 + 5n + Поскольку, имеем (n 2 + 5n + 4)a 𝑛 = (n + 1)(n + что и требовалось доказать. Лемма 2. При n ¾ 4 справедливо соотношение+ 1)(n + 3) n + Доказательство. Используя рекуррентное соотношение (n + 3)a 𝑛 +2 + (n + 2)a 𝑛 +1 + и переписывая a 𝑛 +3 , a 𝑛 +2 в терминах, согласно лемме 1 получаем+ Следовательно+ 4|δ 𝑛 +2 , откуда следует, что 0 и+ 1)(n + 3) n + что и требовалось доказать. Предположим, что существует такое ¾ 1, что 6= ( n + 1)(n + 3) n + Согласно лемме 2 существует наибольшее, 1 ¶ m ¶ 3, удовлетворяющее этому условию. Тогда+ 2)(m + 4) m + Если 0, то+ 1)(m + 3) m + что противоречит выбору. Значит 6= Ясно, что+ 3|a 𝑚 +1 . Положим (m + 3)k и a 𝑚 +2 = (m + 2) · (m + Тогда+ 1)a 𝑚 + δ 𝑚 +1 = a 𝑚 +2 − (m + 2)a 𝑚 +1 = (m + 2)k. Решения задач АТМО Таким образом + 2)k − δ 𝑚 +1 . Но a 𝑚 также делит (m + 2)(m + Отсюда следует, что + 4)δ 𝑚 +1 . Поскольку 6= 0, имеем + 8 ¶ что противоречит предыдущему результату о том, что 223 для всех неотрицательных n. Итак, a 𝑛 +1 = ( n + 1)(n + 3) n + при всех ¾ 1. Подставляя n = 1, получаем, что 3|a 1 . Полагая по индукции находим n!(n+2)c для n ¾1. Поскольку |s 2 − 2a 1 | = получаем, что c ± 1, что даёт два семейства решений. Замечая, что ( n +2)n!=n!+(n+1)!, находим s 𝑛 +1 =c(n+2)!+(−1) 𝑛 ( c − a 0 ). Следовательно, оба семейства решений удовлетворяют условиям задачи. 28-я олимпиада, 2016 год Задача 1 . Для любой точки D на стороне BC пусть D 0 — точка, симметричная точке относительно прямой PQ см. рис. Для начала докажем, что если треугольник замечательный, то он равнобедренный и имеет прямой угол A. Пусть AD является биссектрисой уг- B C D A Q D 0 P Рис. 30 ла A. Заметим, что точки P и Q, являющиеся проекциями точки на прямые и соответственно, симметричны друг другу относительно прямой. Откуда следует, что AD. Поэтому лежит на прямой. Тогда либо D 0 = A, либо является второй точкой пересечения биссектрисы угла и описанной окружности треугольника. Однако, так как четырёхугольник APDQ является описанным, отрезок PQ пересекает отрезок. Следовательно, лежит на луче, и тогда D 0 = По свойству углов в окружности имеем ∠PDQ = 180 ◦ − Атак как A, получаем, что ∠PD 0 Q = ∠BAC. Значит, ∠BAC = 90 ◦ Решения задач АТМО 2016 Теперь пусть — середина отрезка BC см. рис. Поскольку = 90 ◦ , стороны треугольника являются средними линиями треугольника. Следовательно, PQ k BC и DD 0 ⊥ BC. Но расстояние от точки D 0 до прямой равно радиусу описанной окружности треугольника и расстоянию от A до прямой BC. Это может быть только в случае, когда A. Следовательно, треугольник ABC равнобедренный и имеет прямой угол A. B C D A Q D 0 P Рис. Рис. Теперь докажем, что если — равнобедренный треугольник с прямым углом, то он замечательный. Пусть D — произвольная точка на стороне, тогда D 0 P = DP и DP = BP см. рис. Следовательно, и аналогично D 0 Q = CQ. Заметим, что пятиугольник описанным с диаметром. Следовательно APD 0 = ∠AQD 0 , а значит, ∠BPD 0 = ∠CQD 0 . Тогда треугольники D 0 PB и D 0 QC подобны. Следовательно ∠PD 0 C − ∠CD 0 Q = ∠PD 0 C − ∠BD 0 P = и : D 0 Q = D 0 B : D 0 C. Таким образом, получим, что треугольники и D 0 BC подобны. Так как треугольники DPQ и D 0 PQ равны, получаем, что ∠BD 0 C = ∠PD 0 Q = ∠PDQ = 90 ◦ . Следовательно, D 0 ле- жит на окружности с диаметром, которая является описанной окружностью треугольника ABC. Задача_2'>Задача 2 . Ответ n = 2 101 − Пусть — натуральное число, меньшее 2 101 − 1. Тогда k в двоичном представлении имеет не более 100 единиц. Следовательно, найдутся такое натуральное число такие и неотрицательные целые числа. . . , a 𝑟 , что ¶ 100 и k = 2 𝑎 1 + 2 𝑎 2 + . . . + 2 𝑎 𝑟 . Заметим, что для натурального числа выполняется равенство 2 𝑎 1 +𝑠 + 2 𝑎 2 +𝑠 + . . . + 2 𝑎 𝑟 −1 +𝑠 + (1 + 1 + 2 + . . . + 2 𝑠 −1 )2 𝑎 𝑟 = = 2 𝑎 1 +𝑠 + 2 𝑎 2 +𝑠 + . . . + 2 𝑎 𝑟 −1 +𝑠 + 2 𝑎 𝑟 + 2 𝑎 𝑟 + 2 𝑎 𝑟 +1 + . . . + 2 𝑎 𝑟 +𝑠−1 Решения задач АТМО Это показывает, что имеет кратное, которое равно сумме r + степеней двойки. В частности, можно выбрать 100 − r ¾ 0, те. имеет кратное, которое является чудесным. Теперь докажем, что ни одно из кратных числа 2 101 − 1 не является чудесным числом. В действительности будет доказано более сильное утверждение о том, что ни одно из кратных числа не может быть представлено не более чем 100 степенями двойки. Предположим противное пусть существует такое натуральное число, что cn представимо в виде суммы не более 100 степеней двойки. Предположим, что — наименьшее из таких натуральных чисел. Повторными слияниями одинаковых степеней двойки в представлении числа можно добиться разложения 2 𝑎 1 + 2 𝑎 2 + . . . + где ¶ 100 и a 1 < a 2 < . . . < a 𝑟 — различные неотрицательные целые. Рассмотрим следующие 2 случая. Если 101, то 2 𝑎 𝑟 − 2 𝑎 𝑟 −101 = 2 𝑎 𝑟 −101 n. Следовательно, число+ 2 𝑎 2 + . . . + 2 𝑎 𝑟 −1 + является кратными меньше, чем cn. Это противоречит минимальности. Если 100, то {a 1 , a 2 , . . . , a 𝑟 } является собственным подмножеством множества, 1, . . . , 100}. Тогда ¶ cn < 2 0 + 2 1 + . . . + 2 100 = Снова получим противоречие. Из этих противоречий следует, что не может быть представимо в виде суммы не более 100 степеней двойки. В частности, ни одно из натуральных чисел, кратных, не является чудесным. Задача 3 . Приведём два подхода к решению. В первом вводится дополнительная точка и изучается подобие фигур. Второй подход сводит решение задачи к вычислениям. Второй подход имеет два варианта. Первое решение. Пусть прямая, проходящая через точку N и касающаяся окружности в точке X 6= E, пересекает AB в точке Теперь достаточно доказать, что AC, так как это приводит к равенству см. рис. Предположим, что прямая пересекает в точке Q. Решения задач АТМО 2016 Рис. Рассмотрим для начала четырёхугольник PM 0 NQ. Понятно, что в нём углы при вершинах и Q равны, а прямые и делят углы M 0 и N соответственно пополам. Введём обозначения ∠P = ∠Q = α, ∠PM 0 O = ∠OM 0 N = β, ∠M 0 NO = ∠ONQ = γ. Тогда из суммы углов четырёхугольника получим +2γ=360 ◦ , или Следовательно, в треугольнике имеем ∠QON = 180 ◦ − α − γ = Теперь пусть описанная окружность треугольника пересекает прямую во второй разв точке Y. Тогда ∠AM 0 Y = ∠AOY = и ∠AYO = ∠OM 0 P = β. Следовательно, треугольники AYP и подобны по двум углам, аи — высоты, проведённые из соответствующих вершин. Тогда из этого подобия и параллельности PQ следует, что PR RN = QE EN = PM 0 M 0 A , а значит AN k Второе решение а. Как ив первом решении, вводим точку и сводим задачу к доказательству соотношения : RN = По теореме Менелая в треугольнике для точек F, R, E имеем 1. Решения задач АТМО Поскольку EA, имеем FP : NE = PR : RN. Так что нам остаётся доказать равенство FP NE = PM 0 M 0 A (1) А это можно доказать с использованием треугольника и его вневписанной окружности, касающейся. Введём обозначения M 0 N, b = NA, c = M 0 A, s = (a + b + c)/2, x = s − a, y = s − b, z = s − тогда AF = s, M 0 F = z и NE = y. Из подобия треугольников и следует, что FP = r 2 𝑎 /s, где r 𝑎 = OF — радиус вневписанной окружности, касающейся. Скомбинировав следующие две формулы для нахождения площади треугольника ( S 𝐴𝑀 0 𝑁 ) 2 = xyzs формула Герона) и r 𝑎 ( s − a), — получаем, что r 2 𝑎 = yzs/x. Следовательно. Выразив равенство (1) через x, y, z, получаем эквивалентное равенство+ yz/x x + в справедливости которого легко убедиться. Замечание. Другим подходом к решению с использованием теоремы Менелая является дополнительное построение касательной в точке для получения точки на и последующее доказательство того, что точки, R и лежат на одной прямой. Задача снова сводится к алгебраическому подсчёту. Второе решение б. Как ив первом решении, введём точку Пусть прямая, проходящая через M 0 и параллельная, пересекает в точке R 0 . Обозначим точку пересечения прямых NR 0 и AM через P 0 . Тогда задача сводится к доказательству того, что откуда следует, что P 0 , и тогда и M 0 . Значит, достаточно доказать, что AF FP 0 = AD DO , (2) где D — точка пересечения прямых AO и EF. Последнее вновь сводится к использованию треугольника и его вневписанной окружности, касающейся стороны M 0 N. Обозначим u = P 0 F и x, y, z, s, как ив решении а. Заметим, что, поскольку AE = AF и M 0 R 0 k AE, справедливо равенство M 0 R 0 = M 0 F = Зная, что AN, получаем, что P 0 M 0 : P 0 A = M 0 R 0 : NA, те Решения задач АТМО 2016 Из последнего уравнения получаем yz/x. Отсюда следует, что AF FP 0 = xs yz Так же как ив решении а, получаем, что Наконец, используя подобие треугольников, FDA и OFA и доказанные выше равенства, получаем AD DO = AD DF · DF DO = AF OF · AF OF = s 2 r 2 𝑎 = s 2 yzs /x = xs yz = AF FP 0 , что и требовалось доказать. Задача 4 . Ответ Рейсы, установленные авиакомпанией Starways, дают ориентированный граф с 2016 вершинами, в котором каждая вершина имеет одно выходящее ребро. Сначала покажем, что необходимо по крайней мере 57 групп. Для этого предположим, что имеет ориентированный цикл длины Тогда для любых двух городов в цикле из одного в другой можно попасть не более чем за 28 перелётов. Это означает, что никакие два города не могут принадлежать одной группе. Значит, необходимо не менее 57 групп. Покажем теперь, что 57 групп достаточно. Рассмотрим произвольный ориентированный граф, вершины которого являются городами нашей страны, а из вершины проведено ориентированное ребро в город, если из v можно попасть вне более чем за 28 перелётов. Тогда каждая вершина имеет не более 28 исходящих рёбер. Задача будет решена, если мы сможем разбить вершины на не более, чем 57 групп так, что внутри одной группы не проведено никаких ориентированных рёбер. Докажем более сильное утверждение. Лемма. Пусть имеется ориентированный граф с n ¾ 1 вершинами, где каждая вершина имеет не более 28 исходящих рёбер. Тогда вершины могут быть разбиты на 57 групп так, что ни одна пара из одной группы не будет соединена ориентированным ребром. Доказательство. Используем индукцию. База для n = 1 очевидна. Теперь представим, что имеется 1 вершин. Так как количество исходящих рёбер из одной вершины не более 28, имеется вершина, у которой количество входящих рёбер не более 28. Если убрать вершину, то получится граф, который всё равно удовлетворяет Решения задач АТМО условию леммы, но количество вершин уменьшилось. Тогда по индукционному предположению граф можно разбить на 57 групп, где вершины водной группе не соединены ребром. Так как вершина имеет не более 28 входящих рёбер и 28 исходящих рёбер, она имеет максимум 56 соседей в исходном графе. Таким образом, мы можем вернуть вершину назад и поместить её в группу, в которой она не имеет соседей. Это завершает шаг индукции. Задача 5 . Ответ f (x) = x для всех x ∈ Перепишем тождество, данное в условии+ 1) f (x + y) = f (x f (z) + y) + f (y f (z) + Очевидно, что тождественная функция (x) = x удовлетворяет заданному функциональному уравнению. Пусть теперь функция удовлетворяет заданному функциональному уравнению. Подставляя y в равенство (1), получим 2 f ( f (z) + 1) = (x + 1)( f (2)) для всех z ∈ Следовательно, функция не ограничена сверху, так как x можно выбрать сколько угодно большим. |