Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
708. Ответ · 2002 2 + 1 = Докажем, что сумма не может бытьменьше. Переставив, если нужно, столбцы, будем далее считать, что числа впервой строке стоят в неубывающем порядке. Пусть a i — е число первой строки. Рассмотрим сумму = (a 1 − 1) + (a 2 − 1) + (a 3 − 1) + (a 4 − 2) + . . . + (a i − (i − 2)) + . . . . . . + (a 2003 − 2001) + (a 2004 − 2001). ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Заметим, что сумма вычитаемых чисел как раз равна · 2002 2 + 1 ; поэтому достаточно доказать, что S 0. Обозначим е слагаемое в нашей сумме через d i . Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что a 2004 2001, a 2 a 1 1, те Пусть d i < 0 , те. Тогда в i первых столбцах содержатся только числа от 1 до i, следовательно, там содержатся все такие числа. Отсюда следует, что a i = i − 3, a i+1 i + 1, и d i + d i+1 > 0 . Таким образом, для любого отрицательного сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых, что и требовалось. Осталосьпривести пример таблицы, для которой оценка достигается 1 1 2 3 4 · · · k · · · 1998 1999 2000 2001 2001 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2001 2002 2003 2004 1 2 3 4 5 6 · · · k + 2 · · · 2000 2002 2002 2003 2004 2 3 4 5 6 7 · · · k + 3 · · · 2001 2002 2003 2003 2004 2 3 4 5 6 7 · · · k + 3 · · · 2001 2002 2003 2004 два первых и четыре последних столбца устроены несколько иначе, чем остальные. Пусть A 1 1. Достаточно доказать, что A n+1 < при любом n Имеем A n A 1 A n . Перемножая и и раскрывая скобки, видим, что A 1 A n = A n+1 + S n , где S n — сумма всех слагаемых полученной суммы, в которых встречается квадрат одного из x i . Тогда S n > 0 , откуда следует требуемое. Предположим противное. Выберем прямую, неортогональную ни одному из векторов нашего множества. Тогда проекции хотя бы N векторов на нее направлены в одну сторону обозначим их e 1 , . . . , e N . Введем на этой прямой направление так, что эти векторы направлены в отрицательную сторону, и выберем N векторов f 1 , . . . , так, что алгебраическая проекция s их суммы максимальна (ясно, что из условия 2) s > 0). При этом, если некоторые из этих векторов совпали с векторами e i , то проекции всех векторов, кроме f 1 , . . . , f N , направлены в отрицательную сторону тогда мы обозначим через e i какие-то N векторов, отличных от f i , i = 1 , . . . , N. УЧЕБНЫЙ ГОД, 11 КЛАСС 419 Для N векторов найдутся векторы a 1 , . . . , a N такие, что f 1 +. . . . . . + f N = −(a 1 + . . . + a N −1 ) . Хотя бы один из векторов не совпадает ни с одним из a j (пустьэто e 1 ), при этом алгебраическая проекция суммы+ отрицательна и больше s по модулю. Тогда для векторов a 1 , . . . , a N −1 , существуют N векторов, сумма которых равна+ . . . + a N −1 + e 1 ) , те. алгебраическая проекция суммы которых больше s. Противоречие с выбором векторов f i 711. Индукция по k. Если k = 0, утверждение тривиально авиалиний нет. Рассмотрим граф, вершины которого соответствуют городам, а ребра авиалиниям. Пусть E 1 , E 2 , . . . , E k — группы ребер, соответствующие авиалиниям первой, второй, . . . , й авиакомпаний. Нетрудно понять, что для любого i ∈ {1, . . . , k} группа E i — либо треугольник, либо ёж — несколько ребер с одним концом. Если какая-то группа E i — ёж сцен- тром в вершине A, то удалим A и все выходящие из нее ребра. В оставшемся графе ребра принадлежат k − 1 авиакомпании, его вершины мы разобьем на k + 1 группу так, чтобы вершины из одной группы небыли соединены ребром, а вершина A составит (k + ю группу. Остается рассмотретьслучай, когда все группы E 1 , . . . , E k — треугольники. Тогда всего в графе 3k ребер. Разобьем вершины графа на минимальное возможное количество групп так, что никакие две вершины одной группы не смежны (те. не соединены ребром. Пустьэто группы, . . . , B n , причем n k + 3. Отметим, что для любых двух групп и существует ребро между вершиной из и вершиной из B j , иначе можно объединитьэти две группы в одну. Таким образом, всего в графе хотя бы − ребер. Отметим, что − 1) 2 (k + 3)(k + 2) 2 > 3k , — противоречие, завершающее решение задачи. Пусть ABCDA 1 B 1 C 1 D 1 — прямоугольный параллелепипед, в котором, причем a b c. Без ограничения общности можно считать, что шестиугольное сечение KLMNP Q расположено так, что K ∈ AD, L ∈ AB, M ∈ BB 1 , N ∈ B 1 C 1 , P ∈ C 1 D 1 , Q ∈ см. рис. В шестиугольнике пары противоположных сторон параллельны (как прямые пересечения плоскости с парой параллельных плоскостей. Расстояние между параллельными прямыми QK и MN не меньше, чем расстояние между гранями и BCC 1 B 1 , которое равно Аналогично, расстояние между парами параллельных сторон KL и P , LM и P Q не меньше длины одного из ребер параллелепипеда, и, следовательно, не меньше a. ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ a b c A B C D A 1 B 1 C 1 D 1 K P Q L M N Рис. Рис. Докажем, что проекция шестиугольника на любую прямую, лежащую в плоскости этого шестиугольника, не меньше, чем a. Поскольку противоположные стороны шестиугольника KLMNP параллельны, его проекция на некоторую прямую l будет совпадатьс проекцией одного из отрезков KN, LP , MQ. Пусть, для определенности, проекция на l совпадает с отрезком K N , где и N — проекции точек K и N соответственно. Можно предполагать, что K , N , P и Q лежат по одну сторону от KN этого можно добиться параллельным сдвигом l). Тогда один из углов K KN , N N K — не тупой, пусть, например, не тупой (см. рис. 312). Тогда K N = KN sin ∠K KN KN sin ∠QKN. Но sin ∠QKN — это расстояние между прямыми QK и MN, поэтому KN sin ∠QKN a. Пустьшестиугольник KLMNP Q помещен в прямоугольник Π со сторонами, равными d 1 , d 2 . Тогда каждая из сторон d 1 , не меньше, чем длина проекции KLMNP Q на прямые, параллельные сторонам Π. Отсюда по доказанному a, d 2 Заметим, что при проекции на плоскость отрезок LP переходит в отрезок см. рис. 311), поэтому LP AD 1 = √ b 2 + c 2 . С другой стороны, LP содержится в Π, поэтому длина LP не превосходит длины диагонали 1 + d 2 прямоугольника Π. Получаем, что 1 + d 2 2 b 2 + c 2 . (2) УЧЕБНЫЙ ГОД, 9 КЛАСС 421 Если бы каждая из сторон d 1 , была меньше b, то мы получили бы противоречие неравенству (2). Поэтому одна из сторон d 1 , не меньше, другая сторона не меньше a в силу (1). Следовательно, в Π можно по- меститьпрямоугольник со сторонами a, b, равный грани ABCD. 2004–2005 г класс A B C D Q P A Рис. 313 713. Построим биссектрису угла и рассмотрим точку A , симметричную относительно этой биссектрисы. Так как CP = то построенная биссектриса является серединным перпендикуляром к отрезку P Q. Значит, четырехугольник равнобо- кая трапеция или прямоугольник, следовательно, лежит на описанной окружности AP Q при любом положении точек P и удовлетворяющем условию. Ответ. Верно. Предположим, что Олег не сможет выбратьдве требуемые клетки. Заменим все числа на их остатки при делении на 4. Тогда в таблице стоит по чисел 0, 1, 2 и 3. Разобьем таблицу на 121 табличку 2 × 2. В каждой такой табличке может стоятьне более одного нуля и не более одной двойки. Но так как количество табличек равно количеству нулей и количеству двоек, тов каждой табличке стоит ровно один нольи ровно одна двойка. Заметим, что в каждой табличке два оставшихся числа оба должны быть либо единицами, либо тройками. Но тогда количество единиц четно, однако их 121 — противоречие. Преобразуем условие 1 a 1 − 1 > S ⇐⇒ a 2 1 > (a 1 + a 2 + a 3 )(a 1 − 1) ⇐⇒ ⇐⇒ a 1 + a 2 + a 3 > a 1 (a 2 + a 3 ) ⇐⇒ 1 a 2 + a 3 > a 1 a 1 + a 2 + Сложив это неравенство с двумя аналогичными, получаем+ a 2 + 1 a 2 + a 3 + 1 a 3 + a 1 > a 1 + a 2 + a 3 a 1 + a 2 + a 3 = что и требовалось ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Ответ. Может. Лемма. Пусть за x рублей Вася смог выложить в нужном порядке на стол некоторые N −1 карточку, где N 3 k . Тогда он сможет добавить к выложенным карточкам еще одну, потратив при этом еще не более k рублей, те. затратив всего не более x + k рублей. Д ока за тел ьс т во леммы проведем индукцией по числу k. База = очевидна. Пустьдля всех N лемма доказана. Первый рубль Вася потратит на то, чтобы правильно выложить на стол ю карточку и карточки A и B, уже лежащие на местах N 3 и 2N 3 . Тогда я карточка попадет в одну из трех частей, на которые другие две карточки разбивают уже выложенную на стол последовательность. Но карточки A и B разбивают лежащую на столе последовательность из N − 1 карточки на куски размером не более чем по 3 k−1 −1 карточек, а значит Васе осталосьопре- делитьместо карточки с номером N средине более чем 3 k−1 − 1 карточек, потратив не более чем k−1 рубль, а это можно сделать по предположению индукции. Таким образом, лемма доказана. Теперь, используя лемму, подсчитаем Васины затраты на выкладывание всех 365 карточек. На выкладывание первых трех карточек Вася потратит рубль. На добавление к ним карточек с номерами от 4 до 9 всего карточек) Вася потратит не более 2 рублей на каждую карточку. На карточки с 10 по 27 не более 3 рублей на каждую, с 28 по 81 не более рублей, с 82 по 243 не более 5 рублей и наконец на карточки с номерами от 244 доне более 6 рублей на каждую. Итого, Вася сможет выложить все карточки на стол в нужном порядке, потратив не более чем 1 + 6 · 2 + + 18 · 3 + 54 · 4 + 162 · 5 + 122 · 6 = 1845 < 2000 рублей. Таким образом, Вася сможет потратитьне более 2000 рублей. Первое решение. Утверждение верно, если все числа — рациональны. Пусть наше множество содержит иррациональное число a. Тогда каждое из остальных чисел имеет вид либо p − a, либо, где p — рационально. Покажем, что чисел вида p − a не больше двух. Пусть b 1 = p 1 − a, b 2 = p 2 − a, b 3 = p 3 − a, тогда b 1 + b 2 = (p 1 + p 2 ) − 2a — не рационально, значит, b 1 ·b 2 = p 1 p 2 −a(p 1 +p 2 )+a 2 , а также b 1 ·b 3 , b 2 ·b 3 — рациональны. Отсюда A 3 = a 2 −a(p 1 + p 2 ) , A 2 = a 2 −a(p 1 + p 3 ) , A 1 = a 2 −a(p 2 + рациональны, значит, A 3 −A 2 = a(p 3 −p 2 ) — рационально, что возможно только прите противоречие. Значит, чисел второго вида больше двух, пусть c 1 = q 1 a , c 2 = q 2 a , c 3 = = q 3 a — такие числа. Сумма c 1 + c 2 = q 1 + может бытьрациональной только при q 2 = −q 1 . Но q 3 = q 2 , значит, сумма c 1 + c 3 = q 1 + q 3 a — УЧЕБНЫЙ ГОД, 9 КЛАСС 423 иррациональна. Тогда число c 1 · c 3 = q 1 q 3 a 2 — рационально, откуда a 2 — рационально. Второе решение. Рассмотрим произвольные 6 чисел из нашего набора. Поставим этим 6 числам в соответствие граф следующим образом у него шестьвершин, соответствующих нашим шести числам вершины соединены синим ребром, если сумма соответствующих чисел рациональна, и соединены красным ребром, если произведение соответствующих чисел рационально. Хорошо известно, что в таком графе найдется одноцветный треугольник. Рассмотрим каждый из этих случаев. Нашелся синий треугольник, те. нашлись три числа x, y, z такие, что x + y, x + z, y + z рациональны. Но тогда, например, (x + y) + (x + + z) − (y + z) = 2x рационально. То есть числа x, y, z рациональны. Тогда рассмотрим любое из оставшихся чисел t. Из рациональности любого из чисел xt и x + t следует рациональность числа t все числа по условию отличны от нуля. То естьвсе числа набора рациональны. Нашелся красный треугольник. То естьнашлисьтри числа x, y, такие, что xy, xz, yz рациональны. Но тогда, например, число рационально. То есть числа x 2 , y 2 , рациональны. Если хотя бы одно из чисел x, y, z рационально, то аналогично предыдущему случаю получаем рациональность всех чисел набора. Пусть теперь x = m √ a , где a рационально, m = ±1. Так как xy = m√ay = b — рационально, то = b m √ a = b √ a ma = c √ a , где c = m — рационально. Тогда рассмотрим любое из оставшихся чисел t. Если xt или yt — рационально, то аналогично предыдущему t = d √ a , где d — рационально, те рационально. Если же x + t и y + t — рациональны, то (y + t) − (x + t) = (m − c) √ a — рационально. Но (x + t) − (y + t) = (m − c) √ a — иррационально. Противоречие. То естьмы получили, что либо все числа набора рациональны, либо квадраты всех чисел набора рациональны, что и требовалось. Замечание. Утверждение задачи верно при любом n 5. 718. Ответ. Если x 1 x 2 — корни уравнения, то x 1 , x 2 ∈ N и x 1 + x 2 = S(A) , x 1 x 2 = S(B) , поэтому (x 1 + 1)(x 2 + 1) = S(B) + S(A) + 1 = 1 + 2 + 4 +. . . . . . + 2 2005 + 1 = 2 2006 . Значит, x 1 + 1 = 2 k , x 2 + 1 = 2 2006−k , где k может приниматьзначения 1, 2, . . . , Наоборот, пусть x 1 , x 2 — числа такого вида, тогда они являются корнями уравнения x 2 −px+q = 0, где p = 2 k + 2 2006−k −2, q = 2 Но число p имеет единственное разложение в сумму различных степеней двойки (двоичное разложение, ив этом разложении степени двойки не ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ превосходят 2 2005 , а двоичное разложение q содержит 1 на тех местах, где у числа p — нули, так как p + q = 2 2005 − 1. Итак, для каждого k такого, что 1 k 1003, существует единственное разбиение (A, B), дающее указанные корни и Рис. 314 |