Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
Лемма 1. Полный ориентированный граф транзитивен тогда и только тогда, когда любой его подграф на трех вершинах транзи- тивен. Д ока за тел ьс т во. Очевидно, что если граф транзитивен, то таковы же все его подграфы. Докажем обратное. Индукция по N. База для N = 3 тривиальна. Пусть N > 3. Достаточно доказать, что существует вершина, из которой не ведет ни одного ребра. Тогда ее можно обозначитьцифрой N и применитьк оставшимся вершинам предположение индукции. Пустьтакой вершины нет. Тогда из любой вершины выходит ребро. Выйдем из любой вершины по ребру, выходящему из нее, из той вершины, в которую мы попадем — снова по выходящему ребру и т. д. Когда- нибудьмы попадем в вершину, в которой уже побывали. Следовательно, в графе нашелся ориентированный цикл (скажем, A 1 A 2 . . . A k A 1 ). Так как треугольники A k−1 A k A 1 , A k−2 A k−1 A 1 , . . . , A 3 A 4 A 1 транзитивны, последовательно получаем, что ребра A k−1 A 1 , A k−2 A 1 , . . . , направлены к A 1 . Но тогда треугольник A 1 A 2 A 3 нетранзитивен — противоречие. Лемма 2. Пусть исходный граф покрашен в два цвета. Изменим все направления красных стрелок на противоположные. Раскраска однотонна тогда и только тогда, когда полученный граф также транзитивен. Д ока за тел ьс т во. Пустьраскраска однотонна. Достаточно доказать, что в полученном графе любой подграф на трех вершинах транзи- тивен. Действительно, пусть вершины A < B < C образуют нетранзи- тивный треугольник. Тогда ребра идут либо A → B → C → A, либо C → B → A. Нов обоих случаях путь ABC одноцветен и имеет другой цвет, нежели ребро AC, что невозможно. Пусть, наоборот, полученный граф транзитивен. Если раскраска не была однотонной, то существуют одноцветные пути A → C 1 → · · · → → C k → B красный) и A → D 1 → · · · → D l → B синий. Тогда в транзитивном графе нашелся ориентированный цикл AD 1 . . . D l BC k . . . что невозможно. Теперьлегко получитьрешение задачи. Действительно, однотонных раскрасок столько же, сколько возможно транзитивных графов на N вер- УЧЕБНЫЙ ГОД, 10 КЛАСС 249 шинах; их, в свою очередь, столько же, сколько перенумераций N вершин, т. е. N! . 381. Ответ. Можно. Пусть d — разностьпрогрессии. Если для всех n число a n+31 ... 5, то. Если же при некотором n число a n+31 ...5, то a n ...5 и a n+62 ...5, значит 62d ...5. Нотогда d...5, поскольку 5 и 62 взаимно просты. Итак, в любом случае d ... 5. Отсюда a 2 n = a n · a n+31 − 31a n d .. . 5, и, поскольку простое число, a n ... Аналогично, пользуясь простотой числа 401, получаем, что a n ... Поскольку 5 и 401 взаимно просты, делится на 5 · 401 = 2005 при любом n. 382. См. решение задачи 374. 383. Ответ. (2, Первое решение. Пустьусловие выполнено, те. существует такая последовательность натуральных чисел c n , что a n + b n = c n+1 n . Ясно, что c n a + b, так как иначе c n+1 n > (a + b) n+1 (a + b) n = a n +. . . . . . + b n a n + b n . Значит, в последовательности хотя бы одно число {1, 2, . . . , a+b} повторяется бесконечно много раз, те. уравнение a n + + b n = с фиксированными a, b, c) имеет бесконечно много решений в натуральных n. Пустьдля определенности a b. Перепишем уравнение+ b n = в виде Если a > c, то 1 + d , где d > 0. Но тогда (1 + d) n = 1 + nd + . . . + d n 1 + nd, что больше при n > c/d, т. е. число решений уравнения конечно. Если a c, то 1 и 1, откуда c = 2 или c = 1. Первый случай возможен только при равенстве 1 , те. при a = b = = этот случай удовлетворяет условию задачи. Второй случай, очевидно, невозможен. Второе решение. Лемма 1. Если (z, t) = 1, тоне делится на Доказательство. Квадрат целого числа при делении надает остаток 0 или 1. Значит, если z 2 + t 2 ... 3, то z ... 3, t ... Лемма 2. Если (z, t) = 1, то (z + t, z 2 − zt + равен либо 1, либо Доказательство сразу следует из равенства z 2 − zt + t 2 = (z + + t) 2 − Решение задачи. Обозначим d = (a, b), x = a d , y = b d . Докажем вначале, что x = y = 1. Предположив противное, имеем x k + y k > x m + + при k > m; в частности, рассматривая числа D n = x 2·3 n + y 2·3 n , ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ имеем D n+1 > при любом натуральном n. Пусть p n — некоторый простой делитель большего 1 натурального числа. По лемме 1 p n = = 3. Отсюда по лемме 2 не делится на p n , ив разложение на простые множители любого числа D l , где l n + 1, число входит водной и той же степени (для доказательства второго утверждения нужно рассмотреть дробь D n+k+1 D n+k и убедиться, что она не делится на p n , так как D n+k ... Поэтому p n = при n = k. Очевидно, в последовательности попарно различных чисел p 1 , p 2 , . . . можно выбрать p = такое, что (p, d) = В разложение любого числа d 2·3 l · D l , где l n 0 + 1 , простой множитель p входит водной и той же степени. С другой стороны, из условия задачи следует, что эта степеньделится на 2 · 3 l + при любом натуральном n 0 + 1 . Противоречие. Получили a = b = d. Найдем d. Очевидно, d = 1; пустьпростое число p входит в разложение d на простые множители в степени α. Пусть p = = 2. Из условия задачи следует, что nα ... n + 1 при любом натуральном значит, (n + 1)α − α ... n + 1, α ... n + 1, что невозможно. Если p = 2, то + nα .. .n+1 при любом натуральном n, 1+(n+1)α−α...n+1, Отсюда α = 1. Получили d = 2. 384. Ответ. Не может. Первое решение. Допустим, это возможно для прямоугольника ABCD x y 0 B A C D A x B x C x D x A y B y C y D y t 1 s 1 t 3 t 2 s 2 t 4 Рис. Пусть AB — его наименьшая сторона. Выберем начало координат в узле сетки, и направим оси координат вдольлиний сетки так, чтобы среди вершин прямоугольника вершина имела наименьшую абсциссу, а вершина наименьшую ординату. Через, B x , C x , и A y , B y , C y , обозначим проекции вершин на оси (см. рис. 173). Абсциссы точек A x , B x , и ординаты точек A y , B y , C y , D y — нецелые, так как вершины A, B, не лежат на линиях сетки. Так как −−−→ D x C x = −−−→ A x B x и A x D x = AD · cos 45 ◦ AB · cos 45 ◦ = A x B x , то точки на оси Ox лежат в порядке A x , B x , D x , C x . (и могут совпасть. Также, точки на оси Oy лежат в порядке B y , A y , C y , D y . При этом D x C x = B y A y = C y D y = AB · cos 45 ◦ , B x D x = A y C y = (AD − − AB) cos 45 ◦ УЧЕБНЫЙ ГОД, 10 КЛАСС 251 Через t 1 , t 2 , t 3 , t 4 , s 1 , обозначим количество точек с целыми координатами соответственно на отрезках A x B x , B y A y , D x C x , C y D y , B x D x , A y C y . На отрезке ровно целочисленных точек, поэтому сторона пересекает ровно вертикальных линий сетки на отрезке A y D y t 4 + целочисленных точек, следовательно, сторона AD пересекает ровно+ горизонтальных линий сетки, и т. д. Таким образом, условие пересечения каждой стороной нечетного числа линий сетки эквивалентно нечетности чисел t 1 + t 2 , t 3 + t 4 , t 1 + t 4 + s 1 + s 2 , t 2 + t 3 + s 1 + Лемма. Если два отрезка равной длины d расположены на числовой прямой так, что их концы нецелочисленны, то количества целых точек на этих отрезках отличаются не более, чем на В самом деле, если на отрезке с левым концом в нецелой точке a и правым концом в нецелой точке b лежит k целых точек n, n + 1, . . . , n + + k − 1, то n − 1 < a < n и n + k − 1 < b < n + k, поэтому k − 1 < d = = b − a < k + 1 и d − 1 < k < d + 1, те или k = [d] + 1. Лемма доказана. Из леммы следует, что числа t 1 , t 2 , t 3 , отличаются не более, чем нате. равны t или t + 1, и также числа и равны s или s + 1. Так как+ нечетно, то t 1 = t 2 . Пустьдля определенности t 1 = t , t 2 = t + 1 1) Если t 3 = t , то t 4 = t + 1 , так как t 3 + нечетно. Тогда s 1 + s 2 = = (t 1 + t 4 + s 1 + s 2 ) − (t 1 + t 4 ) = (t 1 + t 4 + s 1 + s 2 ) − (2t + 1) — четно. Отсюда s 1 = s 2 . Но тогда (t 2 +s 2 +t 4 ) −(t 1 +s 1 +t 3 ) = 2 — противоречие утверждению леммы для отрезков и B y D y 2) Если же t 3 = t + 1 , то t 4 = t . Тогда s 1 + s 2 = (t 1 + t 4 + s 1 + s 2 ) − − (t 1 + t 4 ) — нечетно, те. либо s 1 = s , s 2 = s + 1 , либо s 1 = s + 1 , s 2 = Первый случай противоречит утверждению леммы для отрезков и, второй — для отрезков и Второе решение. Предположим, такой прямоугольник ABCD существует. Пусть AB √ 2 . Отложим на сторонах AB и CD отрезки CC = √ 2[AB/ √ 2] . Тогда отрезки и пересекают по одной вертикальной и горизонтальной линии, а отрезок получается из BC переносом на вектор −−→ BB с целыми координатами. Поэтому прямоугольник также удовлетворяет условию. Продолжая такие действия, получим в результате прямоугольник, все стороны которого меньше обозначим его опять ABCD). Тогда каждая сторона пересекает не более одной прямой каждого направления, те. ровно по одной прямой либо вертикальной, либо горизонтальной. Пусть A — самая левая точка прямоугольника, а B — самая нижняя, тогда C — самая правая, а D — самая верхняя. Если отрезки AB и пересекают вертикальные прямые, то ломаная CDA их также пересекает ОКРУЖНОЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ а горизонтальные прямые, соответственно, не пересекает. Тогда проекция ABCD на горизонтальную прямую имеет длину больше 1 (между A и две вертикальных прямых, а на вертикальную — меньше 1, что невоз- можно. Если отрезки AB и BC пересекают (одну и туже) горизонтальную прямую, то ABCD лежит в полосе между двумя соседними вертикалями, а тогда AD и DC также пересекают горизонтальную прямую, что невозможно по тем же причинам. Остался единственный (с точностью до симметрии) случай — AB и CD пересекают одну и туже вертикальную прямую v, аи одну и туже горизонтальную прямую h. Тогда A и B лежат пода над поэтому BC > AB. Аналогично, B и C лежат правее v, а D — левее поэтому BC < CD. Итого, AB < BC < CD, что невозможно класс. Ответ. Таких чисел нет. Действительно, если x 1, то sin(xy) sin y < sin x + sin y; аналогично, если y 1. Если же x, y > 1 > π 6 , тот. е x + sin y > 1 2 + 1 2 = 1 sin(xy). 386. Ответ. Если числа a, b, c, d удовлетворяют условиям утверждения в задаче, то числа 1 a , 1 b , 1 c , 1 d удовлетворяют этим условиям, а значит, для тех и других верно заключение этого утверждения, те и 1 a − 1 + 1 1 b − 1 + 1 1 c − 1 + 1 1 d − 1 = S . Сложив эти равенства, получим = 2S, ибо − 1 + 1 1 a − 1 = −1, откуда S = Замечание. Нетрудно убедиться, что верно следующее утверждение: если a + b + c + d = −2 и (a, b, c, d отличны от нуля и единицы, то − 1 + 1 b − 1 + 1 c − 1 + 1 d − 1 = −2. Но этого в задаче не требуется. Ответ. N! (N! = 1 · 2 · . . . · См. решение задачи 380. 388. Обозначим в треугольнике ABC за A 0 , B 0 — середины сторон и CA, заточку пересечения высот треугольника, за O — центр описанной окружности треугольника Точки A, B, A 1 , лежат на одной окружности (с диаметром AB), поэтому, следовательно, точки A 1 , B 1 , лежат на одной окружности ω 1 . Пусть ω 2 — окружностьс диаметром УЧЕБНЫЙ ГОД, КЛАССа окружностьс диаметром CO. Заметим, что точки A 1 , лежат на ω 2 , а точки A 0 , лежат на Рис. Точка имеет одинаковую сте- пеньотносительно и ω 2 , а также относительно и ω 3 , следовательно, относительно и ω 3 , те. лежит на их радикальной оси. Центры окружностей и ω 3 — середины CH и соответственно. Прямая перпендикулярна линии центров, а значит и HO Замечание. Степенью точки относительно окружности радиуса R с центром O называется величина. Радикальной осью двух окружностей называется геометрическое место точек, имеющих равные степени относительно этих окружностей. Радикальная ось всегда является прямой, а в случае двух пересекающихся окружностей — прямой, проходящей через точки их пересечения. Заметим, что числа P (r) и P (mk + r) дают одинаковые остатки при делении на k. Следовательно, в сумме P (1) + P (2) + . . . + P для каждого r = 0, 1, . . . , k − 1 будет k слагаемых вида P (mk + r), дающих одинаковые остатки при делении на k. Сумма этих k слагаемых делится на сумма всех слагаемых разбивается на k таких сумма потому тоже делится на k. 390. При указанном отражении сохраняются длины диагоналей четырехугольника. Пусть острый угол между диагоналями был равен α, тогда после отражения один из углов между диагоналями становится равным либо 3α, либо 3α−π, а поэтому отношение площадей равно α . Используя формулу для синуса тройного угла, получим − 4 sin 2 α | < < 3 |