Е. Р. Байсалов, да. ЕлиусизовМатематические олимпиады
 Скачать 2.18 Mb.
|
|
Случай 1: a ≡ 1 (mod p). Тогда отклонение существенного подмножества равно 2 (mod Случай 2: a ≡ −1 (mod p). Тогда отклонение существенного подмножества, где T получается из S заменой (p + 1)/2 на (p − 1)/2 ≡ ≡ −(p + 1)/2 (mod p), равно ∆ 𝑇 = Π 𝑇 − Π 𝑇 ≡ 1 − (−1) ≡ 2 (mod Теперь докажем, что 2 — наименьший возможный остаток. Заметим, что Π 𝑠 = −1 снова по теореме Вильсона. Так как не является квадратичным вычетом (см. определение нас) для простого числа вида 4 k + 3, всегда выполняется неравенство Π 𝑠 6= Π 𝑠 (mod p). Другими словами, отклонение не делится на p. Докажем Решения задач МОШП утверждение от противного. Допустим, что отклонение некоторого подмножества равно Π 𝑠 = 1. Тогда m + 1 (mod p), Π 𝑠 ≡ m (mod для некоторого {2, 3, . . . , p − 3} и m 2 + m ≡ −1 (mod p). Отсюда следует, что 1 (mod p), и по малой теореме Ферма p − 1 делится на 3. Противоречие. Замечание. Как видно из последнего абзаца решения, ответ задачи остаётся неизменным, если убрать условие существенности и условие о том, что подмножество должно содержать ( p − элементов. Эти условия добавлены, чтобы избежать вопросов об остатках отрицательных чисел при делении на и чтобы слегка усложнить построение примера нужного подмножества. Задача 4 . Предположим от противного, что нет прямых l и удовлетворяющих условию задачи. Пусть l ∈ L — произвольная прямая. Найдутся такие две точки a, b ∈ l, что a, b — точки пересечения l с прямыми из L и все точки пересечения прямой с прямыми из семейства L лежат на отрезке, b]. Такой отрезок [a, b] назовём большим отрезком прямой Через точку большого отрезка [a, b] проходит ещё одна прямая, скажем l 0 . Тогда по предположению эта точка служит концом большого отрезка прямой l 0 Обозначим через множество точек, являющихся концами больших отрезков. Если [ a, b] — большой отрезок, то пишем a Rb и говорим, что точки, b связаны отношением R. Лемма 1. Пусть наконечном множестве A задано иррефлексивное симметричное отношение, те. Допустим, что для каждой точки a ∈ A существуют ровно две такие точки A, что aRb. Тогда A разбивается наконечные циклы длины не меньше Доказательство. Очевидно. Но в нашем случае имеется единственный R-цикл, ион имеет нечётную длину. Лемма циклы имеют нечётные длины. Доказательство. Рассмотрим цикл a 0 Ra 1 Ra 2 R . . . длины+ 1, и пусть a = a 0 , b = a 1 . Точки a 𝑖 и a 𝑖 +1 лежат по разные стороны Решения задач МОШП 2007 от прямой, 2 ¶ i ¶ n − 1, так как любые два больших отрезка должны пересекаться, и a 𝑛 лежит стой же стороны, что, так как иначе большие отрезки [ a 𝑛 , a 0 ] и [ a 1 , a 2 ] не пересекаются. Значит, n чётно. Лемма 3. Имеется единственный R-цикл. Доказательство. Пусть a 0 Ra 1 Ra 2 R . . . a 𝑛 Ra 0 — цикл. Допустим, что существует большой отрезок [ b, c] вне этого цикла. Прямая отрезка делит плоскость на две полуплоскости. Поскольку большие отрезки должны пересекаться, смежные (по) точки цикла должны лежать на разных полуплоскостях. Но это невозможно, так как цикл состоит из нечётного количества точек. Из доказанных лемм получаем противоречие с предположением, так как 2006 — чётное число. 6-я олимпиада, 2007 год Задача 1 . Покажем решение, входе которого получатся все части ответа. Заметим, что ab + b 2 Если между простыми числами b существует только одно простое число, то операция упрощения, применённая к паре (a, b), даёт либо, либо c. Таким образом, дыра, существующая между a и может исчезнуть или сместиться вниз на одну «ступеньку». Максимально возможное число — 1999, и это значение не зависит от вычеркнутого вначале числа 2 < q < 2003. Алгоритм получения состоит в применении операции упрощения к наибольшим числам множества, не считая 2003. Перед последней операцией на доске остаётся пара 2, 2003 или 3, 2003. Последнее упрощение даёт Алгоритм получения минимально возможного значения состоит в применении операции упрощения к наибольшим числам множества. Если дыра, образованная стиранием числа, на каком-то шаге исчезнет, то получим минимальное число 2, иначе получим 3. Легко видеть, что дыра исчезает, если ¾ 17. В этом случае минимально возможное значение равно 2. С другой стороны, если 3 ¶ q ¶ 13, то несложный анализ показывает, что она не исчезает при любых действиях школьника. В этом случае минимально возможное значение равно 3. Решения задач МОШП Рис. Задача. Пусть I — центр вписанной, J — центр вневписанной окружности треугольника, и пусть прямая JK во второй раз пересекает вписанную окружность в точке см. рис. 38 ). Пусть E — середина JK, M — середина KP, O 𝑎 — середина. Так как — середина хорды KP окружности, получаем, что ∠IMK = Поэтому точки, C, M лежат на окружности с диаметром IJ. Следовательно. Но JK · KM = EK · KP. Поэтому BK · KC = = EK · KP, те. точки B, C, P, E лежат на другой окружности ω 0 . Также понятно, что IK, IK ⊥ BC, те лежит на серединном перпендикуляре к отрезку, или BE = CE. Следовательно, касательные к ив точках и E параллельны, а это значит, что касательные к этим окружностям в точке совпадают. Таким образом, окружности и касаются в точке. Значит, точки P и S совпадают. Задача 3 . Ответ M = 1 Неравенство+ b 3 + c 3 − 3abc ¾ M(|a − b| 3 + |b − c| 3 + |c − a| 3 ) Решения задач МОШП 2008 для 1/2 следует из тождества+ b 3 + c 3 − 3abc) = (a + b + c)((a − b) 2 + (b − c) 2 + (c − и из очевидных неравенств вида ( x + y + z)(x − y) 2 ¾ |x − y| 3 . Неулуч- шаемость оценки 1/2 следует из того, что при больших a и при малых, c значение a 3 + b 3 + c 3 − 3abc может быть сколь угодно близким ка значение выражения − b| 3 + |b − c| 3 + |c − может быть сколь угодно близким к Задача. Ответ 1) легко убедиться, что многочлены x 2 + x +100, x 2 + x + 101, −2x 2 + x − 200, x + 1 образуют особое множество 2) нет, не существует. Докажем утверждение от противного. Пусть существует особое множество многочленов f 1 , f 2 , f 3 , f 4 , f 5 с вещественными коэффициентами. Если многочлен не имеет корней, то для любых значений переменных знак многочлена будет постоянным в силу его непрерыв- ности. Рассмотрим полный граф с множеством вершин, 2, 3, 4}. Ребро, j) называется положительным отрицательным, если многочлен 3 f 5 + f 𝑖 + является положительным (отрицательным. Из предположения следует, что в графе нет положительных (отрицательных) треугольников. Действительно, если, например 3 f 5 + f + g > 0, 2 3 f 5 + g + h > 0 и 3 f 5 + f + h > то+ f + g + h > 0, что противоречит определению особого множества. Следующая лемма легко доказывается. Лемма. В двухцветном полном графе с четырьмя вершинами без одноцветных треугольников существует пара рёбер трёх общих вершин каждого из цветов. С помощью леммы мы получаем противоречивые неравенства+ f 2 + f 3 + f 4 + 4 3 f 5 > 0, f 1 + f 2 + f 3 + f 4 + 4 3 f 5 < я олимпиада, 2008 год Задача 1 . Имеем a 2𝑏 + c ≡ (d − a) 2𝑏 + c (mod d). Действительно, так как (d − a) 2𝑏 = (a 2 − (d − a) 2 ) × × a 2(𝑏 −1) + a 2(𝑏 −2) ( d − a) 2 + . . . + a 2 ( d − a) 2(𝑏 −2) + (d − a) 2(𝑏 −1) , Решения задач МОШП получаем, что (d − a) 2𝑏 . (a + (d − a)) = а значит, ( d − a) 2𝑏 + c ¾ d, и, следовательно, (d − a) 2𝑏 ¾ (d − c) ¾ Тогда a ¾ 2𝑏 p a, те, что и требовалось доказать. Задача 2 . Пусть для определённости AC ¶ AB. Тогда точка принадлежит отрезку и лежит между A и см. рис. Заметим эквивалентность следующих равенств+ AA 1 = BA 1 ⇔ AC + AC 0 − A 1 C 0 = C 0 B + A 1 C 0 ⇔ ⇔ A 1 C 0 = 1 2 AC ⇔ A 1 C 0 = Рис. Значит, треугольник A 1 A 0 C 0 равнобедренный, поэтому ∠C 0 A 1 A 0 = =∠A 1 A 0 C 0 . Следовательно, поскольку A 0 B 0 ). Тогда A 0 A 1 является биссектрисой ∠C 0 A 0 B 0 . Аналогично B 0 B 1 явля- ется биссектрисой ∠C 0 B 0 A 0 и C 0 C 1 является биссектрисой Отсюда следует, что прямые A 0 A 1 , B 0 B 1 и C 0 C 1 пересекаются в центре вписанной окружности треугольника A 0 B 0 C 0 Задача 3 . Рассмотрим правильный угольник (вписанный веди- ничную окружность, в котором из множества сторон и диагоналей отмечены отрезков. Наша задача эквивалентна следующей надо доказать, что некоторые из неотмеченных отрезков можно покрасить (включая концы) в красный цвет так, чтобы из каждой красной вершины исходило ровно красных рёбер. Назовём k-отрезком отрезок, стягивающий дугу длины. Возможны следующие случаи. Случай 1: какие-то два отмеченных отрезка имеют общую вершину. В этом случае выберем эту вершину и ещё n − 2 вершины так Решения задач МОШП 2008 чтобы в каждом отмеченном отрезке была выбрана хотя бы одна вершина, и удалим эти вершины (их количество равно 1 +(n−2) = Оставшиеся вершины образуют полный граф с+ 1 вершинами, т. е. любые две оставшиеся вершины соединены неотмеченным отрезком. Покрасив все эти отрезки в красный цвет, мы решим задачу. Случай 2: отмеченные отрезки не имеют общих вершин. Подслучай 2.1: n чётно. Без потери общности (с помощью соответствующей нумерации вершин) можно считать, что были отмечены большие диагонали нашего многоугольника. Покрасив в красный цвет все k-отрезки для k = 1, 2, . . . , n/2, мы решим задачу. Подслучай 2.2: n нечётно. Снова без потери общности можно считать, что были отмечены отрезки нашего многоугольника (т. е. его стороны через одну. Покрасив в красный цвет все неотмечен- ные k-отрезки для k = 1, 2, . . . , (n + 1)/2, мы решим задачу. Задача 4 . Ответ P(x) = dx + c, где d 6= 0, c — рациональные числа. Если P(x) — постоянный многочлен, те. равен константе, то условие не выполняется. Поэтому далее будем считать многочлен непо- стоянным. Сначала докажем, что все коэффициенты многочлена) являются рациональными числами. Пусть deg P = n. Рассмотрим n + различных рациональных чисел. . . , и такие рациональные числа. . . , x 𝑛 +1 , что r 𝑖 , 1 ¶ i ¶ n + 1. Тогда из интерполяционной формулы Лагранжа следует, что 𝑖 ( x − x 𝑗 ) Q 𝑗 6= 𝑖 ( x 𝑖 − Отсюда нетрудно заметить, что коэффициенты многочлена рацио- нальные. Заметим, что удовлетворяющий условию многочлен, умноженный на некоторую натуральную константу, снова удовлетворяет условию задачи. Поэтому можно считать, что) имеет целые ко- эффициенты. Пусть старший коэффициент равен a 𝑛 (пусть для определённости он положительный, а младший равен a 0 Рассмотрим числа вида r = p 1 + a 0 , где простое число. Тогда существуют такие целое число и натуральное число q, что (p, q) = и. Тогда нетрудно заметить, что p|r −a 0 = и, следова- Решения задач МОШП 2009 тельно, p ∈ {−1, 1, −p 1 , p 1 }. Поскольку таких r существует бесконечно много, получаем, что и пар ( p, q) также бесконечно много. Теперь покажем, что существует бесконечно много пар ( p, q), для которых {−p 1 , p 1 }. В противном случае |p/q| ¶ 1, но число r может быть сколь угодно большим. Тогда с некоторого момента равенство не будет возможным. Для определённости допустим, что существует бесконечно много пар ( p, q), для которых p = если знак отрицательный, то соответствующие рассуждения аналогичны. Так как количество делителей числа a 𝑛 конечно, существуют бесконечное множество простых чисел p 1 и постоянное число — делитель числа a 𝑛 , для которых) = p 1 + Рассмотрим новый многочлен (x) = P(x/d). Тогда существует бесконечно много чисел Z, для которых f (a) = a + и, следовательно. Итак, получаем, что P(x) = dx + c — линейный многочлен. 8-я олимпиада, 2009 год Задача 1 . Первое решение. Перепишем исходное неравенство в виде+ b + c) ¾ a + b + c + В силу неравенства Коши о среднем арифметическом и среднем геометрическом имеем 3 p abc ¾ 1 и a + b + c ¾ 3 Тогда 3 1 a + 1 b + 1 c ( a + b + c) ¾ a + b + и 3 1 a + 1 b + 1 c ( a + b + c) ¾ 2 3 3 3 p abc 3 3 p abc = Суммируя два последних неравенства, получим требуемое неравен- ство. Второе решение. Рассмотрим два случая. Случай 1: a + b + c ¾ 3. Поскольку 3 p abc ¾ получаем, что+ b + c) ¾ 3(a + b + c) ¾ a + b + c + 6. Решения задач МОШП 2009 Случай 2: a + b + c < 3. Тогда+ b + c) ¾ 3 3 p abc 3 3 p abc = 9 > a + b + c + Задача. Обозначим точки и углы, как на рис, тогда ∠C 2 CB = ∠C 2 CA = ∠C 2 A 2 A = γ, ∠ A 2 CB = ∠A 2 AB = ∠A 2 AC = ∠A 2 C 2 C = и AC 2 C = ∠CA 2 A = ∠ABC = Рис. По теореме синусов для 4C 2 AC 1 и 4C 2 AI легко получим ∠C 2 IA sin ∠AC 2 I = sin γ sin α · sin( α + γ) sin Аналогично для получаем ∠IA 2 C sin ∠A 2 IC = sin γ sin α · sin 2 β sin( α + γ) Тогда C 2 C 1 C 1 I · IA 1 A 1 A 2 = sin γ sin α 2 (1) Пусть прямая пересекает отрезок в точке. Тогда из теоремы Чевы, применённой для, получим Решения задач МОШП Далее, по теореме синусов для треугольников и A 2 IN, пользуясь равенством (2), получим sin ∠C 2 IN sin ∠NIA 2 = C 2 N Также для треугольников и CIM по теореме синусов, пользуясь равенством (3), получим sin ∠AIM sin α = MI sin ∠NIA 2 sin α = MI sin ∠C 2 IN sin γ = MI sin ∠MIC sin γ = что и требовалось доказать. |