Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
Второе решение. Как ив первом решении, можно считать, что в нашем множестве найдутся точки A, B, C, не лежащие на одной прямой. Докажем, что tg ∠BAC — либо рациональное число, либо не существует. Рассмотрим координаты этих точек в системе, соответствующей тройке, B, C. Если x A = случай x A = аналогичен, то tg ∠BAC = = ± x C − x A y C − рационален (или не существует. Если же x B = и x C = = x A , то числа p = y B − y A x B − и q = y C − y A x C − рациональны. Но p = tg α, q = tg β , где α и β — углы, образуемые лучами AB и AC с положительным направлением оси Ox, поэтому из формулы tg ∠CAB = tg(β − α) = = p − q 1 + следует рациональность tg ∠BAC или тангенс не существует, если pq = −1). Аналогично, рациональными являются тангенсы углов всех треугольников с вершинами в данных точках. Рассмотрим систему координат с центром A и единичным вектором по оси Ax, равным −−→ AB Для любой точки D нашего множества tg ∠DAB и tg ∠DBA рациональны, поэтому уравнения прямых AD и BD имеют рациональные коэффициенты. Тогда и точка D имеет рациональные координаты. Изменив масштаб, мы получим целочисленные координаты у всех точек. Первое решение. Достаточно доказатьэто неравенство при 0 < < x при x оно очевидно, при x получается заменой = π 2 − x). При k 2 имеем cos k x − sin k x = (cos k x − sin k x)(sin 2 x + cos 2 x) = = (cos k+2 x − sin k+2 x) + sin 2 x cos 2 x(cos k−2 x − sin k−2 x) cos k+2 x − Поэтому неравенство сводится к случаю n = m + 1, за исключением n = = 3 . Кроме того sin n x cos n−1 x − sin n−1 x cos k x − sin k x cos k−1 x − при n k > 1. Действительно, приведя к общему знаменателю, получаем неравенство sin k−1 x cos k−1 x(cos n−k x − sin n−k x)(cos x − sin x) которое очевидно. Поэтому неравенство сводится к случаями. Докажем их sin 3 x = (cos x − sin x)(1 + sin x cos x) 3 2 (cos x − sin поскольку cos x sin x = 1 2 sin 2x 1 2 ; cos 2 x − sin 2 x = (cos x − sin x)(cos x + sin x) 3 2 (cos x − sin ибо sin x + cos x = √ 2 sin x + π 4 3 2 УЧЕБНЫЙ ГОД, 11 КЛАСС 391 Второе решение. Опятьже, неравенство достаточно доказатьдля 0 < x < π 4 . Рассмотрим f(y) = cos y x − sin y x , где 0 < x < π 4 , y Имеем f(0) = 0, f(y) > 0 при y > 0, f(y) → 0 при y → ∞. Далее) = cos y x ln cos x − sin y ln sin x = cos y x(ln cos x − tg y x ln sin поэтому имеет единственный кореньпри y > 0, так как функция) = монотонна. Из f(2) = f(2)(cos 2 x + sin 2 x) = f (4) следует, что f (2) > 0 , f (4) < 0 . Отсюда, при n > m 3 получаем неравенство sin n x − cos n x | | sin m x − Если же m 2, то из соотношений f(1) f(2) f(3) f(n) при > видно, что достаточно доказатьнеравенство 3f(1) 2f(3), которое следует из sin x cos x = sin 2x 2 1 2 , поскольку f(3) = f(1)(1 + + sin x cos x) 3 2 f (1) 660. Сначала докажем, что если с любой площади выходит не более двух улиц, то площади можно покраситьв 13 цветов так, чтобы ни с какой площади нельзя было попасть на площадьтого же цвета, проехав менее трех улиц. Для этого рассмотрим следующий вспомогательный ориентированный граф его вершинами будут площади, а ориентированными ребрами будут соединены пары площадей, между которыми в нашем городе есть путь, проходящий не более, чем по двум улицам. Легко видеть, что в этом графе из каждой вершины выходит не более 6 ребер. Нужно доказать, что вершины этого графа можно раскрасить в 13 цветов правильным образом. Это утверждение легко доказывается индукцией по числу вершин. Действительно, в случае, если вершин не больше 13, утверждение очевидно. Далее, легко видеть, что если в ориентированном графе из каждой вершины выходит не более 6 ребер, то существует вершина, в которую входит не более 6 ребер. Удалив из графа эту вершину, мы получим граф, удовлетворяющий нашему условию и содержащий меньшее число вершин. По индуктивному предположению, мы можем раскраситьвершины этого графа в 13 цветов, после чего удаленную вершину мы также можем покра- ситьв один из цветов, так как она соединена не более, чем с 12 вершинами. Теперьдля каждого цвета разделим все площади данного цвета на типов, в зависимости оттого, на площади каких цветов ведут улицы, выходящие сданной площади. Поскольку других цветов 12, для каждого цвета есть вариантов, в которых обе улицы ведут на площади одного цвета, и 12·11 2 = вариантов, в которых они ведут на площади разных цветов. Итого, 78 вариантов. Таким образом, мы можем разбитьвсе площади на 13 = 1014 районов ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Докажем, что полученное разбиение подходит. Пустьв районе A есть площади и a 2 , а в районе B — площади и такие, что из выходит улица, ведущая на b 1 , а из b 2 — на a 2 . Тогда, поскольку площади и принадлежат одному району, из них выходят улицы, ведущие на площади одних и тех же цветов. Это означает, что из выходит улица, ведущая на площадьтого же цвета, что и a 2 , а следовательно, того же цвета, что и a 1 . Таким образом, мы получили путь длины 2 между площадями одного цвета, что невозможно. Полученное противоречие завершает решение задачи. Ответ. 10010. Пустьдля натурального числа n имеют место указанные представления+ Воспользуемся тем, что каждое из чисел a 1 , . . . , дает такой же остаток при делении на 9, что и сумма цифр обозначим этот остаток через r (0 r 8), а соответствующий остаток для чисел b 1 , . . . , b 2003 — через s (0 s Тогда числа n − 2002r и n − 2003s кратны 9, а значит, и число (n − − 2002r) − (n − 2003s) = 2003s − 2002r = 2003(r + s) − 4005r кратно Число 4005r также кратно 9, а число 2003 — взаимно просто с 9; отсюда следует, что число r + s кратно Если при этом r = s = 0, то n 9 · 2003 (поскольку b 1 , . . . , делятся на 9). Если же r = 0, то r + s = 9, и потому имеет место по крайней мере одно из неравенств r 5 или s 5; для числа n получаются неравенства n 5 · 2002 или n 5 · 2003 соответственно. А так как 10010 = 5 · 2002 = 4 · 2002 + 2002 · 1, и числа 4 и 2002 имеют одинаковую сумму цифр, то число 10010 — искомое. Будем считать, что K лежит в AOD все остальные случаи разбираются аналогично). Пусть L — точка, симметричная L относительно BC см. рис. Тогда = ∠OBC − ∠L BC = ∠OBC − но ∠OBC = ∠OAD, так как ABCD — вписанный, следовательно = ∠OAD − ∠KAD = ∠OAK = так как ABOK — вписанный. Значит, ∠L BO = ∠OBK. Аналогично Далее, ∠BKO = ∠BAO = ∠CDO = ∠CKO, так как четырехугольники и CDKO — вписанные. Теперьрассмотрим четырехугольник см. рис. 300). Пусть точка пересечения CK и BL , M — точка пересечения BK и CL УЧЕБНЫЙ ГОД, 11 КЛАСС 393 A B C D K O L L B C K L O P M N Q R T Рис. Рис. Так как CO — биссектриса ∠MCK, BO — биссектриса ∠NBK, а KO — биссектриса ∠MKN, то O равноудалена от сторон четырехугольника L N и является центром вписанной в него окружности. Пусть P , Q, R , T — точки касания этой окружности со сторонами ML , L N , NK и KM соответственно. Тогда + BL = (CR + KR) + (BQ − L Q) = CP + KT + BT − L P = (KT + BT ) + (CP − L P ) = KB + Значит, CK + BL = KB + CL, и четырехугольник BLCK является описанным, что и требовалосьдоказать. 663. См. решение задачи 656. 664. Положим) = n i=1 где A(n) и B(n) взаимно просты. Заметим, что B(n) > n/2 (действительно, наибольшая степень двойки, не превосходящая n, является делителем ровно одного из чисел, 2, . . . , и потому является делителем знаменателя суммы Предположим, что при всех n число A(n) является степенью простого. Пусть p > n 0 + 5 — простое число. Тогда A(p−1)...p слагаемые суммы S(p − 1) разбиваются на пары, для каждой из которых числитель суммы делится на p). Следовательно, A(p − 1) = p k , k ∈ Далее, докажем, что числитель A(p n −1) также кратен p и, стало быть, является степенью p) при всех натуральных Проведем индукцию по База доказана ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Переход от n − 1 к n. Имеем S(p n − 1) = S(p n−1 − 1)/p + S , где первое слагаемое как раз равно сумме слагаемых со знаменателями, делящимися на p). Сумма разбивается на несколько (а именно, p n−1 ) сумм вида 1 pl+i , l = 0, 1, . . . , p n−1 − 1. Каждая из них имеет числитель, делящийся на p, что устанавливается как и для S(p − − 1). Осталосьубедиться, что числительдроби S(p n−1 − 1)/p делится на. Действительно, A(p n−1 − 1) = в силу индуктивного предположения, причем s > 1 (вспомним, что B(p n−1 − 1) p n−1 /2 p/2, а S(p n−1 − − 1) S(n 0 + 4) S(4) > Положим H p (n) := S(p n −p)−S(p n −1) = p−1 i=1 1 −p n + i . Если n > k, то числительдроби делится на p k , ноне на ибо H p (n) − S(p − 1) — дробь, числитель которой делится на p n ). Отсюда получаем, что оба числителя A(p n − 1) и A(p n − p) делятся на p, но один из них не делится на p k+1 . Значит, одна из дробей S(p n − 1) и S(p n − p) не превосходит при n = k + 2 — противоречие г класс. Возьмем три различных числа a, b, c ∈ M. Из рациональности чисел+ следует рациональность чисел+ b √ 2 − (b 2 + a √ 2) = (a − b)(a + b − √ 2) = 1 2 (a √ 2 − b √ 2)(a √ 2 + + b √ 2 − 2) и c 2 + a √ 2 − (c 2 + b √ 2) = a √ 2 − b √ 2 , те. числа a √ 2 + Значит, a √ 2 = 1 2 (a √ 2 + b √ 2 + a √ 2 − рационально. Заметим, что ∠LAK = ∠BAK + ∠BAL = 1/2(∠BO 2 A + + ∠BO 1 A) = ∠BO 2 O 1 + ∠BO 1 O 2 = 180 ◦ − ∠LBK, поэтому четырехугольник вписанный. Но тогда ∠BO 2 O 1 = ∠BAL = следовательно O 1 O 2 KL. 667. Достаточно доказатьследующее утверждение если любой белый отрезок пересекается хотя бы с k черными, то найдется черный, пересекающийся со всеми белыми. Предположим противное. Выберем для каждого черного отрезка белый, не пересекающийся с ним. Такой белый отрезок лежит либо левее соответствующего черного, либо правее его. Следовательно, есть хотя бы k черных отрезков, для каждого из которых его белый отрезок лежит по одну и туже сторону от него (пусть, для определенности, левее. Для УЧЕБНЫЙ ГОД, 9 КЛАСС 395 каждого из этих черных отрезков его левый конец лежит правее правого конца соответствующего ему белого отрезка. Тогда, если мы выберем из правых концов белых отрезков самый левый, то он будет лежатьлевее хотя былевых концов черных отрезков, те. этот белый отрезок не будет пересекаться ни с одним из этих k отрезков. Противоречие. Ответ. a 2003 = 10p Пустьв записи числа 1/n естьпредпериод A из m цифр и период B из k цифр. Тогда из формулы суммы геометрической прогрессии имеем 1) = A(10 k − 1) + B 10 m (10 k − Следовательно, 10 m (10 k − 1) ... n. Наоборот, пусть m, k — наименьшие числа такие, что 10 m (10 k − 1) ... n те естьмаксимальная из степеней двойки и пятерки, на которые делится n, а k — минимальное число такое, что (10 k − 1) ... n НОД(n, 10 m ) ) , и пусть C = 10 m (10 k − 1) n . Положим A = = C 10 k − 1 , B = C−A(10 k −1). Тогда B < 10 k −1, A < 10 m , и дробь имеет предпериод A с нулями, дополняющими его до m цифр) и период аналогично, ибо m и k были выбраны минимальными. Из условия наследует, что p = 2, p = 5 и p не может бытьчис- лом, в десятичной записи которого присутствуют только нули и единицы. Последнее следует из того, что сумма цифр такого числа должна равняться, и, значит, оно непростое. Мы докажем, что последовательность будет периодической с периодом 2. Период обыкновенной дроби равен (10 n − 1)/p, где n — наименьшее натуральное число, для которого 1) ... p. Таким образом, a 2 = 2(10 n − 1)/p. Докажем, что a 3 = = 10p . Поскольку делится на 2, ноне делится ни на 2 2 , ни на 5, период обыкновенной дроби будет равен (10 k+1 − 10)/a 2 , где k — наименьшее натуральное число, для которого (10 k+1 − 10) ... a 2 = 2(10 n − 1)/p в обозначениях первого абзаца A = 0, так как a 2 > 10 (a 2 ... 18), поэтому = C ). Следовательно, k является наименьшим натуральным числом, для которого 1)p ... 10 n − Покажем, что в этом случае k = n. Сначала установим, что n ... k. Предположим противное, тогда n = kq + r, где 0 < r < k. Заметим, что 1)p ... (10 k − 1)p ... (10 n − 1) и (10 n − 1) ... (10 n − А значит 1)p = ((10 n − 1)p − (10 kq − 1)p) ... (10 n − Стало быть, (10 r − 1)p ... (10 n − 1), что невозможно, ибо k было наименьшим числом, удовлетворяющим условию (∗). Поэтому, n = km и (10 k − ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ 1)p ... (10 mk − 1). Отсюда заключаем, что p ... (10 k(m−1) + 10 k(m−2) +. . . . . . + 10 k + 1) . Но p — простое число, следовательно, если m = 1, то = 10 k(m−1) + 10 k(m−2) + . . . + 10 k + 1 , что невозможно, ибо p не может бытьчислом из нулей и единиц. Итак, мы установили, что k = n, а значит (10 n+1 − 10)/a 2 = 10p . Для завершения решения осталосьлишь заметить, что периоды чисел 1/p и 1/(10p) равны. Переформулируем задачу на языке графов. Нам дан полный граф с N вершинами, ребра которого покрашены в два цвета. Требуется доказать, что мы можем выделить в этом графе цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Доказательство проведем по индукции. Для полного графа стремя вершинами утверждение очевидно. Пустьдоказываемое утверждение верно для N = = k . Рассмотрим полный граф с k + 1 вершиной. Удалим из рассмотрения одну вершину M с выходящими из нее ребрами. Для оставшегося графа с k вершинами по предположению индукции существует цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Возможны два случая) Все ребра цикла окрашены в один цвет. Занумеруем вершины цикла по порядку A 1 , A 2 , . . . , A k . Тогда, удалив ребро и соединив вершину M с вершинами и A 2 , мы получим цикл, состоящий не более чем из двух одноцветных частей) Не все ребра цикла окрашены в один цвет. Пустьизменение цвета происходит в вершинах и A m , те. в цикле есть две одноцветные части. первого цвета) и A m A m+1 . . . второго цвета. Тогда посмотрим на цвет ребра A m M . Если это ребро первого цвета, то цикл. . . A m M A m+1 . . . A 1 — искомый, если же оно второго цвета, то искомым будет цикл A 1 A 2 . . . A m−1 M A m . . . То естьв любом случае мы получили требуемый цикл с k+1 вершиной. Первое решение. Воспользуемся следующими неравенствами + b , которые следуют из очевидного неравенства + для положительных x, y. Сложив эти 3 неравенства, получим неравенство + b + 2 b + c + 2 c + a 4 a + 2b + c + 4 b + 2c + a + 4 c + 2a + которое после сокращения на 2 и замены в знаменателях дробей a + b + на 1 превратится в доказываемое неравенство. |