Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
568. Пусть Φ 1 , . . . , Φ k — всевозможные расположения фигуры Φ в прямоугольнике. Утверждение задачи можно переформулировать так: можно взятьфигуры такой неотрицательной толщины d i , i = 1 ,. . . , рационально, что суммарная толщина всех фигур над каждой клеткой прямоугольника будет равна Предположим, что это утверждение неверно. Покажем, что тогда существует такое заполнение клеток прямоугольника числами, при котором сумма всех чисел положительна, а сумма чисел в клетках, закрываемых фигурой при любом ее положении, неположительна. Введем обозначения индексом j, j = 1, . . . , m · n, будем нумеровать клетки прямоугольника, индексом i, i = 1, . . . , k, — положения фигуры на прямоугольнике. Положим P ij = 1 , если я клетка закрыта фигурой Φ i , P ij = 0 , если незакрыта. Тогда набору чисел {d i } соответствует заполнение клеток прямоугольника числами θ j = 1 − i d i P ij , характеризующими уклонение покрытия прямоугольника фигурами от равномерного. По нашему предположению, все числа не могут бытьравными нулю. Выберем числа d j 0 так, чтобы величина |θ| уклонения была минимальна, где |θ| 2 = j θ 2 j . Покажем, что получившиеся числа и образуют искомое заполнение клеток прямоугольника Почему существует набор {d i }, для которого |θ| — минимален? После раскрытия скобок получаем УЧЕБНЫЙ ГОД, 9 КЛАСС 347 Заменим одно число на d i = d i + x , x −d i . Тогда θ j = θ j − следовательно |θ | 2 = j θ 2 j = j θ 2 j − 2x j θ j P ij + x 2 j P 2 ij , те. Здесь a = j P 2 ij = j P ij = N , где N — число клеток в фигуре, c = |θ| 2 . Квадратный трехчлен y = y(x), заданный на множестве x −d i , принимает наименьшее значение при x = 0 в случае 0 , если d i > 0 , ив случае b i 0, если d i = 0 . Таким образом, предположив, что |θ| минимален на наборе {d i }, мы получаем, что если d i > 0 , то 0 , а если d i = 0 , то b i 0. Значит, сумма чисел, закрываемых фигурой это как раз) — неположительна; с другой стороны, сумма всех чисел в прямоугольнике положительна, так как она равна, а. Действительно, так как при 0 b i = 0 1998–1999 г класс. Ответ. Заметим, что 9A = 10A − A. При вычитании этих чисел столбиком нив одном разряде, кроме младшего, не приходится заниматьединицу из следующего разряда. Таким образом, сумма цифр разности равна разности суммы цифр чисел 10A и A которые равны) плюс 9. |θ| 2 = X j 1 − X i d i P ij ! 2 = X i d 2 i X j P 2 ij + X i,k M ik d i d k + m · n − где M ik 0. Таким образом N X i (d i − 1) 2 + X i,k M ik d i d k + m · n − где N — число клеток в фигуре. Отсюда следует, что, если d i > 2 для некоторого i, тов то время как |θ| 2 = m·n, если все d i = 0. Итак, функция |θ| 2 — многочлен второй степени, заданный на множестве 0 d 1 , . . . , d m·n те. на (m · мерном кубе. Многочлен достигает своего наименьшего значения на кубе. Точка минимума имеет рациональные координаты, так как это многочлен второй степени и его коэффициенты — целые числа, те. координаты этой точки — решение линейной системы уравнений с целыми коэффициентами ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ. Рассмотрим некоторый путь, соединяющий некоторые два города, возможно включающий в себя некоторые закрытые после кризиса рейсы. Покажем, что в этом пути любой закрытый рейс можно заменитьпосле- довательностью незакрытых. Пронумеруем авиакомпании числами от 1 до. Водной из авиакомпаний сохранилисьвсе рейсы предположим, что впервой. Тогда в любой другой авиакомпании закрыли по одному рейсу. Рассмотрим только рейсы первой и второй авиакомпаний из каждого города выходит по одному рейсу этих авиакомпаний. Следовательно, все города разбиваются на циклы. Водном из этих циклов закрыли один рейс. Очевидно, можно пролететьостальными рейсами этого цикла, следовательно, мы можем обойти любой закрытый рейс. Отметим, что мы при этом не используем рейсы других авиакомпаний, следовательно, аналогично можно обойтисьбез остальных закрытых рейсов. A B C A 0 C 0 D L K I S 1 S 2 Рис. 268 571. Из точки I проведем касательную к окружности так, чтобы луч IK пересекал меньшую дугу A 0 C (см. рис. 268). Аналогичным образом проведем касательную IL к окружности Биссектриса AI угла BAC делит дугу BC на 2 равных дуги. Поэтому точки A, лежат на одной прямой. Аналогично, на одной прямой лежат точки C, I и Из равенств 2 C 0 BA 0 = 1 2 C 0 B + BA 0 , ∠A 0 IC = 1 2 AC 0 + A 0 C = 1 2 C 0 B следует, что ∠A 0 IC и A 0 I = Далее, пусть D — середина отрезка BC, тогда касается BC в точке В прямоугольных и катеты и равны и = по доказанному выше. Следовательно, A 0 KI = Отсюда ∠A 0 IK = ∠A 0 CD = ∠A 0 CB . Но ∠A 0 CB теорема о вписанном угле) и ∠A 0 AB = ∠A 0 AC . Значит, ∠A 0 IK следовательно прямая IK параллельна AC. Аналогично, IL AC, следовательно лежат на одной прямой, параллельной AC. 572. Ответ. Можно. Лемма. Пусть дан набор простых чисел p 1 , . . . , p n . Тогда можно за несколько перекрашиваний добиться того, что поменяют цвет УЧЕБНЫЙ ГОД, 9 КЛАСС 349 те и только те числа, которые делятся на все простые числа на- бора. Д ока за тел ьс т во. (формула включения–исключения). Для каждого непустого поднабора наших простых чисел перекрасим числа, не взаимно простые с произведением всех чисел этого поднабора. Число, делящееся на все числа набора, перекрашивалосьпри каждом таком перекрашивании, всего перекрашиваний было 2 n − 1, следовательно, числа, делящиеся на все числа набора, перекрашены. Пустьнекоторое число k не делится хотя бы на одно из чисел набора, например, на p 1 . Тогда оно не перекрашивалось, когда мы перекрашивали числа, не взаимно простые с. Остальные непустые поднаборы чисел можно разбить на пары следующим образом поднабору, не содержащему p 1 , в пару ставится поднабор, полученный из него добавлением p 1 . При этом число k перекрашивается или при обоих перекрашиваниях пары, или ни при одном. Поэтому число k не будет перекрашено. Лемма доказана. Первое решение. Для каждого набора простых чисел, произведение которых не больше 1 000 000, перекрасим числа, делящиеся на все эти простые числа. По лемме такая операция возможна. Докажем, что любое число k при этом будет перекрашено. Пусть k имеет m различных простых делителей, тогда оно перекрашивалосьпри 2 m − 1 операции, т. е. нечетное число раз. Второе решение. Назовем два числа эквивалентными, если у них совпадают наборы простых делителей. Заметим, что при наших операциях классы эквивалентности перекрашиваются целиком. Будем говорить, что один класс больше другого, если все простые делители второго класса являются делителями первого. Из леммы следует, что мы можем перекра- ситьлюбой класс, перекрасив вместе с ним только большие классы. Сначала перекрасим минимальные классы (класс называется минимальным, если он не больше никакого другого класса. Исключим их из рассмотрения. Среди оставшихся некоторые классы станут после такого исключения минимальными. При необходимости перекрасим их и тоже исключим. Итак далее. Поскольку классов конечное число, процесс закончится. Ответ. n(n + Общее количество отрезков длины 1 равно 3 · n(n + 1) 2 . Все отрезки, параллельные двум сторонам большого треугольника, не образуют треугольников, так как любой треугольник состоит из отрезков, параллель ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ ных всем трем сторонам. Следовательно 3 · 3 · n(n + 1) 2 = n(n + отрезков длины 1 отметитьможно. Докажем, что большее количество отрезков отметить нельзя. Рис. Заштрихуем треугольники со стороной 1, как показано на рис. 269. Треугольники содержат все отрезки длины 1, причем каждый отрезок принадлежит ровно одному треугольнику. Для того чтобы не образовался ни один из заштрихованных треугольников, в каждом из них можно отметитьне более двух отрезков. Значит, количество выделенных отрезков не превышает от их общего числа. При n = 1 неравенство обращается в равенство 0 = 0. При n > докажем, что сумма дробных частей на каждом промежутке между двумя последовательными квадратами удовлетворяет неравенству 2m + 1 Из неравенства между средним арифметическими средним квадратичным получаем+ a + m 2 + 2m − a 2(2m 2 + 2m) < 2m + при 0 a Следовательно+ a + m 2 + 2m − a Просуммировав эти неравенства при a = 0, 1, . . . , m − 1 и неравенство+ m 1 получаемое делением на 2 обеих частей (2) при a = приходим к неравенству (Суммируя неравенство (1) по всем m от 1 до n − 1, получаем 1 Остается заметить, что 0 575. Заметим, что ∠BCF = 180 ◦ − ∠BEF = ∠AEF , аналогично = ∠F DC, значит AEF ∼ DCF . Пусть K и L — середины отрезков AE и CD соответственно. Тогда ∠AKF = ∠F LB как углы между медианой и основанием в подобных треугольниках, поэтому точки, K, F , L лежат на одной окружности. Но, так как серединные перпендикуляры к отрезками пересекаются в точке O, то точки K и лежат на окружности с диаметром BO. Но тогда и точка F лежит на этой окружности, и ∠BF O — прямой. Ответ. Выигрывает Петя УЧЕБНЫЙ ГОД, 10 КЛАСС 351 A B C E D O K L F Рис. Мысленно разобьем контакты на четыре одинаковых группы A, B, и D. В каждой группе пронумеруем контакты числами от 1 до 500. Петя будет отвечатьна любой ход Васи так, чтобы для каждого номера k от контактов A k , B k , и отходило поровну проводов. До начала игры это условие, очевидно, выполняется. Именно благодаря этому условию проигрышная ситуация впервые случится после Васиного хода. Опишем подробно Петину стратегию. Если Вася перерезает провод между контактами одной группы, например, провод A i A j , то Петя перережет провода B j B j , и D j D j . Если Вася перерезает провод между проводами из разных групп и с разными номерами, например, провод, то Петя в ответ перережет провода A j B i , и C j D i . Если же Вася перерезал провод между контактами из разных групп с одинаковыми номерами, например, провод A k B k , то Петя перережет провод Заметим, что из описанной стратегии Пети следует, что провода, которые он собирается резать, не будут отрезаны до его хода. Поэтому Петя всегда сможет разрезатьтребуемые провода. Отметим, что каждый раз после хода Пети от контактов A k , B k , и отходит поровну проводов при этом от одного из них столько же проводов отходило уже после Васиного хода. Поэтому ситуация, когда от одного контакта отрезан последний провод, случится впервые после Ва- синого хода. Так как количество проводов конечно, проиграет Вася ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ класс. ПустьВинни и Пятачок вначале кладут свои орехи во вторую и третью банки, несмотря на ходы Кролика, до тех пор, пока водной из банок не станет 1998 орехов. После этого тот, кто должен кластьорехи в эту банку (пусть, например, это Винни) начинает класть их в I. При этом он уже положил во II банку не менее 999 орехов, значит, в III орехов тоже не менее 999 (туда их клал Пятачок. После этого Пятачок продолжает кластьв III банку орехи, пока там не станет 1998 — это произойдет не более, чем через 500 ходов, так как в III банку также приходится класть орехи Кролику, чтобы не проиграть. После этого Пятачок также может кластьорехи в I банку, так как там не более 500 орехов, положенных Вин- ни, а Кролик вынужден будет положитьорех во II или III, где их уже по. Ответ. a 1 = a 2 = . . . = 2 Пустьдля каких-то двух членов последовательности и a k+1 их НОД равен 1. Тогда НОД(a k , a k+1 ) = НОД(a k + a k+1 , a k+1 ) = = НОД(a k+2 , a k+1 ) , те. для всех последующих членов последовательности НОД тоже будет равен 1. При этом, начиная с го члена, последовательность превращается в последовательность a n = a n−1 + которая неограниченно возрастает, что невозможно. Тогда a k+2 a k+1 + a k 2 max{a k+1 , и max{a k+1 , a k } не возрастает. Следовательно, когда-то он стабилизируется. Если при этом a k+1 = a k , то a k+2 < d , a k+3 < d , что невозможно. Поэтому a k+1 = a k+2 = . . . = d , откуда d = 2. Но тогда+ 2 НОД(a k−1 , 2) = откуда a k−1 = 2 , и последовательность состоит только из двоек. Пусть O 1 , O 2 , O 3 — центры малых окружностей (см. рис. Так как ∠KO 1 M = 90 ◦ + 1 2 ∠A, а ∠KLM = 90 ◦ − 1 2 ∠A, то ∠KO 1 M + + ∠KLM = 180 ◦ , и является серединой дуги KM вписанной в окружности. Аналогично и лежат на этой окружности и являются серединами дуги. Используя результат задачи 571, заключаем, что построенные касательные проходят через центр окружности, вписанной в треугольник KLM, что и требовалосьдоказать. 580. Будем различатьдва типа ходов — внутренние и внешние, в зависимости оттого, куда ставится фишка, делающая ход внутрьисходного квадрата n × n клеток, или вне его УЧЕБНЫЙ ГОД, 10 КЛАСС 353 A B C K L M O 1 O 2 O 3 Рис. 271 Пустьполучена позиция, где дальнейшие ходы невозможны, причем сделано k внутренних ходов и l внешних. Ясно, что никакие две фишки не находятся в соседних клетках; поэтому в исходном квадрате n × × n не менее чем клеток пусты. Действительно, нетрудно понять, что квадрат разрезается на доминошки (в случае четной стороны) или доминошки и одну угловую клетку (в случае нечетной, а в каждой доминошке естьхотя бы одна пустая клетка. Так как каждый внутренний ход увеличивал количество пустых клеток не более, чем на а каждый внешний — не более, чем на 2, то имеем неравенство + 2l n 2 Предположив теперь, что n четно, разобьем исходный квадрат на 4 четырехклеточных квадратиков и заметим, что на каждый квадратик при- шлосьне менее двух ходов, в которых участвовали (делали ходили сни- малисьс доски) фишки, стоявшие в клетках этого квадратика. Поскольку в каждом внутреннем ходе участвовали фишки не более, чем двух квадратиков, а в каждом внешнем — не более, чем одного, то + l 2 n 2 Из неравенств (1) и (2) получаем k + l n 2 3 n 2 3 , те. утверждение задачи в этом случае верно. Легко видеть, что оно верно также при n = 1 и при n = В случае n = 2m + 1, где m > 1, в кресте , образованном третьей сверху горизонталью и третьей слева вертикалью, выделим 2m доминошек , а остальную часть исходного квадрата разобьем на m 2 че- тырехклеточных квадратиков. В каждом внутреннем ходе участвовать могли фишки, принадлежащие не более чем двум из m 2 + рассматриваемых фигура в каждом внешнем — не более чем одной. Имеем неравенство+ поскольку фишки каждого из квадратиков участвовали не менее, чем в двух ходах, афишки каждой доминошки — по крайней мере водном ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Из (1) и (3) следует, что 3(k + l) 4m 2 + 4m = n 2 − 1. Если здесь 0 (mod 3), то, очевидно, 3(k + l) ив противном случае n 2 ≡ 1 (mod 3) и k + l n 2 − 1 3 = n 2 3 . Тем самым утверждение задачи полностью доказано. Замечание. Можно доказать, что для любого ε > 0 при достаточно больших n количество ходов будет больше, чем n 2 1 2 − ε . Один из методов доказательства заключается в следующем. Предположим противное. Рассмотрим каемку нашего квадрата ширины 2, каемку квадрата, получающегося выкидыванием первой, и т. д., всего k = [nε/8] каемок. Заметим, что внутри последней каемки содержится хотя бы n 2 (1 − ε/2) 2 > n 2 (1 − ε/4) клеток. Тогда за максимум 2 − ходов из нашего квадрата ушло хотя бы 2 1 2 n 2 (1 − фишек значит, было хотя бы ходов, на которых количество фишек в нем уменьшалось на 2; эти ходы вели из первой каемки вовне, и не затрагивали квадрата внутри первой каемки. Тогда зане более чем n 2 1 2 − 3 ходов из следующего по величине квадрата ушло хотя бы 2 n 2 (1 −ε) фишек значит, было хотя бы εn 2 ходов, на которых количество фишек в нем уменьшалось на 2; эти ходы вели из второй каемки вовне. Аналогично, из третьей каемки вовне вело хотя бы 2εn 2 ходов, . . . , из й каемки — ходов. Однако при больших n 2 k−2 εn 2 = 2 [nε/8]−2 εn 2 > n 2 , те. ходов гораздо больше, чем предполагалось. Противоречие. Заметим, что 44n естьсумма 4 экземпляров числа n и 4 экземпляров числа 10n. Если складыватьэти числа поразрядно, тов каждом разряде окажется сумма учетверенной цифры из этого же разряда числа n и учетверенной цифры из следующего разряда. Если при этом не происходит никаких переносов, то каждая цифра числа n складывается 8 рази сумма цифр во всех разрядах оказывается равной 800. При переносах же сумма цифр, очевидно, уменьшается (так как из одного разряда вычитается, а к другому прибавляется только 1). Поэтому в ситуации условия задачи переносов не происходит. Это означает, в частности, что любая цифра числа n не превосходит 2. Тогда приумножении напросто умножается на 3 каждая его цифра, а, значит, и сумма цифр. Поэтому сумма цифр числа 3n равна 300. |