Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
556. Предположим противное. Тогда найдется такое n (n > 1), что любой набор из n − 1 выделенного подмножества имеет общий элемент и существует выделенных подмножеств A 1 , A 2 , . . . , A n , не имеющих общего элемента. Исключим из набора A 1 , A 2 , . . . , множество A i . Оставшиеся имеют общий элемент, который мы обозначим через x i . Заметим, что при i = j. Каждое из множеств содержит все элементы множества, кроме x i , поэтому, если из множеств исключить элементы множества {x 1 , x 2 , . . . , x n }, тов каждом из них останется 2k − − n + 1 элемент (в частности, n 2k + 1). Следовательно, объединение множеств A 1 , A 2 , . . . , состоит не более чем из n + n(2k − n + 1) = = n(2k + 2 − n) элементов. Максимальное значение выражения n(2k + + 2 −n) равно (k+1) 2 . Но тогда, по условию задачи, все должны иметь общий элемент. Противоречие. Ответ. Нельзя. Допустим, что можно, и рассмотрим способ добиться этого за наименьшее количество действий. Пусть a k , b k — числа, получавшиеся из и 98 после го действия, s — число действий. Тогда a s = b s = итак как мы рассматриваем оптимальный способ. Действия, проведенные над и b s−1 , различны. Значит, m = и нам шаге мы имели числа a s−1 = и b s−1 = n 2 − 1 (или наоборот на дальнейшее решение это не влияет. Общее количество s действий не больше, чем n − 18, так как на s − 1 шаге мы получили n, а каждый шаг увеличивает числа по крайней мерена. Тогда n 2 − 1 могло получиться только последовательным прибавлением единиц, так как от ближайшего квадрата добудет единицы. Следовательно, b 1 > (n − поэтому все числа b 1 , . . . , не являются полными квадратами. Поэтому, с другой стороны a s = a 2 s−1 19 2 . Противоречие ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Переписав выражение ((x ∗ y) ∗ z) ∗ t двумя способами, получим равенство (x + y + z) ∗ t = (x ∗ y) + z + t. Подставив в него x = y = имеем z ∗ t = z + t + C, где C = 0 ∗ 0. Тогда (x ∗ y) ∗ z = (x + y + C) + + z + C = x + y + z , откуда C = 0. 559. Будем говорить, что три вершины угольника (n > 3), через которые проходит описанная окружность, образуют отмеченный треугольник. Докажем, что все отмеченные треугольники образуют триангуляцию многоугольника, те. разбиение многоугольника непересекающими- ся диагоналями на треугольники. Это следует из следующих свойств 1) и) отмеченных треугольников) Никакие два отмеченных треугольника не имеют общей внутренней точки. Действительно, если и A 2 B 2 C 2 — различные отмеченные треугольники, аи сооответствующие описанные окружности, то точки A 1 , B 1 , расположены на дуге окружности S 1 , лежащей внутри, а точки A 2 ,B 2 , C 2 — на дуге окружности S 2 , лежащей внутри S 1 (см. рис. 260) и утверждение очевидно. Рассуждения не меняются, если одна или две вершины наших треугольников совпадают. A 1 B 1 C 1 A 2 B 2 C 2 S 2 S 1 Рис. 260 2) Если ABC — отмеченный треугольники диагональ угольника, ток стороне примыкает еще один отмеченный треугольник. В самом деле, рассмотрим вершины n-угольника, лежащие сточкой по разные стороны от Среди этих вершин выберем такую вершину что угол ADB наименьший (из условия, что никакие четыре вершины не лежат на одной окружности, следует единственностьтакой вершины). Легко понять, что окружность, проходящая через точки A, B и D, будет описанной для угольника, соответственно треугольник ABD отмечен- ный. Далее будем называтьотмеченный треугольник граничным соответственно внутренним, если соответствующая описанная окружность граничная (внутренняя. Пусть Γ — число граничных треугольников, B — число внутренних, Π — число оставшихся отмеченных треугольников (назовем их простыми. Каждая из n сторон угольника принадлежит одному из треугольников, причем граничным треугольникам принадлежат по две стороны, простым — по одной, а внутренним — ни одной. Отсюда получим соотношение + Π = Так как любая триангуляция состоит из n − 2 треугольников, то + Π + B = n − 2. (2) УЧЕБНЫЙ ГОД, 10 КЛАСС 341 Вычитая (2) из (1), получаем Γ − B = 2, что и требовалось. Ответ. Удачная расстановка единственна — все числа равны +Первое решение. Докажем индукцией последующее утверждение: если в таблице из 2 n −1 столбцов и k строк (k+1 не делится на 3) расставлены числа ±1 так, что выполняется условие задачи, то все числа таблицы равны +1. При n = 1 имеем один столбец высоты k. Пустьв нем стоят числа a 1 , a 2 , . . . , a n — по порядку сверху вниз. Тогда a 1 = условие задачи для первой клетки, a 2 = a 1 a 3 , следовательно a 3 = 1 , 1 = a 3 = следовательно a 4 = a 2 = a 1 . Итак далее. Получаем, что все числа, стоящие в клетках с номером, кратным трем, равны 1, а все остальные равны. Поскольку k + 1 не делится на 3, то возможны две ситуации) a k−1 = a 1 , a k = 1 ; 2) a k−1 = 1 , a k = Но равен произведению своих соседей, те. Следовательно, и столбец состоит из одних единичек. Для доказательства индуктивного перехода введем следующие обозначения. Если A, B — две таблицы одинакового размера, то пусть A · B — таблица, в каждой клетке которой записано произведение чисел из тех же клеток таблиц A и. A будет обозначатьтаблицу, полученную из A зеркальной симметрией: первый столбец меняется с последним, второй — с предпоследними так далее. Нетрудно видеть, что если таблицы A и B удовлетворяют условию, то это же можно сказатьо таблицах A · B и A. Таблицу, в которой стоят только единицы, будем обозначать Докажем, что если в таблице размера k × (2 n+1 − 1) расставлены числа согласно условию, то расстановка симметрична A = A. Это равносильно тому, что A · A = 1. В таблице A · A весьцентральный столбец (с номером 2 n ) состоит из единиц, так как центральные столбцы у A и одинаковы. Следовательно, если мы рассмотрим отдельно часть таблицы слева от центрального столбца, то числа в этой меньшей таблице расставлены согласно условию. Размер ее — k × (2 n − 1), так что по предположению индукции, все числа в ней — единицы. Тоже касается и правой части A·A. Итак, A·A = 1. Это значит, что для любого числа из центрального столбца таблицы A числа слева и справа от него одинаковы, поэтому само оно равно произведению своих верхнего и нижнего соседей. Как мы доказали в базе индукции, из этого следует, что центральный столбец заполнен единицами. Теперьснова рассмотрим частьтаблицы A слева от центрального столбца. Применяя предположение индукции, убеждаемся, что в ней стоят только единицы. Правая часть симметрична левой, поэтому иона состоит из единиц. Переход индукции доказан. Для всех таблиц размера k × (2 n − 1) (где k + 1 не делится на 3) единственностьрасста- ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ новки доказана. Если k = 2 n − 1, то k + 1 = 2 n , поэтому доказано и утверждение задачи 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Рис. Второе решение. Пусть R — удачная расстановка в таблице 1) × (2 n − 1). Расставим числа на клетчатой плоскости, как показано на рис. 261 (симметрия буквы R означает, что там стоит таблица отраженная соответствующим образом. Тогда расстановка на всей плоскости удовлетворяет нашим условиям (те. любое число естьпроизведе- ние его четырех соседей) и, кроме того, она периодична, те. при сдвиге на вверх или вправо она переходит в себя. Докажем индукцией по n, что любая периодичная перестановка состоит из единиц. a 13 a 22 a 23 a 24 a 31 a 32 a 33 a 34 a 35 a 42 a 43 a 44 a 53 Рис. База при n = 0 очевидна a = a 4 , где a — число в клет- ке. Пусть n Рассмотрим фрагмент таблицы, показанный на рис. 262. Имеем a 23 = a 13 a 22 a 24 a 33 , a 32 = a 22 a 31 a 33 a 42 , a 34 = = a 24 a 33 a 35 a 44 , a 43 = a 33 a 42 a 44 a 53 , откуда a 33 = a 23 a 32 a 34 a 43 = = a 13 a 31 a 35 a 53 a 2 22 a 2 24 a 2 42 a 2 44 a 4 33 = a 13 a 31 a 35 a 53 , те. тоже соотношение верно для разреженной таблицы, состоящей из чисел, находящихся в пересечениях нечетных строк с нечетными столбцами. Эта таблица 2 n−1 - периодична, поэтому по предположению индукции она состоит из единиц УЧЕБНЫЙ ГОД, 11 КЛАСС 343 Абсолютно аналогично, остальные три разреженных подтаблицы состоят из единиц, что и требовалось класс. См. решение задачи Рис. 263 562. Первое решение. Случай правильного очевиден. Пусть AB = AC см. рис. 263). Обозначим через O, I центры описанной и вписанной окружностей. Тогда IA 1 ⊥ BC; OA 2 ⊥ BC так как O и лежат на серединном перпендикуляре к Следовательно, OA 2 и OA 2 IA 1 — трапеция. Точка P пересечения диагоналей этой трапеции делит OI в отношении : P I = OA 2 : IA 1 = R : r , где, r — радиусы соответственно описанной и вписанной окружностей. Проведя аналогичные рассуждения для трапеций OB 2 IB 1 , если ABC — равнобедренный, то одна из них вырождается в отрезок) получаем, что отрезки A 1 A 2 , B 1 B 2 , делят OI в отношении R : r и проходят через одну точку P Второе решение. Касательная в точке к описанной окружности параллельна BC. Рассмотрев касательные l B , в точках B 2 , аналогично получим l B AC, l C AB. Поэтому треугольник ABC гомоте- тичен треугольнику, образованному прямыми l A , l B , l C . При этой гомотетии переходит в A 2 , B 1 — в B 2 , C 1 — в C 2 . Поэтому прямые A 1 A 2 , B 1 B 2 , пересекутся в центре гомотетии. Пусть ABC — один из треугольников семейства S. Его высоту примем за единицу. Так как треугольники из S попарно пересекаются, то они лежат в некоторой полосе ширины 2, параллельной стороне Аналогично, взяв полосы, параллельные BC и CA, рассмотрим их пересечение это будет шестиугольник H с углами пои расстояниями между противоположными сторонами, равными 2. У такого шестиугольника длины сторон чередуются, обозначим их a и b см. рис. 264). Пустьвначале a b, тогда все треугольники из S содержат центр фигуры см. рис. Если же a > b, то рассмотрим прямые l X , l Y , l Z , параллельные сторонам шестиугольника и равноудаленные от них. В качестве искомых точек ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ a a a b b b l Z l Y l X X Y Z l Z l Y l X X Y Z T Рис. Рис. Рис. 266 X , Y и Z возьмем середины отрезков, высекаемых сторонами на этих прямых (см. рис. Покажем, что любой треугольник T , T ∈ S, содержит какую-то точку из множества M = {X, Y, Заметим, что T пересекает любую из прямых l X , и см. рис. так как иначе T лежит в полосе меньшей ширины, чем его высота. Предположим противное T не содержит точек X, Y или Z, тогда без ограничения общности можно считать, что T пересекает выше и левее X, а левее Y см. рис. 266). Так как T ∼ XY Z, то легко видеть , что правая нижняя вершина T лежит в XY Z, а значит, T не пересекает l Z — про- тиворечие. A B C O Рис. 267 564. Рассмотрим граф, вершинами которого являются города, ребрами — авиалинии. По условию получится связный граф, степени вершин которого равны трем. Предположим, что в графе, степени вершин которого не превосходят трех, естьдва пересекающихся (по вершине) цикла (см. рис. 267). Тогда рассмотрим вершину, в которой они разветвляются . Эта вершина, очевидно, имеет степеньтри. Удалим эту вершину и три выходящих из нее ребра OA, OB, OC. Нетрудно заметить, что граф сохранил связность, так как существует путь, соединяющий вершины A, B и Рассмотрим полученный граф. Если в нем естьдва пересекающихся цикла, то повторим операцию. Итак далее. Очевидно, что никакие две удаленные вершины не соединены ребром в исходном графе, так как мы удаляли только вершины степени три, а после каждой операции степени вершин, соседних с удаленной, уменьшались, те. они не могут стать равными трем. Предположим, что в связном графе n вершин и не менее чем 3 ·n ребер. Докажем, что в таком графе обязательно есть два пересекающихся цикла. Предположим, что это не так. В силу связности графа, в нем можно выде- литьдерево с n вершинами. Будем возвращать в граф оставшиеся после выделения дерева ребра. Добавление каждого ребра увеличивает ко УЧЕБНЫЙ ГОД, 11 КЛАСС 345 личество циклов по крайней мерена один. Однако, если какое-либо ребро добавит не менее двух циклов, они будут пересекающимися, что противоречит нашему предположению. С другой стороны, каждый цикл содержит не менее трех вершин, и никакая вершина не входит в два цикла. Кроме того, дерево с n вершинами содержит ровно n − 1 ребро. Следовательно, ребер не более, чем (n − 1) + n 3 < 4n 3 . Противоречие. Пусть N = 1998 — количество вершин в исходном графе, тогда исходное количество ребер равно 2 N . За каждую операцию выкидывания вершины количество вершин уменьшается на одну, а количество ребер уменьшается натри. Предположим, что было сделано x операций. Тогда стало вершин и 2 N −3x ребер. До тех пор, пока выполняется неравенство 2 N − 3x 4 3 (N − x), вершины удалятьможно. Решив это неравенство, получаем x N 10 , те. можно удалить 10 + 1 = 200 вершин. Отсюда и следует утверждение задачи. Ответ. r 1998 = Пусть r n — радиус й окружности, S n = r 1 + r 2 + . . . + r n . Тогда уравнение (n + й окружности имеет вид+ (y − (2S n + r n+1 )) 2 = Условие касания означает то, что уравнение y+(y−(2S n +r n+1 )) 2 = имеет один корень, тогда его дискриминант D = (2r n+1 − 1) 2 − 8S n = те, так как r n+1 > 0 . Отсюда r 2 = 3 2 , r 3 = 5 2 . По индукции легко проверить, что r n+1 = n + 1 2 . Действительно, если r n+1 = = n + 1 при n k, то 2 + . . . + k − 1 2 + 1 2 = 2 k(k + 1) 2 − k 2 + 1 2 = = k + 1 2 = (k + 1) − 1 2 . 566. Ответ. Да. Пустьнабор N = {a 1 , . . . , a n } состоит из чисел, удовлетворяющих данному условию U. Тогда набор N 1 = {b 1 , . . . , b n , b n+1 }, где b 1 = a 1 , . . . , b n = a n , b n+1 = также удовлетворяет U. Прибавим к каждому число c = (b 2 − b 1 ) 2 · (b 3 − b 1 ) 2 · . . . · (b n+1 − b n ) 2 . Получим набор состоящий из натуральных чисел и также удовлетворяющий U, так как+ c) − (b j + c)) 2 = (b i − и (b i + c)(b j + c) = b i b j + c(b j + b j + c) — делится на (b i − b j ) 2 ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Поэтому, взяв в качестве исходного набор N = {1, 2}, последовательным применением указанной выше процедуры мы получим набор N 2 , состоящий из трех, набор N 4 — из четырех, . . . , N 2n−4 — из n чисел. Рассмотрим множества M центров сфер диаметра 1, лежащих в данном тетраэдре T . Так как M — множество точек, удаленных от всех граней T не менее, чем на 1/2, то M — это тетраэдр с гранями, параллельными граням тетраэдра T , те и T гомотетичны. Центры вписанных сфер обоих тетраэдров совпадают, поэтому коэффициент k гомотетии равен − 1/2 r , где r — радиус сферы, вписанной в T С другой стороны, две сферы единичного диаметра не пересекаются, поэтому расстояние между их центрами не меньше 1, значит, длина одного из ребер тетраэдра M, содержащего эти центры, не меньше 1. Отсюда следует, что k 1 длины ребер тетраэдра T не больше 100), те, откуда 2r 100 99 > 1, 01 . Итак, диаметр сферы, вписанной в, больше 1,01, те. в качестве искомой можно выбрать сферу, вписанную в T . |