Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
Лемма. Вершины графа без нечетных циклов можно раскрасить правильным образом в два цвета. Д ока за тел ьс т во. Достаточно доказатьлемму для связного графа. Выберем вершину A и припишем каждой вершине число, равное минимальной длине пути до нее из A. Тогда два одинаковых числа не стоят рядом (иначе естьнечетный цикл. Раскрасив все четные вершины в один цвета нечетные — в другой, получим требуемое. Таким образом, вершины графа G можно покраситьв два цвета (пусть это цвета a итак, что никакие две вершины одного цвета небыли соединены хорошим ребром. Поскольку через каждую вершину графа G проходит не более нечетных циклов, а в каждом из них мы отметили одно ребро, то из каждой вершины выходит не более N плохих ребер. Следовательно, мы можем раскраситьвершины графа G в N + 1 цвет так, чтобы никакие две из них небыли соединены в графе G плохим ребром. (Будем краситьвершины по очереди. Добавляя очередную вершину A, заметим, что среди покрашенных ранее она соединена плохими ребрами не более, чем с N вершинами, следовательно, мы можем покрасить вершину A в цвет, отличный от цветов ранее покрашенных вершин, соединенных с A плохими ребрами.) Итак, покрасим вершины графа G в цвета 1, 2, 3, . . . , (N +1) так, чтобы никакие две из них небыли соединены плохим ребром. После этого у всех вершин изменим оттенок на светлый, если впервой раскраске она была покрашена в цвет a, и на темный, если она была покрашена в цвет b. В полученной раскраске используется 2N + 2 цвета (с учетом оттенков) и никакие две вершины одного цвета не соединены ребром класс. Идея построения искомого примера видна из приведенного рисунка в случае a 1 = −7, a 2 = −6, . . . , a 10 = графики функций y = (x − − a 1 ) . . . (x − и y = (x + a 1 ) . . . (x + пересекаются ровно в точках x = 0, ±1, ±2. Ясно, что на промежутке [−2; 2] других корней нет. Вне этого отрезка получаем + 7)(x + 6) . . . (x + 3) = (x − 7)(x − 6) . . . (x − те ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ x y 0 Рис. 122 2 (7 + 6 + 5 + 4 + 3)x 4 + (7 · 6 · 5 + 7 · 6 · 4 + . . . + 5 · 4 · 3)x 2 + +7 · 6 · 5 · 4 · 3 = 0 — биквадратное уравнение, не имеющее корней. Ответ. Тремя. Впишем в цилиндр правильный треугольник с вершинами в серединах образующих и рассмотрим три единичных шара с центрами в серединах его сторон. Возьмем основание цилиндра. С ним наши шары пересекаются потрем кругам радиуса √ 3/2 с центрами в серединах сторон вписанного правильного треугольника. Легко проверить, что эти три круга целиком покрывают основание. Значит, цилиндр целиком покрыт тремя цилиндрами высоты 1, построенными на этих кругах, а, следовательно, и нашими шарами, содержащими эти цилиндры. Чтобы показать, что двумя шарами покрыть цилиндр не удастся, достаточно заметить, что если центр шара не совпадает с центром основания, то круг, по которому шар пересекается с плоскостью основания, пересекается с границей основания по дуге, меньшей 180 ◦ , а двумя такими дугами окружностьне покрыть. Если же центры двух шаров совпадают с центрами оснований, то непокрытой остается боковая поверхностьци- линдра. 227. Докажем индукцией по n, что при любом n сумма S n = a 1 + . . . представима в виде 2 b n (b n + 1) , где b n — целое. База индукции a 3 1 = a 2 1 ⇒ S 1 = a 1 = или 1, те или 2 · 1 · 2. УЧЕБНЫЙ ГОД, 11 КЛАСС 185 Индуктивный переход S 2 n+1 = (a 1 + . . . +a n +a n+1 ) 2 = (S n +a n+1 ) 2 = = S 2 n + 2S n a n+1 + a 2 n+1 , с другой стороны (a 1 + . . . + a n+1 ) 2 = a 3 1 +. . . . . . + a 3 n + a 3 n+1 = (a 1 + . . . + a n ) 2 + a 3 n+1 = S 2 n + a 3 n+1 . Отсюда 2S n a n+1 + + a 2 n+1 = a 3 n+1 , те. либо a n+1 = и тогда S n+1 = S n = 1 2 b n (b n + 1) , либо+ a n+1 = a 2 n+1 ⇒ b n (b n + 1) + a n+1 − a 2 n+1 = 0 , те+ или a n+1 = −b n . В этих случаях S n+1 = 1 2 b n (b n + 1) + b n + 1 = 1 2 (b n + + 1)(b n + или S n+1 = 1 2 b n (b n + 1) − b n = 1 2 (b n − Итак, при каждом n сумма S n — целая, что равносильно условию задачи. См. решение задачи 220. 229. Возведем доказываемое неравенство в квадрат, получим 1 + x 2 + 2 1 + x 2 · 1 + y 2 + 1 1 + y 2 4 1 + Сначала покажем, что 1 + x 2 + 1 1 + y 2 2 1 + Действительно, после приведения к общему знаменателю и раскрытия скобок имеем + x 2 + y 2 + x 2 y 2 ) − (1 + y 2 + xy + xy 3 ) − (1 + x 2 + xy + x 3 y) = = (1 − xy)(x − y) 2 Далее по неравенству о средних для двух чисел получим + x 2 · 1 + y 2 1 1 + x 2 + 1 1 + y 2 2 1 + Для завершения доказательства осталосьсложитьполученные неравен- ства. A B C E F B 1 B 2 O P K L M Рис. 123 230. Пусть L и M — точки, в которых вписанная окружностькасается сторон AB и BC см. рис. 123). Тогда и из равенства треугольников, OKB 2 , OLE, OMF следует = B 2 K = EL = F M , поэтому = BF , AE = AB 2 , CF = Пусть и соответственно точки, в которых отрезки и пересекают. Тогда по теореме Менелая: AE BE · BP 2 KP 2 × KB 2 AB 2 = и 1 , следовательно · AB 2 AE · и · CB 1 CF · KB 1 = BF KB 1 ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Отсюда BP 2 KP 2 = BP 1 KP 1 , те. Утверждение доказано. Ответ. При N Если k 3 — наибольшее черное число, то можно перекрасить тройку чисел (k − 2, k − 1, k) и далее действоватьаналогично до тех пор, пока все числа, кроме, бытьможет, 1 и 2, не станут белыми. Если число 2 после этого будет черным, то при N 8 перекрашиванием троек (2, 5, 8), (5, 6, 7) и (6, 7, 8) его можно сделатьбелым (цвет остальных чисел не изменится затем, если нужно, можно изменитьи цвет числа (перекрасив тройки (1, 4, 7), (4, 5, 6) и (5, 6, Случаи N = 1 и N = 2 очевидны, а для случаев 3 N 7 заметим, что четностьчисла черных чисел, принадлежащих множеству {2, 3, 5, при перекрашиваниях не изменяется. Поэтому, если первоначально число — черное, а остальные — белые, то все числа белыми сделатьнельзя. 232. Рассмотрим граф с вершинами в городах, ребра которого соответствуют дорогам. Из условия следует, что в этом графе через каждую вершину проходит не более N нечетных циклов. Докажем индукцией по количеству вершин, что вершины такого графа можно покраситьв N + 2 цвета так, чтобы никакие две вершины одного цвета небыли соединены ребром. База индукции для графа из одной вершины очевидна, докажем индуктивный переход. Пустьутверждение верно для графа, в котором менее k вершин. Рассмотрим граф G с k вершинами, в котором через каждую вершину проходит не более N нечетных циклов. Удалив из этого графа любую вершину A и все выходящие из нее ребра, мы получим граф с k − 1 вершиной. Очевидно, через каждую вершину графа проходит не более N циклов нечетной длины. Тогда покрасим вершины графа в N + 2 цвета таким образом, чтобы никакие две вершины одного цвета небыли соединены ребром (это можно сделать по индуктивному предположению). Для цвета k где 2 k (N + 2)) рассмотрим граф из всех вершин графа G , покрашенных в цвета 1 и k, и всех проведенных между ними ребер графа G. Поскольку никакие две вершины одинакового цвета в графе не соединены ребром, тов этом графе нет циклов нечетной длины. Построим граф G 1k , добавив к графу вершину A и все выходящие из нее к вершинам G 1k ребра. Если для некоторого k в графе через вершину A не проходит ни один цикл нечетной длины, то циклов нечетной длины в этом графе нет. В этом случае несложно доказать(см. лемму к задаче 224), что мы можем так перекраситьвершины графа используя лишь цвета 1 и k), что все ребра в этом графе будут соединятьпары вершин разных цветов. Так как все остальные вершины графа G покрашены в цвета, отличные от 1 и k, то УЧЕБНЫЙ ГОД, 8 КЛАСС 187 и во всем графе G никакие две вершины одинакового цвета не соединены ребром. Остается рассмотретьслучай, когда для каждого k где 2 k N в графе через вершину A проходит хотя бы один цикл нечетной длины. Заметим, что такой нечетный цикл проходит только по вершинам цветов и k, причем среди них естьхотя бы одна вершина цвета k. Следовательно, через вершину A проходит хотя бы N + 1 цикл нечетной длины, что противоречит условию. Следовательно, этот случай невозможен, и требуемая раскраска получена г класс. Ответ. Нельзя. Пустьчисло l получается из числа n изменением на k процентов (n, l — натуральные, k — целое. Тогда = n + n · k 100 = 100n + nk 100 = n(100 + Отсюда следует, что если n и 100 взаимно просты, то l делится на n. Поэтому если n = 7, то следующее число l должно делиться на 7, но больше среди чисел 1, 2, . . . , 10 таких нет. Значит 7 может быть только последним. Аналогично, 9 может бытьтолько последним. Нона последнем месте может бытьтолько одно число, поэтому требуемая расстановка невозможна. Противоречие. 1 1 1 2 1 2 2 1 1 2 2 2 Рис. 124 234. Ответ. Заметим, что изображения чисел 1111, 2112 и 2122 не могут иметьобщих единица изображения чисел 2222, 1221 и 1211 — общих двоек. Следовательно, если все эти числа встречаются среди изображенных, то по кругу должны располагаться не менее 14 цифр — 7 единиц и двоек. Равенство N = 14 возможно, и соответствующий пример расположения цифр показан на рис. 124. 235. Предположим противное. Рассмотрим пятиугольник удовлетворяющий условиям задачи. Не умаляя общности, можно считать, что угол A — наибольший, а угол D — наименьший (любую пару несмеж- ных вершин можно перевести в эту переобозначениями). Заметим, что ∠EAC = ∠A−∠BAC = ∠A−∠ACB > ∠C −∠BCA Предположим, что лучи AE и CD пересекаются в точке X. Тогда в треугольнике ACX сторона CX больше стороны AX, так как противнее ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ лежит больший угол. Тогда DX = CX − CD = CX − AE > AX − AE = = EX , поэтому 180 ◦ −∠E > 180 ◦ −∠D, что противоречит минимальности угла Рис. Случай, когда прямые AE и CD пересекаются с другой стороны от ED, аналогичен. В случае AE CD легко прийти к противоречию следующим образом. Заметим, что ACDE — ромб, ABC — равносторонний, и тогда ∠D < ∠E ⇒ ∠A = = 60 ◦ + D < ∠C = 60 ◦ + ∠E. 236. Ответ. При любых n и m победит первый игрок. Укажем выигрышную стратегию для первого игрока. Можно считать, что n. Если m = 2, то первый своим ходом красит всю большую сторону уголка, оставляя второму одну клетку, и выигрывает. Далее считаем m 3. В этом случае первый красит на большей стороне n − m + клетку, начиная с угловой, после чего остается две одинаковых полоски по m − 1 клетке. Далее первый игрок симметрично повторяет в другой полоске ходы второго, сделанные водной из полосок, до тех пор, пока после хода второго не останется единственного незакрашенного прямоугольника из более чем одной клетки. Затем, если число незакрашенных одноклеточных прямоугольников к этому моменту нечетно, то первый красит неодноклеточный прямоугольник целиком, а если четно, то оставляет в нем одну незакрашенную клетку. Таким образом, после его хода останется нечетное количество некрашенных прямоугольников, каждый из которых одноклеточный, поэтому последний ход вынужден будет сделатьвторой игрок, в результате чего и проиграет. Пусть x 0 = − f e . Тогда+ f | = e · − f e + f = |−f + f| = 0. Модульлюбого числа неотрицателен, поэтому = |ex 0 + f | = |ax 0 + b | + |cx 0 + d | Значит |ax 0 + b | = |cx 0 + d | = 0. Откуда ax 0 + b = и cx 0 + d = следовательно x 0 = − b a = − d c , поэтому b a = d c или ad = bc. 238. Ответ. Обязательно. Допустим, что нашлосьхорошее число n = c 1 . . . c k 8 , где c 1 , . . . , цифры, причем c k = 9. Тогда n + 1 = c 1 . . . c k 9 , n + 3 = c 1 . . . c k 1 , где c k + 1 УЧЕБНЫЙ ГОД, 9 КЛАСС 189 Числа n+1 и n+3 нечетны, а суммы их цифр равны c 1 + c 2 + . . . + c k + + и c 1 + c 2 + . . . + c k + соответственно. Эти суммы отличаются на, и потому одна из них четна. Но четное число не может бытьделителем нечетного. Противоречие. Ответ. Нельзя 1 2 4 1 3 3 4 1 2 4 Рис. Предположим, что существует раскраска таблицы, удовлетворяющая условию. Рассмотрим эту таблицу (см. рис. 126). По принципу Дирихле в каждом столбце найдется цвет, в который покрашены по крайней мере две клетки этого столбца. Назовем такой цвет преобладающим для данного столбца (возможно, у какого-то столбца будет два преобладающих цвета. Аналогично, какой то цвет (назовем его) будет преобладающим для двух столбцов. Поскольку от перестановки строки столбцов ничего не зависит, будем считать, что это столбцы a и b. Также можем считать, что в первом столбце цветом 1 покрашены клетки a4 и a5. Тогда клетки b4 и b5 должны бытьпокрашены какими-то двумя различными цветами, отличными от цвета 1. Пустьони покрашены цветами 2 и 3, а поскольку цвет 1 — преобладающий для столбца b, можем считать, что клетки b2 и b3 покрашены цветом 1. Рассмотрим клетку a3. Выбрав 3 и 4 строку и столбцы a и b, мы получим, что клетка a3 не может бытьпокрашенной цветами 1 и 3. Выбрав и 5 строку и столбцы a и b, мы получим, что клетка a3 не может бытьпокрашенной цветами 1 и 2. То естьклетка a3 покрашена цветом Но из аналогичных рассуждений мы получаем, что и клетка a2 покрашена цветом 4. То естьквадрат, состоящий из клеток a3, a2, b3 и b2, покрашен в два цвета — противоречие. A B C A 1 B 1 C 1 P Q M Рис. 127 240. Пусть AC — большая сторона средняя линия, параллельная AC, асе- редина A 1 C 1 . Так как ∠A и ∠C острые, то M проектируется внутрь отрезка AC, пусть B 1 — эта проекция (см. рис. Проведем 2 разреза и. Так как B 1 M — медиана и высота A 1 B 1 C 1 , то C 1 B 1 = A 1 B 1 . Пустьточка Q симметрична относительно, точка P симметрична относительно C 1 . Тогда BQA 1 = = CB 1 A 1 , AC 1 B 1 = BC 1 P . Равные отрезки и B 1 A 1 — половины сторон P B 1 Q , значит, он равнобедренный ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ класс. См. решение задачи 233. |