Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
582. Задача является частным случаем задачи 575, когда точки E и совпадают сточкой точка K в данной задаче — это точка F задачи. Вначале докажем, что УЧЕБНЫЙ ГОД, КЛАСС + y 2 x 2 + Допустим противное x + y 2 < x 2 + y 3 , тогда, складывая это неравенство с неравенством x 3 + y 4 x 2 + y 3 , получим (x+x 3 ) + (y 2 + y 4 ) < 2x 2 + что противоречит неравенствами Из (1) получаем + y 2 x 2 + y 3 x 3 + откуда + 2y 2 x 2 + y 3 + x 3 + Замечая, что (1 + x 2 ) + (1 + y 4 ) 2x + 2y 2 x 2 + y 3 + x 3 + y 4 , получаем неравенство 2 + x 2 + y 4 x 2 + y 3 + x 3 + y 4 , равносильное требуемому. Возьмем граф на 12 вершинах, которые соответствуют людям, две его вершины соединены, если люди незнакомы. Если в этом графе нет циклов нечетной длины, то его вершины можно разбитьна две части, в каждой из которых вершины не будут соединены (см., например, лемму к задаче 224 окружного тура, и поэтому найдутся попарно знакомых. Предположим теперь, что в графе есть циклы нечетной длины. Рассмотрим нечетный цикл минимальной длины. Пустьего длина равна: а) 3. Тогда, если среди 9 человек, не входящих в этот цикл, естьдва незнакомых, то среди оставшихся 7 человек из каждых 4 найдутся три знакомых. Таким образом, в подграфе на 7 вершинах каждые два ребра имеют общую вершину. Любое третье ребро обязано проходитьчерез эту вершину, иначе среди 4 человек не найдутся трех знакомых. Поэтому все ребра имеют общую вершину, и, удаляя эту вершину, мы получаем 6 попарно знакомых. б) 5. Тогда, как и выше, среди оставшихся 7 из каждых 4 найдутся знакомых, и среди этих 7 найдутся 6 знакомых. A B C D Рис. в) 7. Тогда среди 5 человек, не входящих в этот цикл, все попарно знакомы. Если естьчеловек из цикла, знакомый со всеми этими 5, то все доказано. В противном случае, каждый из цикла незнаком с кем- то из оставшихся. Так как 7 > 5, то найдется человек A из оставшихся, незнакомый с двумя из цикла B, Из того, что мы взяли нечетный цикл минимальной длины, следует, что эти два незнакомых из цикла должны быть незнакомы через одного D (см. рис. 272). Но тогда D знаком со всеми из пяти оставшихся, потому что удаляя из цикла D и заменяя на A, мы получаем снова цикл длины 7, а в дополнении к циклу длины 7 все попарно знакомы. г) Цикла длины 9 не может бытьпо условию задачи ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ д) Цикл длины 11. Тогда, как и выше при рассмотрении циклов длины, мы видим, что оставшийся человек может бытьне знаком максимум с двумя из цикла. Но тогда в цикле легко найти 5 человек, знакомых между собой и с оставшимся. (Например, взяв идущих через одного по циклу и знакомых с оставшимся класс. Ответ. Нет. Предположим, что такие 19 чисел существуют и сумма цифр каждого из чисел равна S = 9k + n, n ∈ {0, 1, . . . , 8}. Тогда все эти числа имеют остаток n при делении на 9, и имеет место сравнение 19n = 18n+n ≡ 1999 (mod 9) , откуда n ≡ 1 (mod 9), те n = 1. 1) Пусть k = 0, те S = 1. Рассмотрим 5 наименьших натуральных чисел с суммой цифр, равной 1. Это числа 1, 10, 100, 1000 и 10000. Но даже их сумма больше 1999. 2) Пусть k = 1, те. Рассмотрим 19 наименьших натуральных чисел чисел с суммой цифр, равной 10. Это числа 19, 28, 37, 46, 55, 64, 73, 82, 91, 109, 118, 127, 136, 145, 154, 163, 172, 181, 190. Их сумма равна < 1999 . Следующее натуральное число с суммой цифр, равной есть, что по крайней мерена больше любого из первых 19 чисел, и значит, сумма будет не менее 1990 + 18 = 2008 > 1999. 3) Пусть k 2, те. Но наименьшее число с суммой цифр не меньше 19 есть 199, а сумма любых 19 таких чисел будет заведомо больше 1999. Таким образом, мы получили, что 19 чисел, удовлетворяющих условию, не существует. Предположим противное, те. существует такая расстановка целых чисел, что для любого отрезка AB с серединой C выполняется неравенство, где a, b, c — соответственно числа, стоящие в точках, B и C. Пусть A, B, C, A n , B n , n = 1, 2, . . ., — соответственно точки, 1, 0, − 1 2 n , 1 числовой прямой, a, b, c, a n , b n — целые числа, записанные в этих точках. Тогда, по предположению, c < a + b 2 , a 1 < a + c 2 , a 2 < a 1 + c 2 , и т. д. Отсюда следует, что max{a, c} > a 1 , так как a 1 < < a + c 2 max{a, c} + max{a, c} 2 = max {a, c}. Аналогично, max{a 1 , c } > > a 2 , max{a 2 , c } > a 3 , . . . , и max{b, c} > b 1 , max{b 1 , c } > b 2 , . . . . Таким образом, если a m > c , то c < a m a m−1 − 1 . . . a − m, что при a − c невозможно поэтому при m max{1, a − c, b − c} получаем c, b m c, откуда a m + b m 2c, что противоречит нашему предположению УЧЕБНЫЙ ГОД, 11 КЛАСС 357 K L M N A B C D Q F E R Рис. 273 587. Введем обозначения (см. рис. 273). Как было показано в решении задачи 571, RQ KM EF , RE LN QF . Значит, образовавшийся четырехугольник — параллелограмм. Используя то, что касательные к окружности, проведенные из одной точки, равны и AB +CD = AD получаем RQ + EF = RE + QF , так как (RQ + EF ) − (RE + QF ) = = (a 12 + a 34 ) − (a 23 + a 41 ) , где a ij — длина общей внешней касательной к окружностями Значит, RQF E — ромб. См. решение задачи 580. 589. Набор натуральных чисел, удовлетворяющий условию задачи, условимся называть хорошим. Пустьсуществует хороший набор. Ясно, что если (a, b, c, d) — хороший набор, то и тоже хороший набор, где k = = НОД(a, b, c, d). Поэтому в дальнейшем считаем, что НОД(a, b, c, d) = 1. (1) Пустьодно изданных чисел, например a, имеет нечетный простой делитель. Тогда суммы b + c, c + d, b + d и, следовательно, сами числа b, c и d делятся на p ибо, например, 2d = (b+d)+(c+d)−(b+c)), что противоречит условию (1). Значит, числа a, b, c, d — степени двойки. Упорядочив данные числа в порядке возрастания, получим a = 2 m , b = 2 n , c = 2 r , d = 2 s , где 0 = m n r s, r 1 (иначе m = n = r = 0, значит = b = Тогда число (a + c) 2 = (1 + 2 r ) 2 — нечетно и не может делиться начетное число bd. Противоречие ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Пустькаждый из многоугольников A, B, C можно отделитьот двух других. Докажем, что их нельзя пересечь одной прямой. Предположим противное X, Y , Z — соответственно точки многоугольников A, B, лежащие на одной прямой. Тогда одна из точек, например Y , лежит на прямой между X и Z. Следовательно, B нельзя отделить от A итак как в противном случае точку Y , лежащую между двумя другими X и нужно отделитьот этих точек одной прямой, что невозможно. В обратную сторону утверждение можно доказатьдвумя способами. Пусть многоугольники нельзя пересечь одной прямой) Рассмотрим треугольники с вершинами X ∈ A, Y ∈ B, Z ∈ Пусть из всех таких треугольников наименьшую высоту из вершины имеет треугольник кстати, почему треугольник с наименьшей высотой существует. Тогда прямая, перпендикулярная высоте и проходящая через середину высоты, не пересекает многоугольники B, A итак как, в противном случае, существовал бы треугольник с меньшей высотой, выходящей из Y 0 2) Рассмотрим две внешние касательные к многоугольниками Тогда они не могут пересекать B. Если мы сдвинем немного ту, которая лежит ближе кв направлении к многоугольнику B, то получим прямую, отделяющую B от A и Рис. 274 591. Проведем плоскость, параллельную касательной плоскости, пересекающую ребра ив точках B 1 , и соответствен- но. В плоскости ABC получим конфигурацию, изображенную на рис. 274. Заметим, что = ∠CAM по теореме об угле между касательной и хордой, а ∠CAM = как накрест лежащие при параллельных и секущей, те. Следовательно AB 1 C 1 ∼ ACB. Откуда B 1 C 1 BC = AB 1 AC = AC 1 AB . Аналогично, C 1 D 1 CD = AC 1 AD = AD 1 AC и B 1 D 1 BD = AD 1 AB = AB 1 AD . Из этих равенств вытекает, что CD = AD 1 AB · AC = B 1 D 1 AC · BD = AB 1 AD · AC = B 1 C 1 AD · BC УЧЕБНЫЙ ГОД, 11 КЛАСС 359 Значит, равносторонний тогда и только тогда, когда AB · CD = = AC · BD = AD · BC. Осталосьзаметить, что углы, образуемые указанными в условии линиями пересечения, соответственно равны углам треугольника A 1 B 1 C 1 592. Ответ. Выигрывает Петя. Разобьем контакты на четыре одинаковых группы A, B, C и D. В каждой группе пронумеруем контакты числами от 1 до 500. Мысленно покрасим в черный цвет провода между контактами с разными номерами, ив белый цвет — между контактами с одинаковыми номерами. Петя будет отвечатьна любой ход Васи так, чтобы для каждого номера от контактов A k , B k , и отходило поровну черных проводов, и если у одного из контактов больше нет белых проводов, то их не было бы и у других контактов с таким же номером. До начала игры это условие, очевидно, выполняется. Именно благодаря этому условию проигрышная ситуация впервые случится после Васиного хода. Опишем подробно Петину стратегию. Сначала рассмотрим случай, когда Вася режет черный провод. Если Вася перерезает провод между контактами одной группы, например, провод A i A j , то Петя перережет провода B i B j , и D i D j . Если Вася перерезает провод между проводами из разных групп и с разными номерами, например, провод A i B j , то Петя в ответ перережет провода A j B i , и C j D i . Такие ходы Петя может сделать, так как из возможности отрезать один провод от некоторого контакта следует возможностьотрезатьпо одному проводу от вершин с таким же номером. Остается рассмотретьслучай, когда Вася перерезал белый провод, т. е, провод между контактами из разных групп, нос одинаковыми номерами. Рассмотрим четыре контакта A k , B k , и D k . Первоначально любые два из них соединены белым проводом. После того, как Вася перерезал первый из этих проводов, например, провод A k B k , Петя перережет два провода так, чтобы между этих контактов осталосьтри провода, имеющие один общий конец (например, Петя может перерезатьпровода и C k A k , после чего останутся провода A k D k , и C k D k , что подтверждает возможностьтакого хода. Если же Вася когда-нибудьперережет один из этих трех проводов, то от одного из контактов A k , или он отрежет последний провод к контактам с этим же номером k, следовательно, от этого контакта будет отходитьеще какой-то черный провод. Значит, и от трех других контактов с номером k будут отходитьчерные провода, следовательно, Петя может перерезать два оставшихся белых провода между контактами с номером k, что они сделает ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Отметим, что каждый раз после хода Пети описанное выше условие выполняется. Следовательно, Петя всегда сможет сделатьход, итак как количество проводов конечно, проиграет Вася г класс. Ответ. a + b + c = Если x 2 1 + ax 1 + 1 = и x 2 1 + bx 1 + c = 0 , то (a − b)x 1 + (1 − c) = 0 ⇒ ⇒ x 1 = c − 1 a − Аналогично, из равенств x 2 2 + x 2 + a = и x 2 2 + cx 2 + b = следует − b c − очевидно, c = 1), те. С другой стороны, по теореме Виета 1 x 1 — кореньпервого уравнения. Значит, x 2 — общий кореньуравнений x 2 + ax + 1 = и x 2 + x + a = = 0 , откуда (a − 1)(x 2 − 1) = 0. Но при a = 1 эти уравнения не имеют действительных корней. Значит, x 2 = 1 , тогда x 1 = 1 ⇒ a = −2, b + c = = −1. 594. Узнав наибольший общий делитель чисел X + 1 и 2, Саша определит четность X. Если X оказалосьчетным, то второй вопрос будет о наибольшем общем делителе X + 2 и 4, а если нечетным, то о наибольшем общем делителе X + 1 и 4. Таким образом, Саша узнает остаток отделения на 4. Вообще, пусть , задав k вопросов (k 5), Саша определил остаток отделения на 2 k . Тогда (k + м вопросом он узнает наибольший общий делитель X + 2 k − и заметим, что 0 < 2 k − − r k < 2 k+1 64 < 100). Если (X + 2 k − r k , 2 k+1 ) = 2 k+1 , то остаток отделения на равен 2 k + r k , а если (X + 2 k − r k , 2 k+1 ) = 2 k , то этот остаток равен Итак, задав 6 вопросов, Саша узнает остаток отделения на 64. Ясно, что чисел с таким остатком при делении на 64 в пределах первой сотни не более 2. Если их все же 2 — скажем, a и a+64, то Петя может задать вопрос Чему равен наибольший общий делитель X + 3 − r и 3? , где r — остаток отделения на 3. Ясно, что если X = a, то ответа если = a + 64 , то 1. Итак, седьмым вопросом число X определится одно- значно. Замечание. Можно заметить, что первые шесть вопросов Саша употребил на отыскание последних шести цифр двоичной записи числа X. 595. Пусть и N — точки пересечения серединных перпендикуляров кис прямыми AB и BC соответственно. Тогда ∠ABC = = ∠N AB = ∠M CB , поэтому точки A, M , C, лежат на одной ок- УЧЕБНЫЙ ГОД, 9 КЛАСС 361 ружности. Далее, ∠AM C = ∠ABC + ∠M CA = 2 ∠ABC = ∠AOC, так что O лежит на той же окружности, а тогда эта окружностьи есть, и = M , N = N . Теперь, поскольку дуга M этой окружности равна, то симметричная ей относительно MN окружность(с центром) описана около Рис. Тогда ∠LBN = π 2 − ∠BMN = = π 2 − ∠BCA, что и требовалось. Предположим, что существует граф, степени всех вершин которого более двух, но длина любого цикла в этом графе делится на 3. Рассмотрим такой граф G с наименьшим числом вершин. Очевидно, в этом графе существует цикл Z, пустьэтот цикл последовательно проходит по вершинам, A 2 , . . . , A 3k . Пустьсуществу- ет путь S, соединяющий вершины и и не проходящий по ребрам цикла Z. Рассмотрим циклы и Z 2 , состоящие из пути и двух половинок цикла Z. Поскольку длины обоих этих циклов делятся на 3, нетрудно заметить, что длина пути S делится на 3. В частности, из доказанного утверждения следует, что никакая вершина X, не входящая в цикл Z, не может бытьсо- единена ребрами с двумя разными вершинами цикла Z. Кроме того, ребра, выходящие из вершин цикла Z, отличные от ребер этого цикла, все раз- личны. Объединим все вершины A 1 , A 2 , . . . , цикла Z в одну вершину которую соединим ребрами со всеми вершинами, которые были соединены с вершинами цикла Z. Очевидно, в полученном графе меньше вершин, чем в графе G, и степенькаждой вершины по-прежнему более двух. Из доказанного выше следует, что длина любого цикла в графе делится на 3. Мы получили противоречие ведьв выбранном ранее графе G было минимальное количество вершин среди всех таких графов. Таким образом, в любом графе, степени всех вершин которого более двух, существует цикл, длина которого не делится на 3. Остается лишь применитьэто утверждение для графа, вершины которого соответствуют городам, а ребра — дорогам ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Докажем по индукции, что при n = 5m все числа от 1 до n выписаны на доску, a 5m = 5m − 2 и при всех k 5m выполняется равенство a k + 5 . База 1 → 4 → 2 → 5 → 3 → 6. Индуктивный шаг так как при n = 5m все числа от 1 до 5m уже выписаны и a 5m = 5m − 2, то следующие пятьчисел выглядят так a 5m+1 = 5m + 1 , a 5m+2 = 5m + 4 , a 5m+3 = 5m + 2 , a 5m+4 = 5m + 5 , a 5m+5 = 5m + 3 . Шаг индукции дока- зан. Таким образом, числа, дающие при делении на 5 остатки 4, 1 и 0, появляются на доске после увеличения предыдущего числа на 3. Но только такие остатки и могут даватьпри делении на 5 квадраты натуральных чисел. Заметим, что в конце никакие две разноцветные фишки не стоят нив одной строке, нив одном столбце. Действительно, если исходно черная фишка стояла водном столбце с белой, то ее сняли в первый раза если после первого снятия белая фишка стоит водной строке с черной, то ее сняли во второй раз. Пустьв конце черные фишки стоят в a строках и b столбцах, тогда белые могут стоятьне более, чем в 2n−a строках и 2n−b столбцах. Но тогда черных фишек не более ab, а белых не более (2n − a)(2n − b). Поскольку то либо черных, либо белых фишек осталосьне более Рис. 276 |