Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
344. Ответ+ Занумеруем окошки слева направо числами от 1 до n, а через обозначим номер окошка, в которое делается й по счету выстрел (i = 1, 2, 3, . . . ). ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Серия из+ выстрелов, определенная равенствами k[ n 2 ] +1 = и 2i − 1 для i ! n 2 " , гарантирует поражение мишени (легко проверить, что если вначале мишень находится в м окошке и m ! n 2 " , то результативным окажется й выстрел если же m > ! n 2 " , то мишеньбу- дет поражена последним выстрелом). Покажем, что никакая серия из меньшего числа выстрелов требуемым свойством не обладает. В самом деле, если произведено не более ! n 2 " выстрелов, то для m = = 1 , 2, . . . , ! n 2 " + условием поражения мишени, находившейся вначале в м окошке, является равенство k i = m + i − 1 хотя бы для одного из значений i. Но каждый выстрел может обеспечитьвыполнение только одного из требующихся равенств. Следовательно, найдется такое число+ 1 , что k i = m 0 + i − 1 для i = 1, 2, . . . , ! n 2 " ; это и означает, что для произвольной серии из ! n 2 " (и, тем более, из меньшего числа) выстрелов существует начальное положение мишени, при котором она останется непораженной. 10 класс. По условию a + b < π 2 , поэтому cos a > cos π 2 − b = sin b , так как cos убывает на отрезке. Аналогично, cos b > sin c и cos c > sin Сложив три полученных неравенства, получаем требуемое. См. решение задачи 338. 347. См. решение задачи 340. 348. Пусть A 1 , A 2 , . . . , A N — отмеченные точки, и каждое из расстояний) равно одному из n фиксированных чисел r 1 , r 2 , . . . , r n . Это означает, что для каждого i (1 i все отмеченные точки, кроме A i , лежат на одной из n окружностей, r 1 ), O(A i , r 2 ), . . . , O(A i , через O(X, r) мы обозначаем окруж- ностьрадиуса r с центром в точке Введем на плоскости систему координат так, что оси координат не параллельны прямым A i A j (1 i < j N). Рассмотрим отмеченную точку с наименьшей абсциссой, пусть это точка A 1 . Среди прямых A 1 A 2 , A 1 A 3 , . . . , найдем прямую (или одну из прямых) с наибольшим угловым коэффициентом, пусть это прямая A 1 A 2 . Точки, лежат водной полуплоскости α относительно прямой A 1 A 2 По условию каждая из точек A 3 , A 4 , . . . , является точкой пересечения окружностей O(A 1 , и O(A 2 , для некоторых k, l ∈ ∈ {1, 2, . . . , n}. Каждая из пар таких окружностей имеет не более одной точки пересечения, принадлежащей полуплоскости α. Следователь УЧЕБНЫЙ ГОД, 10 КЛАСС 235 но, среди N − 2 точек A 3 , A 4 , . . . , имеется не более различных. Отсюда, и N n 2 + 2 (n + 1) 2 349. Пусть и не взаимно просты. Тогда они имеют общий простой делитель p, те. Пусть x 1 , x 2 , . . . , x n — корни уравнения. Из тождества x n + a 1 x n−1 + a 2 x n−2 + . . . + a n−1 x + + a n = (x − x 1 )(x − x 2 ) . . . (x − получаем (приравнивая свободные члены и коэффициенты при x): x 1 x 2 . . . x n = ±a n = ±pk; x 1 x 2 . . . x n−1 + x 1 x 2 . . . x n−2 x n + +x 1 x 2 . . . x n−3 x n−1 x n + . . . + x 1 x 3 x 4 . . . x n−1 x n + +x 2 x 3 . . . Из первого равенства вытекает, что один из корней делится на p. Без ограничения общности делится на p. Тогда во втором равенстве все слагаемые левой части, кроме x 2 x 3 . . . x n−1 x n , делятся на p. Значит. также делится нате. хотя бы один из корней, x 3 , . . . , не взаимно прост с x 1 . Противоречие. Ответ. Набор с указанными свойствами не может состоятьиз одного числа. В самом деле для каждого N = abcde имеется различающееся с N во всех разрядах число G = ggggg, где g — цифра, отличная от нуля и от a, b, c, d, e. Покажем, что числа N 1 = и N 2 = = образуют набор, удовлетворяющий условиям задачи. Пусть = a 1 a 2 a 3 a 4 a 5 — произвольное число, для цифр которого выполнены неравенства 1 a 1 a 2 a 3 a 4 a 5 . Тогда, если A не совпадает в разряде единиц ни с N 1 , ни сто и, следовательно, a 4 7; если при этом нет совпадений ив разряде десятков, то a 4 5 и a 3 5. Если, кроме того, нет совпадений ив разряде сотен, то a 3 3, откуда a 2 предположив еще, что a 2 = 2 и a 2 = 3, придем к равенству a 1 = 1 , означающему совпадение A си св самом старшем разряде. Совершим гомотетию с центром в точке A и положительным коэффициентом, переводящую окружность в окружность ω 1 , равную Условимся образы точек и прямых при этой гомотетии обозначатьштри- хами. Пусть B 1 — вторая (отличная от A) точка пересечения и Окружности и симметричны относительно прямой AB 1 , причем при этой симметрии переходит в T 2 , переходит в t 2 , и переходит в. Таким образом, AM 2 = AM 1 = kAM 1 (k не зависит от положения точек и T 2 ). Тогда все треугольники AM 1 M 2 гомотетичны с центром A (так как точки и лежат на прямых и l 2 , проходящих через по разные стороны от прямой AB 1 , и отношение AM 2 : постоянно ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Отсюда следует, что середины отрезков лежат на фиксированной прямой, проходящей через точку Рис. 166 352. Рассмотрим два прямоугольника прямоугольники прямоугольнику которых совпадает левая нижняя клетка. Назовем часть прямоугольника (k + 1) × непокрытую прямоугольником) черной это полоска 1 × n), а частьпря- моугольника k × (n + 1), непокрытую прямоугольником (k + 1) × n белой это вертикальная полоска 1). Объединение этих частей назовем конструкцией. Если в каком-то положении конструкции на плоскости в белую часть попало больше отмеченных клеток, чем в черную, то мы нашли прямоугольник, в котором больше p отмеченных клеток. Пронумеруем клетки белой полоски сверху вниз. Рассмотрим любую отмеченную клетку и возьмем k конструкций такую, чтобы наша отмеченная клетка накрываласьпервой клеткой белой полоски, такую, чтобы отмеченная клетка накрываласьвторой клеткой белой полоски, и т. д. Черные полоски этих конструкций не перекрываются ив объединении дают прямоугольник k × n, те. в сумме накрывают не больше p отмеченных клеток. Каждая белая полоска накрывает хотя бы одну отмеченную клетку. Поскольку k > p, то среди этих конструкций естьтакая, у которой белая частьнакрывает больше отмеченных клеток, чем черная, что и требовалось класс. Пустьв алфавите жителей Банановой Республики n букв. Занумеруем их по порядку. Выпишем на доску слово, содержащее первую букву. Затем выпишем на доску слово, содержащее вторую букву. Затем — третью, и т. д. до тех пор, пока не выпишем на доску слово, содержащее ю букву. Таким образом мы выпишем на доску n слов, в записи которых используется ровно n различных букв. Сотрем с доски повторяющиеся слова (те. если какое-то слово написано m раз, то сотрем m − 1 такое слово. Вместо стертых слов выпишем на доску новые так, чтобы на доске оказалосьнаписано ровно n различных слов. Это можно сделать, поскольку слов больше n. При этом мы не используем новых букв, так как УЧЕБНЫЙ ГОД, 11 КЛАСС 237 букв всего n, и каждая из них где-то записана на доске. В записи этих слов используется ровно n различных букв, что и требовалось. Замечание. Приведенное решение показывает, что в утверждении задачи можно взять k = n — числу букв в алфавите. T 1 T 2 T 3 O 1 O 2 O 3 M S Рис. 167 354. Обозначим через O 1 , O 2 , O 3 , O центры окружностей ω 1 , ω 2 , ω 3 , ω соответственно. Из касания и ω следует, что точки O, O 1 , лежат на одной прямой, причем OO 1 = OT 1 − − O 1 T 1 = R − r. Аналогично, OO 2 = OO 3 = = R − r, поэтому O — центр окружности, описанной около треугольника O 1 O 2 O 3 . Поскольку, точка S также является центром окружности, описанной около треугольника O 1 O 2 O 3 . Отсюда следует, что точки S и O совпадают. Пусть M — середина отрезка T 1 T 2 . OM — медиана и высота равнобедренного треугольника OT 1 T 2 , следовательно M лежит на окружности, построенной на как на диаметре, те лежит на ω 1 . Аналогично, лежит на ω 2 355. В решении будем использовать следующие факты) Непрерывная функция (в частности, многочлен, принимающая на концах интервала значения разных знаков, обращается в нольв некоторой точке этого интервала) При достаточно больших положительных x значения многочлена по знаку совпадают сего старшим коэффициентом. При достаточно больших по модулю отрицательных x значения многочлена по знаку совпадают сего старшим коэффициентом, если степеньего четна, и противоположны ему, если степеньего нечетна. В частности, ввиду 1), многочлен нечетной степени всегда имеет корень. Приведем схему вычеркивания одночленов, дающую на каждом шаге многочлены, имеющие корни. Пустьмногочлен P (x) = ax n + bx m +. . . . . . + c (a, b = 0) содержит не менее трехчленов, и x m — две старших степени переменной x в P (x) (c = P (0) ⇒ c = 0). Если n или m нечетно, вычеркивая в P (x) одночлен или соответственно, получим многочлен нечетной степени, имеющий хотя бы один корень. Вычеркивая в дальнейшем другие одночлены, мы получим искомую последовательность многочленов. Поэтому далее рассматриваем случай, когда n и m четны. Умножая при необходимости на −1, можем считать a > 0. Если c < тов) можно вычеркнутьлюбой одночлен, отличный от старшего и свободного члена, полученный многочлен принимает отрицательное ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ значение c при x = 0 и положительное при достаточно большом x, значит, имеет корень. Далее считаем c > Пусть P (t) = 0. Если b > 0, вычеркнем в P (x) одночлен bx m . При больших положительных x значение полученного многочлена положительно, но P 1 (t) = P (t) − bt m < так как t = 0, а m — четно, следовательно имеет корни. Если же b < 0, вычеркнем одночлен тогда значения отрицательны при больших x, но P 1 (0) = P (0) = = c > 0 , значит, он тоже имеет корни. По приведенной схеме мы получим в конце многочлен, имеющий корни и содержащий ровно два одночлена, один из которых — P (0). Утверждение доказано. Ответ. Не сможет ни один из них. Построим ориентированный граф, вершины которого соответствуют городам, а ребра — дорогам, причем дорогам с односторонним движением мы поставим в соответствия ориентированные, а дорогам с двусторонним движением — неориентированные ребра. Докажем, что в любой момент игры любое еще неориентированное ребро можно ориентироватьтак, чтобы связностьграфа сохранилась. Из этого очевидно следует, что при правильной игре обоих игроков игра закончится вничью, и оба министра сохранят свои посты. Итак, пустьребро между вершинами u и v еще не ориентированно. Заметим, что если между этими вершинами существует путь(не умаляя общности можно считать, что он ведет от u к v), не проходящий поданному ребру, то ребро (u, v) можно ориентироватьв направлении от v к Тогда в любом пути, проходившем поданному ребру в противоположном направлении, мы можем заменитьэто ребро на указанный выше путьот к v, и связностьграфа не нарушится. Таким образом, нам достаточно рассмотретьситуацию, когда между вершинами u и v не существует путине проходящего через ребро (u, Рассмотрим множество U всех вершин, до которых можно добраться из вершины u, не проходя по ребру (u, v) (включая и саму вершину u). Поскольку граф связен, для любой вершины множества U должен существо- ватьпуть, ведущий от нее до вершины v. Однако, по нашему предположению, этот путьобязан проходитьпо ребру (u, v). Из этого следует, что из любой вершины множества U можно добраться до вершины u, не проходя по ребру (u, v). Но тогда из любой вершины множества U можно добраться до любой другой вершины этого множества, не проходя по ребру (u, Аналогичное множество для вершины v мы обозначим через V . Легко видеть, что из любой его вершины также можно добраться до любой другой его вершины, не проходя по ребру (u, v). УЧЕБНЫЙ ГОД, 11 КЛАСС 239 Поскольку граф связен, любая вершина должна принадлежать ровно одному из множеств U или V . Кроме того, поскольку исходный граф, в котором ребра небыли ориентированы, сохранял связностьпри удалении ребра (u, v), между множествами U и V должно существоватьеще хотя бы одно ребро, кроме ребра (u, v). Пустьэто ребро ведет из вершины u 1 ∈ в вершину v 1 ∈ V в данный момент игры это ребро может бытькак ориентированным, таки неориентированным, но как минимум водном из направлений, например, изв, по нему пройти в любом случае можно). Но тогда из вершины u мы можем добраться до вершины u 1 , из дои из доне проходя при этом по ребру (u, v), что противоречит сделанному ранее предположению. Полученное противоречие завершает решение задачи. См. решение задачи 341. 358. Ответ. Обозначим через x 1 , x 2 , x 3 , x 4 , количество пар последовательно идущих чисел, расстояние между которыми равно 1, 2, 3, 4, 5 соответственно. Так как последних цифр встречается всего 10, то они меняются как минимум 9 раз, следовательно, получаем неравенство Количество пар двух последних цифр — 100, аналогично имеем+ x 5 100 − 1 = итак далее получаем еще три соотношения+ x 4 + x 5 999, x 2 + x 3 + x 4 + x 5 9999, x 1 + x 2 + x 3 + x 4 + x 5 = в последнем равенстве и справа, и слева стоит количество всех 5-значных чисел, уменьшенное на 1. Сложив все эти неравенства, получим+ 2x 2 + 3x 3 + 4x 4 + 5x 5 Заметим, что слева в этом неравенстве у нас как раз получиласьсумма расстояний между последовательными числами. Теперьдокажем, что оценка точная. Для каждого числа n = = рассмотрим число n = оно может начинаться с нулей, ноне может оканчиваться нулем) и запишем числа в порядке возрастания. В соответствующем порядке запишем и исходные числа Заметим, что у чисел в таком порядке первая цифра (которая последняя у n) меняется 9 раз, первые две цифры — 99 разит. д, так как любые первые k цифр чисел тоже идут по порядку в данной последователь ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ ности. Таким образом, все выписанные выше неравенства обращаются в равенства. Ответ. Для любого треугольника T с углами α, β, γ обозначим f n (T ) = = sin nα + sin nβ + sin Лемма. Пусть x + y + z = πk, где k ∈ Z. Тогда sin x| | sin y| + | sin При y = πl, z = πl, где l ∈ Z, это неравенство — строгое. Д ока за тел ь ст во y| · | cos z| + | sin z| · | cos y| | sin y| + | sin При y = πl, z = πl, где l ∈ Z, последнее неравенство строгое. Из леммы следует, что знак функции f n (T определяется двумя синусами, имеющими одинаковые знаки если, например, sin nα > 0, sin nβ > > 0 , то f n (T ) sin nα + sin nβ − | sin nγ| > Очевидно, f 1 (T ) > 0 . Для любого (необязательно остроугольного) треугольника T справедливо и неравенство f 2 (T ) > 0 . В самом деле, если < π 2 , β < π 2 , то sin 2α > 0, sin 2β > Пусть n = 3. Рассмотрим равнобедренные остроугольные треугольники с углами α и β при основании при изменении x = α = β от π 4 до π 2 величина 3x меняется от 3π 4 до 3π 2 . Следовательно, sin 3x а вместе сними) принимает как положительные, таки отрицательные значения. Пусть n = 4, α β γ. Поскольку треугольник остроугольный, β если β π 4 , γ π 4 , то α π 2 ). Значит, π < 4β 4α < 4 · π 2 = откуда sin 4α < 0, sin 4β < 0. Вследствие леммы f 4 (T ) < Пусть n > 4. Рассуждая как в случае n = 3, получаем при изменении = α = β от π 4 до π 2 величина y = nx пробегает интервал, длина которого больше π. Следовательно, найдутся точки и такие, что sin nx 1 > 0 , sin nx 2 < 0 . Отсюда f n (T 1 ) > 0 , f n (T 2 ) < 0 , где и T 2 — треугольники, соответствующие и x 2 |