Е. Р. Байсалов, да. ЕлиусизовМатематические олимпиады
 Скачать 2.18 Mb.
|
|
Лемма 1. Для любых натуральных a, b, c (a > 1) справедливо равенство ( a 𝑏 − 1, a 𝑐 − 1) = a (𝑏,𝑐) − Лемма 2. Если a, b, c, d — натуральные числа и (a, b) =1, (c, то (a · b, c · d) = (a, c) · (a, d) · (b, c) · (b, Имеет место равенство+ 1, 2 𝑚 − 1) = (2 𝑛 + 1, 2 𝑛 − 1) = Поэтому 1)(2 (𝑚,𝑛) + 1) = 2 2(𝑚,𝑛) − 1 = 2 (2𝑚,2𝑛) − 1 = = (2 2𝑚 − 1, 2 2𝑛 − 1) = ((2 𝑚 − 1)(2 𝑚 + 1), (2 𝑛 − 1)(2 𝑛 + 1)) = = (2 𝑚 − 1, 2 𝑛 − 1) · (2 𝑚 − 1, 2 𝑛 + 1) · (2 𝑚 + 1, 2 𝑛 − 1) · (2 𝑚 + 1, 2 𝑛 + 1) = = (2 (𝑚,𝑛) − 1) · (2 𝑚 − 1, 2 𝑛 + 1) · (2 𝑚 + 1, 2 𝑛 − 1) · (2 𝑚 + 1, 2 𝑛 + Следовательно, (2 𝑚 + 1, 2 𝑛 + 1) | 2 𝑑 + Отсюда с учётом равенства ( 1 ) получаем 2 𝑑 + 1 = (2 𝑚 + 1, 2 𝑛 + 1). Решения задач МОШП 2013 Рис. Задача. а) Пусть прямые AI, BI, CI второй раз пересекают описанную окружность треугольника в точках соответственно (см. рис. Тогда можно доказать, что C 0 I = и B 0 I = B 0 C лемма о трезубце, а значит, треугольники AIC 0 и AIB 0 равнобедренные, B 0 C 0 ⊥ AI, и делит пополам. Пусть ∠A 2 IC 0 = ∠A 1 IC = α. Тогда ∠A 1 CI = ∠ICA = 90 ◦ − Следовательно, в равнобедренном треугольнике OAC 0 выполня- ется равенство ∠AOC 0 = 180 ◦ − 2α, а значит, ∠OAC 0 = α. Из соотношений и ∠OAC 0 = α = получаем, что точка A 2 симметрична точке относительно B 0 C 0 . Следовательно, прямая AA 2 симметрична прямой относительно B 0 C 0 . Отсюда имеем Аналогично доказывается, что OI и что прямая симметрична прямой относительно Пусть теперь AA 2 второй раз пересекает описанную окружность треугольника в точке X б) Для решения этого пункта достаточно доказать, что прямая BX симметрична прямой относительно A 0 C 0 . Имеем A 0 C 0 , BX ) = 1 2 ( _ C 0 X − _ BA 0 ) = ∠C 0 AX − ∠BAA 0 = = ∠C 0 IO − ∠A 0 C 0 I = те. прямая симметрична IO относительно A 0 C 0 , что и требовалось доказать. Задача 3 . Ответ f (n) = n для всех n ∈ N. 1. Предположим, что функция ограничена, те. существует такое, что f (n) ¶ c для всех n ∈ N. Пусть M = max f (n) и m 0 ∈ N Решения задач МОШП такое, что (m 0 ) = M. Положив в исходном уравнении m = m 0 , получим противоречие. Таким образом, функция не ограничена. Далее предположим, что существует N, для которого (m 0 ) < m 0 . Тогда, положив в данном уравнении m 0 , получим ( f (m 0 ) f (n) + m 0 ) = f (m 0 f (n)) + f (m 0 ) > f (m 0 f для всех N. Так как f — неубывающая функция, получаем, что (m 0 ) f (n) + m 0 > m 0 f или (n) < m 0 m 0 − f для всех N. Противоречие, так как функция f не ограничена. Итак (n) ¾ n для всех n ∈ N. Пусть f (1) = c. Подставив вис- ходное уравнение 1, получим (c f (n) + 1) = f ( f (n)) + c для всех n ∈ Положив в исходном уравнении 1, m = n, получим (c f (n) + n) = f (n) + f (cn) для всех n ∈ Заменив в формуле ( 2 ) n на f (n), а затем применяя монотонность (c f (n)) ¶ f (c f (n) + 1) и ( 1 ), получим (c f ( f (n)) + f (n)) = f ( f (n)) + f (c f (n)) ¶ ¶ f ( f (n)) + f (c f (n) + 1) = 2 f ( f (n)) + Следовательно, для всех N выполняются неравенства ( f (n)) + c ¾ f (c f ( f (n)) + f (n)) ¾ c f ( f (n)) + f или c) f ( f (n)) ¾ f (n) − а это возможно только в случае Тогда из равенства ( 1 ) следует, что ( f (n) + 1) = f ( f (n)) + 1. Теперь простой индукцией можно доказать, что (n) = n для всех n ∈ что удовлетворяет исходному уравнению. Задача_4'>Задача 4 . Рассмотрим всевозможные многочлены вида+ q 1 x + . . . + где. . . , q 𝑘 −1 ∈ {0, 1, . . . , p − 1}. Заметим, что всего существует таких многочленов. Пронумеруем их все. . . , f 𝑝 𝑘 ( x). Решения задач МОШП 2014 Также пронумеруем всех артистов внутри каждой группы, 2, . . . , для всех 1, . . . , Тогда наша схема проведения кастингов будет следующей для каждого ив кастинге под номером на роль номер мы выбираем артиста с номером 1) + 1 (если f 𝑗 ( i − 1) + 1 > выберем любого артиста из этой группы). Теперь докажем, что эта конструкция удовлетворяет условию за- дачи. Рассмотрим группы с номерами. . . , b 𝑘 (1 ¶ b 1 <. . . 𝑘 ¶ n) и соответствующих артистов из этих групп с номерами. . . , c 𝑘 (1 ¶ c 𝑖 ¶ для всех, i = 1, . . . , k) соответственно. Согласно интерполяционной формуле Лагранжа существует такой многочлен степени менее k, что g(b 𝑖 − 1) = c 𝑖 − 1 для всех i = 1, . . . , который представим в виде 1) Y 𝑗 6= 𝑖,1¶𝑗¶𝑘 x − b 𝑗 + 1 b 𝑖 − Пусть g(x) (mod p), deg Q = deg g < k и все коэффициенты многочлена принадлежат множеству, 1, . . . , p − 1}. Тогда существует число, 1 ¶ i ¶ p 𝑘 , для которого f 𝑖 ( x). Это означает, что все артисты. . . , из групп. . . , соответственно участвовали в i-м кастинге, так как для всех j = 1, . . . , k выполняется равенство 1) + 1 = я олимпиада, 2014 год Задача 1 . Ответ 2n − Пронумеруем все столбцы (слева направо) и строки (снизу вверх) числами 1, 2, . . . , n. Каждая клетка при этом будет иметь свои координаты) (номер столбца, номер строки). Пронумеруем монеты в таблице следующим образом. Рассмотрим клетку (где есть монета) с наименьшей координатой. Если таких клеток несколько, то среди них выбираем клетку с наименьшей координатой. Выбранная монета будет первой. Оставшиеся монеты пронумеруем аналогичным образом. Пусть в таблице монет с координатами ( a 1 , b 1 ), ( a 2 , b 2 ), . . . , (a 𝑘 , b 𝑘 ). Заметим, что для всех ¶ i ¶ k − 1, выполнено неравенство b 𝑖 ¶ b 𝑖 +1 Решения задач МОШП Если для некоторого, имеет место равенство b 𝑖 = b 𝑖 +1 , то монеты с номерами и i + 1 лежат водной строке. Значит, a 𝑖 < и+ b 𝑖 < a 𝑖 +1 + Если же b 𝑖 +1 , то неравенство невозможно, так как иначе монета будет одновременно правее и ниже, чем монета i + Таким образом и+ b 𝑖 < a 𝑖 +1 + Нетрудно заметить, что 2 ¶ a 𝑖 + b 𝑖 ¶ 2n. Так как последовательность сумм+ строго возрастает, в ней не более чем 2 n − 1 членов. Данная оценка достигается, если расставить монеты вовсе клетки самого левого столбца и самой верхней строки. Задача 2 . Первое решение. Пусть AC >CB, и AA 1 , BB 1 — высоты треугольника см. рис. Известно, что ∠ACM = ∠SCB см. свойство симедианы треугольника. Так как ∠HAC = ∠HBC, получаем, что ∠HAC + ∠ACM = ∠HBC + ∠SCB = те. точки M 𝑎 , M 𝑏 , S 𝑎 , S 𝑏 лежат на одной окружности. A B C M S B 2 A 2 X Y A 1 B 1 H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H M a M b S a S b ````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````` ` Рис. 46 Решения задач МОШП 2014 Докажем, что HM 𝑏 . Проведём перпендикуляр к прямой в точке C. Пусть AA 1 ∩ ` = A 2 , BB 1 ∩ ` = B 2 , аи такие точки на прямой, что AX k CM k BY. Тогда CX = CY. Имеем CB 2 = CB 1 · CA = CA 1 · CB = CY · а значит CA 2 , те. прямая лежит на серединном перпендикуляре к отрезку. Следовательно, и поэтому точки, S 𝑏 и M 𝑎 также лежат на одной окружности. Значит, ∠M 𝑎 S 𝑏 B 2 = ∠M 𝑎 CB 2 = 90 ◦ . Перпендикулярность прямых M 𝑏 S 𝑎 и HM 𝑎 доказывается аналогично. Второе решение. Предложил Александр Шакиев, 10 класс, лицей 165 г. Алматы.) Также как ив первом решении, воспользуемся тем, что ∠ACM = ∠SCB. Пусть точка T симметрична точке H относительно точки см. рис. Также из известных свойств следует, что точка лежит на описанной окружности треугольника ABC, TC — диаметр этой окружности и ∠ACT = ∠BCH. Отсюда получим равенство = Рис. 47 Решения задач МОШП Заметим, что треугольники CHB 1 и CTB подобны. Если L = CM ∩ то из равенства (1) следует, что HS 𝑏 S 𝑏 B 1 = TL LB Нетрудно заметить, что — параллелограмм. Поэтому TL LB = HM 𝑎 M 𝑎 A , а значит, HS 𝑏 S 𝑏 B 1 = HM 𝑎 M 𝑎 A Из последнего следует, что M 𝑎 S 𝑏 , или HB 1 . Перпендикулярность прямых M 𝑏 S 𝑎 и HM 𝑎 доказывается аналогично. Задача 3 . Первое решение. Если a ¾ b ¾ c или c ¾ b ¾ a, то c 2 )( b − a) ¶ 0 ⇔ a 3 b + b 3 c + c 3 a ¶ b(a 3 + abc + В силу неравенства между средним арифметическими средним геометрическим для любых положительных чисел имеем+ abc + c 3 3 a 3 + abc + c 3 3 a 3 + abc + c 3 3 ¶ ¶ 1 4 b 3 + a 3 + abc + c 3 3 + a 3 + abc + c 3 3 + a 3 + abc + c 3 3 = = 1 4 ( a 3 + b 3 + c 3 + abc) = те. Остальные случаи доказываются аналогично: если a ¾ c ¾ b или b ¾ c ¾ a, то a 2 )( c − b) ¶ 0 ⇒ a 3 b + b 3 c + c 3 a ¶ c(a 3 + abc + b 3 ) ¶ если же ¾ a ¾ c или c ¾ a ¾ b, то b 2 )( a − b) ¶ 0 ⇒ a 3 b + b 3 c + c 3 a ¶ a(b 3 + abc + c 3 ) ¶ Второе решение. Предположим, что набор, b, c} совпадает сна- бором, y, z}, где x ¾ y ¾ z. Тогда набор {x 2 , y 2 , z 2 } совпадает с набором, а набор {xy, xz, yz} — с набором {ab, bc, ca}, причём выполнены неравенства y 2 ¾ и ¾ xz ¾ yz. Тогда по транс- неравенству (см. теорему нас) получаем+ b 3 c + c 3 a = a 2 · ab + b 2 · bc + c 2 · ca ¶ ¶ x 2 · xy + y 2 · xz + z 2 · yz = y(x 3 + xyz + z 3 ) = y(4 − y 3 ). Решения задач МОШП 2014 167 Остаётся доказать, что y 3 ) ¶ 3. Но это следует из неравенства о средних для четырёх чисел+ 1 + 1 + 1 ¾ 4y ⇔ y(4 − y 3 ) ¶ Задача. Ответ f (n) = при всех Пусть | f (kn)=k 2 f (n) } для любого n ∈ N и A 1 ={k | f По условию имеем следующие неравенства (mn) ¾ f (m) f (n), (1) f (m 2 + n 2 ) ¾ ( f (m) + f (n)) 2 , (2) f (m) 2 + f (n) 2 + 2 f (mn) ¾ f (m 2 + Лемма 1. Если f (mn) = f (m) f (n), то f (m 2 + n 2 ) = ( f (m) + f Доказательство. Легко следует из неравенств ( 2 ) и (При из неравенства ( 1 ) следует, что (1)¾ f (1) 2 , а значит (1) = 1. При m = 1 выполнено равенство f (mn) = f (m) f (n), и тогда по лемме 1 имеем (n 2 + 1) = ( f (n) + для любого Из равенства ( 4 ) при 1 получаем f (2) = 4. Из соотношений) и ( 3 ) при n имеем (n) 2 + 2 f (n 2 ) ¾ f (2n 2 ) ¾ f (2) f (n 2 ) = 4 f Тогда (n) 2 ¾ f (n 2 ). При n из неравенства ( 1 ) имеем (n 2 ) ¾ f Следовательно (n 2 ) = f для любого Лемма 2. Если f (kn 2 ) = k 2 f (n) 2 = k 2 f (n 2 ) для любого N, то Доказательство. Имеем f (k) = f (k · 1 2 ) = k 2 f (1) 2 = k 2 , k 2 f (n) 2 = = f (kn 2 ) ¾ f (kn) f (n) ⇒ f (kn) ¶ k 2 f (n) и f (kn) ¾ f (k) f (n) = k 2 f (n) ⇒ ⇒ f (kn) = k 2 f (n) ⇒ k ∈ Так как при n справедливо равенство f (mn) = f (m) f (n), из леммы 1 получим, что (2n 2 ) = 4 f (n) 2 , а из леммы 2 — что (2n) = 4 f (n) для любого n ∈ Следовательно, 2 ∈ A. Из неравенства (получаем, что если p 1 . . . то (n) ¾ f (p 1 ) . . . f (p 𝑘 ). (7) |