Е. Р. Байсалов, да. ЕлиусизовМатематические олимпиады
 Скачать 2.18 Mb.
|
|
Задача 4 . а) Положим S = {3, 6, 12, 24, 48, 95, 96, 97}, те+ Когда пробегает значения от 0 до 5, суммы, составленные из чисел, представимы в виде 3 t, где 1 ¶ t ¶ 63. Это 63 делящихся на 3 числа, не превосходящих 3 · 63 = Суммы элементов множества также могут быть равны 95 + 97 = = 192 и всем числам, являющимся суммами числа 192 и сумм, составленных из чисел 3 · 2 𝑘 , 0 ¶ k ¶ 5. Это 64 делящихся на 3 числа, не меньших 192. Решения задач АТМО 2014 К тому же суммами элементов в могут быть число 95 и все числа, полученные как сумма числа 95 и сумм, составленных из чисел. Это 64 сравнимых с −1 по модулю 3 числа. Наконец, суммами элементов множества являются число и все числа, полученные как сумма числа 97 и сумм, составленных из чисел 3 · 2 𝑘 , 0 ¶ k ¶ 5. Это 64 сравнимых с 1 по модулю 3 числа. Следовательно, существует по крайней мере различных сумм, составленных из элементов множества. С другой стороны имеет 2 8 − 1 = 255 непустых подмножеств. Таким образом не имеет двух различных подмножеств с одинаковой суммой элементов, те, число 8 является 100-различимым. (б) Первое решение. Предположим, что число 9 является различимым. Тогда существует такое множество {s 1 , . . . , s 9 }, s 𝑖 < что в нём не существует двух различных подмножеств с одинаковой суммой элементов. Пусть 0 < s 1 < . . . < s 9 < Пусть есть множество всех подмножеств множества S, содержащих не менее 3 и не более 6 элементов, а — множество всех подмножеств множества, содержащих ровно 2, 3 или 4 элемента, больших чем s 3 Множество X состоит из 9 + C 4 9 + C 5 9 + C 6 9 = 84 + 126 + 126 + 84 = подмножеств множества. Множеством из X с наибольшей суммой элементов является. . . , s 9 }, а множеством с наименьшей суммой является. Таким образом, сумма элементов в каждом из множеств из есть число от s 1 + s 2 + до+ . . . + s 9 , а количество таких чисел ровно ( s 4 + . . . + s 9 ) − (s 1 + s 2 + s 3 ) + 1. Согласно принципу Дирихле это означает, что ( s 4 + . . . + s 9 ) − (s 1 + s 2 + s 3 ) + 1 ¾ 420, те Теперь подсчитаем количество подмножеств в. Заметим, что. . . , s 9 } имеет C 2 двухэлементных 6 трёхэлементных и четы- рёхэлементных подмножеств, в то время как имеет ровно подмножеств. Следовательно, количество подмножеств множества S в Y равно 6 + C 3 6 + C 4 6 ) = 8(15 + 20 + 15) = Множество в с наибольшей суммой элементов есть Решения задач АТМО ас наименьшей — {s 4 , s 5 }. Снова согласно принципу Дирихле+ s 2 + s 3 + s 6 + s 7 + s 8 + s 9 ) − (s 4 + s 5 ) + 1 ¾ те Складывая неравенства ( 1 ) и ( 2 ), получаем 2( s 6 + s 7 + s 8 + s 9 ) ¾ откуда следует, что+ 98 + 97 + 96 ¾ s 9 + s 8 + s 7 + s 6 ¾ 409, те, что противоречит условию s 9 < 100. Таким образом, число не является 100-различимым. Второе решение. Предложил Илья Богданов) Будем рассуждать от противного. Пусть. . . , x 9 — требуемые 9 чисел. Тогда все выражения вида x 2 ± . . . ± различны, одной чётности и отличны от 0. Поэтому минимальные модули двух из этих выражений не меньше, следующие по минимальности два модуля не меньше 3 и т. д., до 511. Значит . . . ± x 9 ) 2 ¾ 2(1 2 + 3 2 + . . . + 511 2 ) = = 2 · 256 · (4 · 256 2 − 1) 3 = 512 · 87 Тождество 1 2 + 3 2 + . . . + (2n − 1) 2 = n((2n) 2 − 1)/3 нетрудно доказать по индукции) С другой стороны, эта сумма равна 512( x 2 1 + . . . + x 2 так как все попарные произведения взаимно уничтожаются. Значит 1 + . . . + x 2 9 ¾ 87 381; так как все не превосходят 100, отсюда получаем, что они все не меньше, скажем, 80. Вычтем из всех x 𝑖 по 80. Получим числа от 0 до 20, их суммы из одинакового числа членов должны быть различными. Но имеется 9 = 126 таких сумм пои все эти суммы не превосходят 4 · 20 = 80. Противоречие. Задача 5 . Введём следующие обозначения X = AB∩` 𝑃 , Y = и ` 𝑃 ∩ см. рис. Без ограничения общности можно считать, что AX < BX. Пусть F = MP ∩ AB. Обозначим через R вторую точку пересечения и через S — такую точку Ω, что SR k AB; наконец, через T — такую точку, что RT k Поскольку является серединой дуги AB, касательная ` 𝑀 в точке к параллельна AB, поэтому ∠(AB, PM) = ∠(PM, ` 𝑃 ). Отсюда имеем ∠PRT =∠MPX =∠PFX =∠PRS. Таким образом, Q есть середина дуги окружности, следовательно, ST k ` 𝑄 . Соответствующие стороны треугольников и XYZ параллельны, и существует гомотетия, отображающая RST в XYZ. Решения задач АТМО 2015 Рис. Пусть — вторая точка пересечения XR и. Утверждается, что есть центр гомотетии. Поскольку D ∈ Ω, это означает, что окружности, описанные около треугольников и XYZ, касаются. Таким образом, остаётся доказать наше утверждение. Для этого достаточно показать, что SY. Из равенства ∠PFX = ∠XPF следует, что XF 2 = = XP 2 = XA · XB = XD · XR. Таким образом, XF : XD = XR : XF, значит, треугольники XDF и XFR подобны. Поэтому ∠DFX = ∠XRF = ∠DRQ = = ∠DQY и точки D, Y, Q и F лежат на одной окружности. Это означает, что ∠YDQ = ∠YFQ = ∠SRQ = 180 ◦ − ∠SDQ, откуда следует, что точки Y, D и S лежат на одной прямой, причём D находится между S и я олимпиада, 2015 год Задача 1 . Первое решение. Пусть XY пересекает в точках и, причём Q лежит между X и Y. Докажем, что точки V и W симмет- Решения задач АТМО 2015 ричны A и B относительно серединного перпендикуляра к PQ. Если это так, то — равнобедренная трапеция и AB = VW. Во-первых, заметим, что = ∠ AXY = ∠ APQ + ∠BAP = ∠ APQ + откуда следует, что APQ = ∠PZV = а значит, точка симметрична A относительно серединного перпендикуляра к PQ. Пусть точка W 0 симметрична B относительно серединного перпендикуляра к, и пусть Z 0 — точка пересечения YW 0 с ω. Достаточно доказать, что точки, X , D и лежат на одной окружности. Имеем ∠YDC = ∠PDB = ∠PCB + ∠QPC = ∠W 0 PQ + ∠QPC = ∠W 0 PC = Следовательно, C, Y и лежат на одной окружности. Тогда ∠CZB − ∠CZD = 180 ◦ − что завершает доказательство. Второе решение. Поскольку четырёхугольники BXDZ и вписанные, последовательно получаем ∠ZDY = ∠ZBA = ∠ZCY. Таким образом, четырёхугольник ZDCY вписанный. Далее, четырёхугольники ABZC и ZDCY вписанные, поэтому AZB = ∠ ACB = или 180 ◦ − ∠WZV, если Z лежит между W и C). Следовательно, хорды и VW равны, поскольку они стягивают равные или дополняющие друг друга до развёрнутого углы в ω. Третье решение. Поскольку четырёхугольники BXDZ и вписанные, последовательно получаем ∠ZDY = ∠ZBA = ∠ZCY. Таким образом, четырёхугольник ZDCY вписанный. Четырёхугольники BXDZ и ABZV вписанные, следовательно = ∠VZB = 180 ◦ − Поэтому AV. Так как четырёхугольники ZDCY и BCWZ вписанные, отсюда следует, что = ∠YZC = Значит Поскольку AV, получаем, что AVWB — равнобедренная трапеция, те Решения задач АТМО 2015 Задача. Ответ таких функций не существует. Предположим противное. Для любых элементов и b множества мы можем выбрать такое целое c, которое больше каждого из них. Поскольку a и c > b, имеем (a 4 b 4 c 4 ) = f (a 2 ) f (b 2 c 2 ) = f (a 2 ) f (b) f Поскольку b и c > a, имеем (a 4 b 4 c 4 ) = f (b 2 ) f (a 2 c 2 ) = f (b 2 ) f (a) f Используя эти соотношения, для любых элементов и b множества получаем (a 2 ) f (b) = f (b 2 ) f Следовательно (a 2 ) f (a) = f (b 2 ) f Отсюда следует, что существует такое положительное рациональное число, что (a 2 ) = k f (a) для всех a ∈ Подставляя в исходное функциональное уравнение, находим (ab) = f (a) f для всех, b ∈ S при a 6= Используя исходное функциональное уравнение и соотношения (и (2), получаем (a) f (a 2 ) = f (a 6 ) = f (a) f (a 5 ) k = f (a) f (a) f (a 4 ) k 2 = f (a) f (a) f для всех S. Следовательно, f (a) = k для всех a ∈ S. Полагая вис- ходном функциональном уравнении 2 и b = 3, получаем, что k = но 1 6∈ S. Противоречие. Задача 3 . Ответ Первое решение. Заметим, что+ 1 = 2(a 𝑖 + 1) или a 𝑖 +1 + 1 = a 𝑖 + a 𝑖 + 2 a 𝑖 + 2 = 2( a 𝑖 + 1) a 𝑖 + Следовательно+ 1 = 1 2 · 1 a 𝑖 + или+ 1 = a 𝑖 + 2 2( a 𝑖 + 1) = 1 2 · 1 a 𝑖 + 1 + 1 2 Решения задач АТМО Поэтому+ 1 = 1 2 𝑘 · 1 a 0 + где 0 или Умножая обе части на 2 𝑘 ( a 𝑘 + 1) и полагая a 𝑘 = 2014, получаем+ 1 + 2015 · 𝑘 X 𝑖 =1 " 𝑖 · где 0 или 1. Поскольку НОД(2, 2015) = 1, находим a 0 + 1 = и Следовательно 1 = 2015 · 𝑘 X 𝑖 =1 " 𝑖 · где или 1. Теперь необходимо найти наименьшее k, удовлетворяющее условию 2015 |2 𝑘 − 1. Так как 2015 = 5 · 13 · 31, применяя малую теорему Ферма, получаем 5 |2 4 − 1, 13|2 12 − 1 и 31|2 30 − 1. Также имеем НОК[4, 12, 30] = 60, поэтому 5|2 60 − 1, 13|2 60 − 1 и 31|2 60 − 1, откуда следует, что 2015 |2 60 − 1. Но 5-2 30 − 1, значит, k = 60 — наименьшее натуральное число, удовлетворяющее условию 2015 |2 𝑘 − 1. Итак, наименьшим натуральным, для которого a 𝑘 = 2014, является k = Второе решение. Ясно, что все члены последовательности — положительные рациональные числа. Для любого натурального имеем 1 или 1 − a 𝑖 +1 . Поскольку 0, получаем 1 если 1, 2 a 𝑖 +1 1 − если Таким образом, a 𝑖 однозначно определяется поте. можно считать что, начиная с 2014, мы двигаемся к началу последовательности, пока не встретим натуральное число. Проведём соответствующие вычисления 1 , 2013 2 , 2011 4 , 2007 8 , 1999 16 , 1983 32 , 1951 64 , 1887 128 , 1759 256 , 1503 512 , 991 1024 , 1982 33 , 1949 66 , 1883 132 , 1751 264 , 1487 528 , 959 1056 , 1918 97 , 1821 194 , 1627 388 , 1239 776 , 463 1552 , 926 1089 , 1852 163 , 1689 326 , 1363 652 , 711 1304 , 1422 593 , 829 1186 , 1658 357 , Решения задач АТМО 2015 107 1301 714 , 587 1428 , 1174 841 , 333 1682 , 666 1349 , 1332 683 , 649 1366 , 1298 717 , 581 1434 , 1162 853 , 309 1706 , 618 1397 , 1236 779 , 457 1558 , 914 1101 , 1828 187 , 1641 374 , 1267 748 , 519 1496 , 1038 977 , 61 1954 , 122 1893 , 244 1771 , 488 1527 , 976 1039 , 1952 63 , 1889 126 , 1763 252 , 1511 504 , 1007 1008 , 2014 Мы выписали 61 число. Значит Замечание. Второе решение перегружено вычислениями. Посчитав несколько первых членов, можно заметить некоторые закономерности, которые легко доказываются. Это проделано в следующем решении. Третье решение. Начинаем с a 𝑘 = m 0 /n 0 , где 2014 и n 0 = как во втором решении. Также двигаясь к началу последовательности, находим a 𝑘 −𝑖 = для ¾ 0, где (m 𝑖 − n 𝑖 , если n 𝑖 , (2 m 𝑖 , n 𝑖 − если Легко заметить, что+ n 𝑖 = 2015, 1 ¶ m 𝑖 , n 𝑖 ¶ 2014 и НОД(m 𝑖 , n 𝑖 ) = для ¾ 0. Поскольку a 0 ∈ N и НОД(m 𝑘 , n 𝑘 ) = 1, нам требуется n 𝑘 = Ясно, что ( m 𝑖 , n 𝑖 ) ≡ (−2 𝑖 , 2 𝑖 ) (mod 2015) для 0, 1, . . . , Таким образом, 2 𝑘 ≡ 1 (mod 2015). Как ив первом решении, наименьшим таким является k = 60. Значит, n 𝑘 ≡ 1 (mod 2015). Но поскольку 1 ¶ n 𝑘 , m 𝑘 ¶ 2014, отсюда следует, что a 0 — целое число. Задача 4 . Первое решение. Рассмотрим прямую на плоскости и такую точку на ней, что не параллельна никакой из 2n наших прямых. Будем поворачивать относительно P против часовой стрелки, пока она не станет параллельной одной из 2 n прямых. Запомним эту прямую и продолжим такие вращения, пока не переберём все прямые. Теперь все наши 2 n прямых упорядочены по мере того, как они нами выбирались. Обозначим их через. . . , ` 2𝑛 . Ясно, что существуют такие {1, . . . , 2n − 1}, что ` 𝑘 и ` 𝑘 +1 разного цвета. Введём на плоскости систему координат с осями и OY. Рассмотрим две биссектрисы углов между ` 𝑘 и ` 𝑘 +1 (см. рис. Если поворачивать прямую ` 𝑘 +1 против часовой стрелки, она станет параллельной одной из биссектрис раньше, чем станет параллельной другой. Пусть эта биссектриса будет осью , а другая — осью OY. Используем ориентированные углы для прямых и определим ∠(s, как вещественное число [0, π), обозначающее такой угол в радианах Решения задач АТМО Рис. что, когда поворачивается против часовой стрелки на угол ∠(s, радиан, она становится параллельной. Заметим, что не существует такого 1, . . . , 2n, что ∠(X, l 𝑖 ) лежит между ∠(X , ` 𝑘 ) и ∠(X , Поскольку все 2 n прямых различны, множество S всех точек пересечения j) конечно. Рассмотрим прямоугольник с двумя противоположными вершинами, лежащими на, и двумя другими вершинами, лежащими на. Ясно, что можно увеличивать длины сторон этого прямоугольника до бесконечности. Поэтому существует такой прямоугольник, который содержит все точки из S внутри себя. Поскольку стороны прямоугольника параллельны осям координат, он ограничен прямыми ±a, y = ±b, где a, b > Рассмотрим окружность , касающуюся справа стороны прямоугольника, лежащей на, а также касающуюся и. Докажем, что эта окружность пересекает ровно в 2n − 1 точках и R — ровно в 2 n − 1 точках. Поскольку C касается и, причём эти прямые разного цвета, достаточно показать, что пересекается с любой другой из 2n − прямых ровно в двух точках. Заметим, что никакие две прямые не пересекаются на окружности, поскольку их точки пересечения лежат в множестве, которое находится внутри R. Возьмём любую прямую из этих 2n − 2 прямых. Пусть L пересекает ив точках и N соответственно (M и N могут и совпадать. Заметим, что и N лежат внутри R. Возможны два случая пересекает R на x = −a и на x = a; (2) L пересекает R на y = −b и на y = Во втором случае ∠(` 𝑘 , L) и ∠(L, ` 𝑘 +1 ) оба должны быть положительными, и поэтому ∠(X , L) должен находиться между ∠(X , ` 𝑘 ) Решения задач АТМО 2015 и ∠(X , ` 𝑘 +1 ), что приводит к противоречию. Следовательно, имеет место случай 1. Тогда пересекает ровно в двух точках. Второе решение. Вращая чертёж, можно добиться того, чтобы не было вертикальных прямых. Пусть. . . , ` 2𝑛 — данные прямые в порядке возрастания наклона. Тогда существует такое, что прямые iiiiиiiii+1разного цвета. Вращая систему координат и циклически переобозначая прямые, можно добиться того, что. . . будут расположены в порядке возрастания наклона, а ` 1 и ` 2𝑛 будут разного цвета, причём вертикальных прямых не будет. Пусть D — окружность с центром вначале координат и достаточно большим радиусом, удовлетворяющая следующим условиям все точки пересечения прямых лежат внутри каждая прямая ` 𝑖 пересекает D в двух точках итак, что A 𝑖 лежит на правой полуокружности (с положительным, а на левой. Заметим, что точки A 𝑖 и B 𝑖 расположены на в следующем порядке против часовой стрелки. . . , A 𝑛 , B 1 , B 2 , . . . , B 𝑛 . (Если A 𝑖 +1 встречается раньше, то лучи r 𝑖 и r 𝑖 +1 (определённые ниже) должны пересекаться вне D.) Для любого луч определяется как половина прямой, начинающаяся в точке A 𝑖 и идущая вправо. Пусть — любая окружность, касающаяся r 1 и r 2𝑛 и лежащая справа от. Тогда C пересекает A 2n −1 A 2n A 2 A 1 B 1 B 2 B 2n −1 B 2n D C r 2n r 1 r 2n −1 r 2 |