Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
Лемма. В полном множестве либо каждая строка, либо каждый столбец одноцветны. Д ока за тел ьс т во. Предположим, что в какой-то строке нашего множества нашлисьдве клетки разного цвета тогда найдутся и две клетки разного цвета на расстоянии n. Пустьэти клетки a и b, а клетки полного множества над ними — x и y см. рис. 150). Из сравнения цветов в квадратах, составленных из клеток множеств a ∪ S 1 ∪ D и x ∪ S 2 ∪ D видно, что наборы цветов в множествах a ∪ и x ∪ одинаковы аналогично, одинаковы наборы цветов в S 2 ∪ y и S 1 ∪ b. Тогда в множестве нет клеток цвета b, поэтому ив множестве нет такого цвета однако вон есть, поэтому цвета y и b совпадают аналогично совпадают цвета x и. Повторяя эти рассуждения, получаем, что столбец нашего множества, содержащий a, окрашен одинаково, и тоже со столбцом b. Теперь, если найдутся две клетки на расстоянии n в каком-то столбце, покрашенные по-разному, то строки множества, их содержащие, будут одноцветными. Но они будут пересекаться со столбцом цвета b, и поэтому их цвета будут совпадать, что невозможно. Полученное противоречие доказывает лемму. x S 2 y D a S 1 b Рис. Назовем полное множество вертикальным, если любой его столбец одноцветен, и горизонтальным в противном случае. Докажем, что все горизонтальные полные множества пересекаются с выделенной строкой. Пустьэто не так. Рассмотрим строку нашего множества, ближайшую к выделенной пустьона имеет цвет a. Тогда любую клетку выделенной строки можно заключитьв квадрат вместе с какой-то клеткой цвета a из нашего горизонтального множества поэтому в выделенной строке нет цвета a. Противоречие. Теперьлегко завершитьдоказательство требуемого. Заметим, что если естьстолбец, для которого все полные множества, его содержащие, вертикальны, тов этом столбце ровно n цветов, так как его раскраска пе УЧЕБНЫЙ ГОД, 11 КЛАСС 213 риодична с периодом n. Пустьлюбой столбец пересекается с горизонтальным полным множеством. Тогда выделенная строка пересекается с n горизонтальными множествами, строки которых одноцветны; поэтому в выделенной строке только n цветов. Противоречие, доказывающее тре- буемое. Замечание 1. Можно доказатьдаже, что в любом столбце содержится ровно n цветов. Замечание 2. Утверждение задачи (ноне предыдущего замечания!) остается верным, если в какой-то строке содержится хотя бы n 2 − n + + цвет. Пусть x 1 , . . . , x N — все различные корни уравнения P (x) = Нам необходимо доказать, что уравнение P (P (x)) имеет по крайней мере N различных корней. Рассмотрим N уравнений P (x) = x 1 , P (x) = x 2 , . . . , P (x) = Каждое из них имеет решение, так как P (x) — многочлен нечетной степени. Пусть a 1 — кореньпервого уравнения, a 2 — второго, . . . , a N — N-го. Тогда для любых i и j (i = j) числа и различны, так как P (a i ) = = x i = x j = P (a j ) . При этом каждое из чисел является корнем уравнения, так как P (P (a i )) = P (x i ) = 0 . То естьуравнение P (P (x)) = имеет по крайней мере N различных корней a 1 , . . . , a N 294. Ответ. Выигрывает первый. Покажем, что первому игроку достаточно каждым ходом проводить вектор с максимальной абсциссой, а из всех векторов, имеющих абсциссу, равную максимальной, вектор с максимальной ординатой. Действительно, докажем, что тогда сумма всех проведенных векторов будет иметьлибо положительную абсциссу, либо нулевую абсциссу и положительную ординату (назовем такой вектор положительным ). Очевидно, что каждым своим ходом первый игрок проводит положительный вектор, и сумма двух положительных векторов положительна. Также очевидно, что сумма векторов, проведенных заход первыми вторым, положительна или ноль. Поэтому достаточно доказать, что после первого хода второго игрока эта сумма будет положительна (те. не будет нулевой). Пустьона нулевая, первый провел вектора второй — −−→ CD . Если абсциссы точек A и D неравны, то один из векторов −→ AC и −−→ DB имеет абсциссу, большую, чему сумма этих абсцисс равна удвоенной абсциссе −→ AC ), что невозможно. Если абсциссы A и D совпадают, тоне совпадают ординаты (иначе A = D, B = C); тогда абсциссы векторов −→ AC , −−→ DB и −−→ AB равны, ноу какого-то из первых двух векторов ордината больше, чему третьего, что опять-таки невозможно ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Пусть P — точка пересечения продолжений сторон BC и AD случай разберем отдельно. Для определенности, пусть точка P лежит на продолжении BC заточку см. рис. 151). По условию BK и AK — биссектрисы углов P BA и P AB, поэтому точка их пересечения K является центром вписанной окружности треугольника ABP . Аналогично, точка M является центром вневписанной окружности треугольника CDP следовательно, K и M лежат на прямой m, являющейся биссектрисой угла Рис. 151 Пустьточки и O 2 — центры описанных окружностей треугольников и CDM. Центр K вневписанной окружности треугольника ABP лежит на биссектрисах углов P , A и B. Тогда углы и прямые, поэтому четырехугольник вписанный, и O 1 — середина, те. лежит на m. Аналогично, лежит на m и является серединой отрезка MK , где K — центр вневписанной окружности треугольника В случае AD BC легко видеть, что K и M, а также и лежат на прямой m, являющейся средней линией трапеции или параллелограмма ABCD .) Пустьокружности, описанные около треугольников ABK и касаются внешним образом. Их центры и лежат на m, поэтому УЧЕБНЫЙ ГОД, 11 КЛАСС 215 точка I касания лежит на m и совпадает си. Значит, I — точка пересечения биссектрис внутренних углов четырехугольника ABCD. Тогда описанный четырехугольники центр вписанной в него ок- ружности. Наоборот, если ABCD — описанный четырехугольники центр вписанной в него окружности, то AI⊥l A , BI⊥l B , и DI⊥l D . Поэтому точка I лежит на окружности, описанной вокруг треугольника, и диаметрально противоположна точке K, и также I лежит на окружности, описанной вокруг треугольника CDM, и диаметрально противоположна точке M. Таким образом, I лежит на m и является точкой внешнего касания окружностей, описанных около треугольников ABK и CDM Итак, внешнее касание окружностей, описанных около треугольников ABK и CDM, равносильно описанности четырехугольника ABCD. Но тоже самое справедливо и для пары окружностей, описанных около треугольников и DAN, откуда следует утверждение задачи. Ответ. Верно. Пусть M — целая точка на отрезке [0, N]. Приведем алгоритм, позволяющий ее отметить. Назовем исходные точки A 1 , A 2 , A 3 , A 4 , и будем считать, что мы на шаге алгоритма заменяем одну из точек на новую и новую называем также. При этом на каждом шаге алгоритма отрезки между отмеченными точками будут взаимно простыв совокупности и расстояние от M до заменяемой точки будет уменьшаться. Кроме того, каждая точка будет оставаться потуже сторону от M, что и изначально (или перемещаться в M). Ясно, что такую процедуру можно проделатьлишьконечное число раз, поэтому M в конце концов будет отмечена. Перенумеруем отмеченные точки в произвольном порядке B 1 , B 2 , B 3 , B 4 . Тогда наше условие взаимной простоты равносильно тому, что длины отрезков B 1 B 2 , B 2 B 3 , взаимно простыв совокупности. Поэтому, если расстояние от заменяемой точки до какой-то из оставшихся умень- шилосьв целое число раз, то взаимная простота сохранилась. Координаты двух из четырех отмеченных точек дают одинаковые остатки при делении на 3; пустьэто точки и A j . Возьмем точки C и D такие, что A i C = CD = DA j . Если точки C и D уже отмечены, то из взаимной простоты получаем A i C = CD = DA j = 1 , и точка M отмечена, ибо лежит на A i A j . Если точка C отмечена, а D нетто можно одну из точек или в зависимости от положения M) заменить на D; при этом взаимная простота сохранится, ибо расстояние от замененной точки до останется неизменным или разделится на 2. Если отмечена только D, шаг аналогичен ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Пустьни одна из точек C, D не отмечена. Если M и лежат по одну сторону от C симметричный случай аналогичен, то переместим в при этом длина уменьшилась в три раза, и взаимная простота сохранилась. Пусть, наконец, M лежит на CD. Если длина четна, то простые делители длины являются простыми делителями A i A j , поэтому при перемещении в D взаимная простота сохранится. Если же расстояние нечетно, то для любой третьей отмеченной точки одно из расстояний A i A m , нечетно. Пусть, для определенности, нечетно. Тогда можно заменить на D; у нового расстояния лишь один новый простой делитель — 2, но НОД расстояний не может делиться на 2, поскольку нечетно г класс. Ответ. Среди чисел от 1 дона делится только сама семерка. Значит, она должна входитьв первую группу, и частное не меньше 7. Приведем пример, когда оно равно 7: 3 · 5 · 6 · 7 · 8 1 · 2 · 4 · 9 · 10 . Он легко строится, если заметить, что 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 = 2 8 · 3 4 · 5 2 · те. надо добиться, чтобы произведение пяти чисел второй группы равнялось. Из условия следует, что проекции жуков на оси OX и OY движутся по осям с постоянными скоростями. Поскольку проекции жуков на ось OX никогда не совпадают, то это значит, что проекции жуков на ось OX движутся водном направлении с одинаковой скоростью. Так как прямые не параллельны, их угловые коэффициенты различны. Следовательно, если жуки пройдут пути, имеющие одинаковые проекции на их смещения по оси OY , с учетом знака, будут различными. Из этого следует, что проекции жуков на ось OY движутся с различными скоростями, а так как эти проекции находятся на одной прямой, то они обязательно когда-нибудьсовпадут (или совпадали раньше. Ответ. Выигрывает второй. Заметим, что если какой-то из игроков выпишет на доску число или 999 (назовем такой ход проигрышным, то его противник следующим ходом выпишет число 1000 и выиграет. Какие числа могут бытьвыписаны на доску до появления чисел 500 и 999? Во-первых, это все числа от до 499 (их 499). Во-вторых, это все числа от 502 до 998 (их 497), так как можно получитьиз числа 251. Заметим также, что число 501 может УЧЕБНЫЙ ГОД, 8 КЛАСС 217 получиться только из числа 500. То есть перед появлением числа 500 или будет сделано 499 + 497 = 996 непроигрышных ходов. Это означает, что проигрышный ход сделает первый игрок. В неравнобедренном треугольнике ABC проведем высоту из вершины наибольшего угла (BD на рис. 152). Пусть BC > BA, тогда DC > > DA . Прямоугольником, равновеликим треугольнику ABC будет прямоугольник, где DE = 1 2 AC , а точка E лежит на DC, так как > DA . Построим GF E, равный ADB (G ∈ BF ). Тогда BG = = BF −GF = DE −AD = (AD +EC)−AD = EC, и из параллельности прямых BG и CE ∠HBG = ∠HCE, ∠BGH = ∠HEC. Следовательно BGH = CEH. Получили три многоугольника ABD, BDEH, тупоугольный треугольник. Перекладывая ABD на место GEF и CEH на место BGH, получим прямоугольник. A B C D F E H G A B C D E F G Рис. Рис. Если ABC равнобедренный (AB = BC на рис. 153), то проводим высоту BD, отрезаем тупоугольный треугольники, перекладывая BDC на место AEB, получаем прямоугольник. Ответ. Три числа должны бытьнепременно: для этого достаточно рассмот- ретьтри ребра кубика, выходящие из вершины, в которой написано число (или 8). Докажем, что найдется расстановка чисел, для которой потребуется ровно три числа. Рассмотрим 2 квадрата. В вершинах первого расположим почасовой стрелке числа 1, 2, 3, 4, в вершинах второго, тоже почасовой стрелке, — числа 5, 6, 7, 8. Пока у нас задействовано два различных числа 1 и 3. А теперьрасположим первый квадрат под вторым 1 под, 2 поди т. д. Первое решение. Пусть + 1 cd + те. Тогда + 1 α 2 ab + 1 = 1 α , или αab + α = α 2 ab + 1 . Откуда (αab − − 1)(α − 1) = 0. То есть либо α = 1 (и тогда a = c и b = d), либо αab = 1. ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Но αab = (αa)b = cb = 1, те аналогично a = d = 1. В обоих случаях мы получили, что a = c и b = Второе решение. По свойствам пропорции если, то + C B + D = A − C B − если знаменатели не обращаются в ноль. Если = d , то все доказано. Пусть b = d, тогда + 1 cd + 1 ⇒ a c = = ab + 1 + a + b cd + 1 + c + d = (a + 1)(b + 1) (c + 1)(d + 1) , те+ Числа a и a + 1 взаимно просты, поэтому c(b + 1) ... a. Аналогично + 1 − a − b cd + 1 − c − d = (a − 1)(b − 1) (c − 1)(d − 1) , и из взаимной простоты a и a−1 следует, что c(b−1)...a. У чисел b+1 и b−1 общим множителем может бытьтолько число 2, поэтому либо c ... a, либо c ... a 2 . Записав равенства в виде + 1 ab + 1 , получаем, что либо a ... c, либо a ... c 2 . Это возможно только если = c , a = 2c или 2a = c. Если a = 2c, то b = 2d и + 1 cd + 1 = 4cd + 1 cd + 1 = Аналогично не подходит случай 2a = Рис. 154 303. Отложим на продолжении заточку отрезок CM = CD (см. рис. Тогда BD = BM в треугольнике BDM медиана совпадает с высотой). Имеем ∠BAK = = ∠AKD − ∠ABK = ∠ABC − − ∠ABK = ∠KBC = ∠CBM, так что ∠BAM = ∠BAK + ∠KAC = = ∠CBM +∠ABC = ∠ABM. Значит ABM — равнобедренный с основанием, те Значит, BK = BD − KD = BM − − KD = AM − KD = AM − AD = DM = 2DC, что и требовалось доказать. Занумеруем числа набора в порядке возрастания 0 < a 1 < a 2 < < . . . < a 2003 . Поскольку суммы a 2003 + a 1 , . . . , a 2003 + в набор входитьне могут, в него входят разности a 2003 − a 1 , . . . , a 2003 − a 2002 . Все эти 2002 разности различны и меньше, чем a 2003 . Поэтому a 2003 − a 1 = = a 2002 , a 2003 − a 2 = a 2001 , . . . , a 2003 − a 2002 = a 1 . Далее, поскольку+ a 2 > a 2002 + a 1 = a 2003 , в набор входит разность a 2002 − a 2 . По тем же причинам в набор входят разности a 2002 − a 3 , . . . , a 2002 − Всего таких разностей 2000, все они различны и меньше, чем ибо a 2003 − a 2 > a 2002 − a 2 ). Поэтому a 2002 − a 2 = a 2000 , . . . , a 2002 − − a 2001 = a 1 УЧЕБНЫЙ ГОД, 9 КЛАСС 219 Возьмем произвольное 2 k 2001. Тогда a 2003 − a k = и a k = a 2002−k , откуда a 2003−k − a 2002−k = a 2003 − a 2002 = Таким образом, a 1 = a 2003 − a 2002 = a 2002 − a 2001 = a 2001 − a 2000 = . . . = = a 2 − a 1 , что и требовалосьдоказать. 9 класс. Пусть a < b < c — длины сторон треугольника. Покажем, что найдется такое число x, что отрезки длин a + x, b + x, c + x — стороны прямоугольного треугольника. Положим P (x) = (x+a) 2 + (x + b) 2 −(x+ + c) 2 . Имеем P (c − a − b) = (c − b) 2 + (c − a) 2 − ((c − a) + (c − b)) 2 Значит, P (x) имеет корни. Достаточно доказать, что a + x 1 > 0 , где x 1 — больший корень P (x). Однако это сразу следует из того, что a + (c − − a − b) > 0. Тогда x 1 > c − a − b, значит a + x 1 > c − b > 0, поэтому треугольник существует. См. решение задачи Рис. 155 |