9-10 классы. Решение. См решение и критерии задачи 11 2 в треугольнике abc точки a 1, b 1, C
 Скачать 103.7 Kb.
|
|
Решения и критерии, 9-10 класс. Во всех критериях пропущено в виду самоочевидности, что полное решение стоит полный балл. №1 Условие. В этой задаче запись x mod n, где x – целое а n – натуральное, обозначает такое целое число y от 0 до n −1, что x−y делится на n. Существует ли такая функция f, определенная для целых значений аргумента и принимающая целые значения, что при любом целом x верно f ( (x 2 + 1) mod 7 ) = ( f (x) 2 + 1 ) mod 11 ? Автор: В.Тиморин Решение. См. решение и критерии задачи 11.1. №2 В треугольнике ABC точки A 1 , B 1 , C 1 – середины сторон BC, AC, AB соответственно. Точки A 2 , B 2 , C 2 – середины ломанных BAC, ABC, ACB соответсвенно (точка называется серединой ломанной если принадлежит ломанной и делит ее на две ломанных равной длины). Докажите, что прямые A 1 A 2 , B 1 B 2 , C 1 C 2 проходят через одну точку. Автор: Из материалов тренировочного лагеря сборной Израиля на международну олим- пиаду Общая преамбула ко всем трем решениям. Пусть стороны треугольника BC = a, AC = b, AB = c. Не умаляя общности, a 6 b 6 c. Тогда A 2 лежит на отрезке AB, причём AA 2 = c −b 2 . Точка B 2 лежит на отрезке AB, причём BB 2 = c −a 2 . Точка C 2 лежит на отрезке AC, причём CC 2 = b −a 2 Решение 1. Заметим, что условие задачи не симметрично. Исправим это. Найдем, где на прямой CA лежит точка A 3 – пересечение с прямых CA и A 1 A 2 . Обозначим отрезок AA 3 = x, положительное направление в сторону, противоположную точке C. Тогда т. Менелая для точек A 1 , A 2 , A 3 в треугольнике ABC гласит: AA 2 A 2 B · BA 1 A 1 C · CA 3 A 3 A = c −b 2 c+b 2 · a 2 a 2 · b + x −x = −1. после стандартных преобразований получаем x = c −b 2 . Поскольку AA 2 = AA 3 , прямая A 3 A 2 перпендикулярная внешней биссектрисе угла , то есть параллельна внутренней. Следовательно, она является биссектрисой угла B 1 A 1 C 1 . Аналогично, прямые B 1 B 2 и C 1 C 2 – биссектрисы углов треугольника B 1 A 1 C 1 и значит все три прямые пересекаются в центре вписанной окружности треугольника B 1 A 1 C 1 Решение 2. Назовём вневписанные окружности, касающиеся отрезков BC, CA, и AB, W A , W B , W C соответственно. Заметим, что точка A 2 - середина отрезка между точками касания W C с отрезком AB и W B с продолжением луча BA за точку A. Точка A 1 – середина отрезка между точками касания W C с продолжением луча за и W B с продолжением луча BC за C. Значит, A 1 A 2 - радикальная ось окружностей W B и W C . Аналогично, получаем, что прямые B 1 B 2 - радикальная ось W A , W C , C 1 C 2 - радикальная ось W A , W B . Значит прямые A 1 A 2 , B 1 B 2 , C 1 C 2 пересекаются в одной точке - радикальном центре окружностей W A , W B , W C Решение 3. Посчитаем, в каком отношении отрезки A 1 A 2 и C 1 C 2 делят отрезок B 1 B 2 Применим теорему Менелая для треугольника AB 1 B 2 и секущей C 1 C 2 . Получим AC 1 C 1 B 2 · B 2 X XB 1 · B 1 C 2 C 2 A = c/2 a/2 · B 2 X XB 1 · −a/2 (a + b)/2 = −1, где Х - точка пересечения B 1 B 2 и C 1 C 2 , здесь и далее длины всех отрезков на промях AB, BC, AC считаются комбинированием формул из преамбулы. Итак, B 2 X XB 1 = a+b c Теперь пусть X ′ – точка пересечения B 1 B 2 и A 1 A 2 . Треугольники A 1 B 1 X ′ и A 2 B 2 X ′ подобны (A 1 B 1 – средняя линия в треугольнике ABC), B 2 X ′ X ′ B 1 = A 2 B 2 A 1 B 1 = (a+b)/2 c/2 . Значит, X = X ′ , ч.т.д. Критерии. A0 решение задачи в частном случае (например, если ABC – равнобедренный): − и 0 баллов. Недоведенный счет в координатах (или любым другим стандартным методом): 0 баллов. №3 Условие. Вася пришел в казино, имея один вшэ-коин (единственную в мире виртуальную валюту, которую можно делить на любые части; например, можно поставить на кон π 10 вшэ- коина). В казино игрокам предлагается делать ставки на цвет шара, который будет вытащен из ящика. Фиксировано число p, причем 1 < p < 2. Если цвет вытащенного шара совпадает с тем, на который игрок поставил x денег – игрок получит назад px денег, если не совпадает – не получит ничего. Для ставок в каждом раунде можно использовать не только деньги, имевшиеся к началу игры, но и выигрыши прошлых раундов. Перед началом игры Вася смог подсмотреть, что в ящик положили 2 черных и 3 красных шара (других шаров нет), сыгранные шары обратно в ящик не возвращаются, игра происходит пока ящик не опустеет. Какую максимальную сумму Вася может гарантированно иметь к концу розыгрыша? Автор: Г.Челноков Решение. См. решение задачи 11.2. Критерии. Внимание! хотя задача та же, что в 11 классе, критерии отличаются. A0 Правильный ответ без доказательства − и 0 баллов. Любые стратегии без доказатель- ства оптимальности (или с неверным доказательством оптимальности) − и 0 баллов. Верно доказанная лемма, что не выгодно ставить одновременно на оба цвета – 0 баллов (однако и решение, полное за исключением отсутствия объяснения, что не надо ставить на оба цвета одновременно, приравнивается к полному). A2 Верно разобран случай, когда остались два шара одного цвета и один – другого: ∓ и 5 баллов. A5 Есть процедура заполнения таблички, аналогичная приведеной в решении: +/2 и 10 баллов. A7 Арифметическая ошибка при наличии всех этапов решения и верной логике: ± и 15 баллов. A8 Решение, полное за исключением отсутствия объяснения, что не надо ставить на оба цвета одновременно: +. и 20 баллов. №4 Условие. Напомним, что запись числа n в t-ичной системе счисления это представление n = a k a k −1 · · · a 0 = a k t k + a k −1 t k −1 + · · · + a 0 , где a i – целые числа от 0 до t − 1, причем a k – не ноль. Назовем четырехзначное число abcd интересным если ab + cd = bc. Найдите количество пар интересных чисел, сумма которых – тоже интересное число (как функцию от t). Авторы: А.Горбунов, Г.Челноков Решение. На протяжении этого решения число сочетаний из n по k обозначается ( n k ) , чита- телей, более привыкших к нотации C k n просим обращать внимание на “перевернутый” порядок индексов: ( n k ) = C k n Итак, нам требуется найти число пар N 1 = a 1 b 1 c 1 d 1 и N 2 = a 2 b 2 c 2 d 2 , таких что N 1 + N 2 = a 3 b 3 c 3 d 3 , причем выполняются три соотношения b i c i = a i b i + c i d i при i ∈ {1, 2, 3}. Наше решение задачи состоит из двух этапов: Утверждение 1. Пары (N 1 , N 2 ) биективно соответствуют четверкам (b 1 , c 1 , b 2 , c 2 ), таким что b 1 − c 1 > 2, b 2 − c 2 > 2 и c 1 + c 2 > t − 1. Комментарий 1. Говоря более развернуто, в Утверждении 1 сказано следующее: у каж- дой удовлетворяющей условию задачи пары (N 1 , N 2 ) их цифры (b 1 , c 1 , b 2 , c 2 ) таковы, как ска- зано в Утверждении 1, и обратно, каждая четверка (b 1 , c 1 , b 2 , c 2 ), удовлетворяющая условию Утверждения 1, ровно одним способом достраивается до пары (N 1 = a 1 b 1 c 1 d 1 , N 2 = a 2 b 2 c 2 d 2 ), удовлетворяющей условию задачи. Утверждение 2. Количество четверок (b 1 , c 1 , b 2 , c 2 ), удовлетворяющих условиям Утвер- ждения 1, есть в точности ( t −1 4 ) План решения намечен, осталось его осуществить. Лемма 1. Всякое интересное число имеет вид: N = (b − c − 1)bc(t − b + c) где 0 6 b, c 6 t − 1 и b − c > 2. И обратно, всякая запись такого вида является корректной записью в t-ичной системе счисления интересного числа. Доказательство. Условие, что число N = abcd является интересным есть bc = ab + cd, или эквивалентно (t − 1)(b − c) − ta − d = 0 (∗). Значит, по заданному значению b −c пара (a, d) восстанавливается не более чем одним способом, иначе число (t − 1)(b − c) имело бы больше одной записи в t-ичной системе счисления. Но заметим, что при подстановке a = b − c − 1, d = t − b + c равенство верно тождественно, кроме того, a > 1 (за это отвечает условие b − c > 2), неравенства a > t − 1 и 0 > d > t − 1 очевидно следуют из 0 > b, c > t − 1. Доказательство утверждения 1. Пусть N 1 = a 1 b 1 c 1 d 1 и N 2 = a 2 b 2 c 2 d 2 – два интересных чис- ла. Рассмотрим “t-ичную запись без переносов” (a 1 + a 2 )(b 1 + b 2 )(c 1 + c 2 )(d 1 + d 2 ), она конечно же может и не быть правильной t-ичной записью, поскольку некоторые из “цифр” могут быть больше t; но она удовлетворяет равенству (*), поскольку ему удовлетворяют a 1 b 1 c 1 d 1 и a 2 b 2 c 2 d 2 Посмотрим, что происходит, когда мы “вспоминаем”, что надо сделать перенос. Если перенос из разряда единиц, то d уменьшается на t, а c увеличивается на 1, значит всего левая часть (*) увеличивается на 1. Аналогично если перенос из разряда t — то c уменьшается на t и b увеличивается на 1, всего левая часть (*) увеличивается на t 2 − 1. Аналогично при переносе из разряда t 2 левая часть (*) уменьшается на t 2 . Заметим, что из одного разряда не может быть сделано больше одного переноса: то что стоит в разряде есть сумма двух цифр, плюс возможно единичка, пришедшая из переноса – это точно меньше 2t. Значит, если соотношение (*) выполнялось до всех переносов и выполняется после всех – то либо не было сделано ни одного переноса, либо были сделаны все три. Докажем, что первый вариант невозможен. В самом деле, a 1 + d 1 = t − 1 по Лемме 1, аналогично a 2 + d 2 = t − 1. Но если из разряда единиц не было переносов, из разряда t 3 его тоже не было (число осталось четырехзначным), тогда сумма цифр в этих разрядах сейчас равна a 1 + d 1 + a 2 + d 2 = 2(t − 1). Но такую сумму двумя цифрами можно набрать единственным образом: (t − 1) + (t − 1). То есть a 1 + a 2 = t − 1. По Лемме 1 это означает b 1 − c 1 + b 2 − c 2 = t + 1, то есть b 1 + b 2 > t + 1 – тогда из разряда t 2 есть перенос – противоречие! Итак, должны осуществиться ровно три переноса. Докажем, что это эквивалентно условию c 1 + c 2 > t − 1. В разряде единиц стоит 2t − b 1 − b 2 + c 1 + c 2 > 2 + c 1 + c 2 – при c 1 + c 2 > t − 1 перенос есть; в разряде t стоит c 1 + c 2 + 1 (единичка пришла от переноса) – перенос есть тогда и только тогда, когда c 1 + c 2 > t − 1; в разряде t 2 стоит b 1 + b 2 + 1 > c 1 + c 2 + 5 – при c 1 + c 2 > t − 1 перенос есть, наконец из разряда t 3 переноса нет когда он есть из разряда единиц. Для Утверждения 2 мы приведем комбинаторное доказательство. Комбинаторное доказательство Утверждения 2 с наводящими соображениями. Напомним, что выражение ( n+k k ) считает способы расставить в ряд n белых и k черных шаров. Научимся через такие функции выражать ответы в задачах типа нашей, начнем с более простой. Поучительный пример 1. Пусть мы хотим перечислить пары (c 1 , c 2 ), такие что 0 6 c 1 , c 2 6 t − 1 и c 1 + c 2 > t − 1. Построим для этого биекцию между такими парами, и расстановками в ряд двух черных и t − 1 белого шарика следующим образом: для расстановки посчитаем число белых шариков, стоящих правее левого черного шарика (не важно до или после правого черного) – назовем это число c 1 ; аналогично посчитаем число белых шаров, стоящих левее правого черного – назовем это число c 2 . Очевидно, оба числа лежат в заказанных пределах, притом c 1 + c 2 > t − 1 — каждый белый шарик посчитан хотя бы один раз, те что стоят между черными посчитаны дважды. Оставляем читателю додумать, почему построена именно биекция, то есть по паре (c 1 , c 2 ) можно построить расстановку шариков в ряд, притом ровно одну. Итак, количество таких пар (c 1 , c 2 ) есть в точности ( t+1 2 ) Поучительный пример 2. Отлично, усложним задачу. Пусть мы ищем число четверок (b 1 , c 1 , b 2 , c 2 ), таких что 0 6 b 1 , c 1 , b 2 , c 2 6 t−1, b 1 > c 1 , b 2 > c 2 и наконец c 1 + c 2 > t−1. Давайте смотреть на расстановки в ряд четырех черных шаров и t −1 белого. Первый черный шар будет отвечать за b 1 , второй за c 1 , для каждого из них соответствующими числами мы будем называть число белых шаров вправо от них, тогда автоматически получится, что b 1 > c 1 (всякий белый шар, который правее второго слева черного, также правее и первого слева черного). Аналогично третий и четвертый черные шары отвечают за числа c 2 и b 2 соответственно, причем числа равны количеству белых шаров левее соответствующего черного. Аналогично имеем b 2 > c 2 а также c 1 + c 2 > t − 1 полностью аналогично прошлому примеру. Итак, количество таких четверок (b 1 , c 1 , b 2 , c 2 ) есть в точности ( t+3 4 ) А теперь собственно то, что нам нужно. Напомним: мы ищем число таких четверок (b 1 , c 1 , b 2 , c 2 ), что 0 6 b 1 , c 1 , b 2 , c 2 6 t − 1, b 1 > c 1 + 2, b 2 > c 2 + 2 и наконец c 1 + c 2 > t − 1. Чтобы действовать как в примере 2 нам нужно было бы пересчитать расстановки в ряд 4 черных и t − 1 белого шара, такие что между первым и вторым черными стоят хотя бы два белых, и между третьим и четвертым черными стоят хотя бы два белых. Сделаем это так: перечислим все расстановки в ряд четырех черных и t − 5 белых, таких расстановок ровно ( 4+t −5 4 ) = ( t −1 4 ) . Теперь в каждую из расстановок добавим два белых шара между первым и вторым черными, и два белых между третьим и четвертым черными. Оставляем читателю доказать, что построена биекция между множеством всех расстановок четырех черных и t − 5 белых, и множеством расстановок с приведенным выше дополнительным условием четырех черных и t − 1 белого. Заметим, что возможно и чисто алгебраическое доказательство утверждения 2, которое мы не приводим по двум причинам: во-первых, оно ничем не хорошо по сравнению с комбина- торным, но технически существенно сложнее. Во-вторых, никто из участников, пытавшихся пройти этим путем, к завершению не подошел даже близко. Критерии. A0 Попытка для частных значений t решить задачу перебором: 0 баллов. Найдено коли- чество интересных чисел вместо того, что спрашивалось в задаче: 0 баллов (но на этом пути могут быть получены промежуточные результаты, подпадающие под действие критерия A3 и оцениваемые по нему). A3 Доказано, что интересное число задается двумя своими цифрами, получено выражение через эти цифры двух оставшихся и выписаны неравенства, которым должны удовлетворять генерирующие цифры. Например: • для a и b выражаются как c = b − a − 1, d = t − a − 1, причем 1 6 a 6 t − 1, 0 6 b 6 t − 1, b − a > 1; • для b и c выражаются как a = b − c − 1, d = t − b − c, причем 0 6 b, c 6 t − 1, b − c > 2; • для b и d выражаются как a = t − 1 − d, c = b + d − t, причем 0 6 b, d 6 t − 1, b + d > t; 8 баллов. Подчеркнем, что выражения двух оставшихся цифр без неравенства на две генери- рующие не стяот ничего. B3 Доказано, что при если сложении двух интересных чисел получается интересное, то есть переносы хотя бы в двух разрядах: 8 баллов (аддитивно с A3, итого A3+B3=16). Что в этом случае есть все три переноса – не приносит дополнительных баллов. №5 Условие. M - середина стороны BC треугольника ABC. Касательные, проведённые из M к вписанной окружности треугольника ABC, касаются этой окружности в точках P, Q. Ка- сательные из M к вневписанной окружности ABC, касающейся стороны BC, касаются этой окружности в точках R, S. Прямые P Q, RS пересекаются в точке X. Оказалось, что AX = AM . Найдите угол BAC. Авторы: А.Заславский, М.Дидин Решение. План решения: мы докажем два ключевых факта: что биссектриса AL угла BAC также является биссектрисой угла XAM ; и что AX перпендикулярна BC. Тогда в треугольнике ABC медиана AM и высота AX симметричны относителдьно биссектрисы AL – отсюда мы выведем, что угол A прямой. Через Ω 1 и Ω 2 обозначим вписанную и вневписанную окружность из условия соответсвенно, через I 1 и I 2 – их центры. Пусть P – та из точек касания P, Q, что лежит на стороне BC, аналогично пусть R лежит на BC. Введя обозначения для длин сторон треугольника и явным образом выразив отрезки, на которые точки касания вписанной и вневписанной окружности делят стороны треугольника, можно показать что P M = M R (оставляется читателю). Значит все четыре точки P, Q, R, S лежат на окружности Γ с центром M и радиусом P M . Точка X лежит на радикальной оси (для пересекающихся окружностей – просто прямой че- рез общие точки) окружностий Ω 1 и Γ; аналогично X лежит на радикальной оси окружностий Ω 2 и Γ; значит X лежит и на радикальной оси Ω 1 и Ω 2 . Но M тоже лежит на этой радикаль- ной оси, поскольку касательные из M равны. Значит, XM – радикальная ось Ω 1 и Ω 2 , тогда она перпендикулярна биссектрисе AL угла BAC. Поскольку AX = AM , в равнобедренном треугольнике высота AL является биссектрисой. Первый ключевой факт доказан. Заметим что прямая QR перпендикулярна P Q (это ясно, если вспомнить определение окруж- ности Γ), значит QR проходит через точку P ′ , симметричную точке P отнисительно I 1 Лемма 1. Пусть в треугольнике вписанная окружность W с центром I и вневписанная окружность W A с центром I A касаются стороны в точках P , R соответственно. Точка P ′ симметрична P относительно I. Точка R ′ симметрична R относительно I A . Тогда точки A, P, R ′ лежат на одной прямой, а также точки A, P ′ , R лежат на одной прямой. Доказательство. Но другое описание точки P ′ таково: если рассмотреть гомотетию с центром в A, переводящую Ω 2 в Ω 1 , то образом точки R будет точка P ′ . Значит, при этой гомотетии прямая QR (она же P ′ R) остается на месте, значит эта прямая проходит через точку A. Итак, P Q - высота треугольника AP R. Аналогично и RS – высота треугольника AP R, значит – его ортоцентр, то есть прямая AX перпендикулярна прямой P R, она же BC. Второй ключевой факт доказан. Итак, в треугольнике ABC высота и медиана из вершины A симметричны относительно биссектрисы из этой вершины. Тогда угол A прямой. Это следует из Лемма 2. В произвольном треугольнике ABC с центром описанной окружности O прямая, содержащая высоту AH и прямая AO симметричны относительно биссектрисы угола A. Доказательство оставляем читателю в качестве полезного упражнения. Указание: посчи- тайте углы через дуги. Критерии. A0 Недоведенный счет в координатах, решение задачи при дополнительных предположе- ниях: 0 баллов. A1 Отмечено, что четырехугольник P QRS – вписанный: 2 балла. A2 К предыдущему добавлено, что точка X – радикальный центр трех одружностей: впи- санной, вневписанной и описанной около P QRS: 5 баллов. A3 X – ортоцентр AP R: 10 баллов. A5 Доказано, что биссектриса угла BAC также является биссектриссой угла XAM : 15 баллов. Баллы за разные пункты не скалдывается, меньшие уже включены в большие. №6 Условие. Рассматриваются всевозможные наборы действительных чисел x 1 , . . . , x 2021 , не пре- восходящих по модулю 1, с суммой 0. Для какого наименьшего C можно любой такой набор расставить по кругу так, что сумма чисел на любой дуге будет по модулю не больше C? Автор: фолклор Решение. Ответ: 2 − 2 1011 Докажем что C > 2 − 2 1011 . Рассмотрим набор из 1010 чисел −1, и 1011 чисел 1010 1011 . Ясно что при любой расстановке по кругу два положительных окажутся рядом, значит найдется дуга с суммой 2020 1011 Покажем, что при любом количестве чисел n верна оценка C(n) 6 2− 2 ⌊(n+2)/2⌋ . Доказывать это будем, как ни странно, индукцией по n. База при n = 1, 2, 3 проверяется непосредственно. Так же заметим, что для расстановки чисел по кругу условие, что сумма на любой дуге по модулю не больше C, эквивалентно условию, что для произвольной позиции на круге множество сумм по всем дугам, имеющим левый конец в этой позиции, умещается на отрезке длины C. Этой переформулировкой мы и будем пользоваться в дальнейшем. Лемма. Определим операцию преобразования набора: заменим в наборе два числа разных знаков a и −b (пусть a, b > 0) на одно число a − b. Тогда если полученный набор допускает рас- становку для некоторого числа C и выполняется a + b 6 C, то исходный допускал расстановку для C. Доказательство. Расставим по кругу преобразованный набор, и воспользуемся переформули- рованным условием, начиная от позиции, на которой стоит добавленное число a − b. Тогда по переформулированному условию все суммы дуг, начинающихся в этой позиции (включая сум- му, равную нулю) покрываются отрезком длины C. Тогда в этот отрезок попало и одно из чисел a и −b, поскольку они не могут лежать с разных сторон от отрезка – расстояни между ними равно a + b, то есть не превосходит длинны отрезка. Если попало число a – заменим a − b на числа a, −b (в таком порядке), у полученной расстановки те же суммы, что у исходной, и еще сумма a, лежащая где нужно. Аналогично заменим a − b на числа −b, a если попало −b. Теперь докажем индукционный переход. Рассмотрим набор из n чисел не больших 1 по модулю с суммой 0. Рассмотрим наименьшие по модулю положительное и отрицательное число. Если их сумма модулей не больше 2 ⌊(n+2)/2⌋−2 ⌊(n+2)/2⌋ – то можно воспользоваться Леммой. Пусть их сумма больше. Тогда это возможно при четном n только если положительных и отрицательных поровну. Тогда разобьем их на пары, как при доказательстве Леммы. Тогда сумма чисел в каждой паре (то есть “новое” число) по модулю не превосходит 2 ⌊(n+2)/2⌋ . Наша задача расположить их по кругу так, чтобы для некоторой позиции A сумма по любой дуге с левым концом в A лежала бы на отрезке [0, ⌊(n+2)/2⌋−2 ⌊(n+2)/2⌋ ], это очевидно можно сделать. Теперь вспомним, что каджое новое число это на самом деле два старых, и расположим эти старые в порядке положительное- отрицательное. Добавились суммы, получающиеся из старых добавлением одного из первых чисел пары, то есть не более чем единицы. Поскольку все старые суммы лежали на отрезке длины ⌊(n+2)/2⌋−2 ⌊(n+2)/2⌋ , теперь все суммы лежат на отрезке длины 1 + ⌊(n+2)/2⌋−2 ⌊(n+2)/2⌋ , что и требовалось. Пусть n = 2k − 1, тогда сумма модулей наименьших по модулю положительного и отрица- тельного чисел может быть слишком большой только если количество положительных и отри- цательных чисел отличается на единицу. Без ограничения общности пусть положительных k. Каждое положительное число, кроме самого маленького, объединим в пару с отрицательным. Получили набор из k чисел (оставшееся положительное и k −1 сумм в парах, суммы в парах по модулю не больше 2 k −1 ), оставшееся положительное обозначим X, естественно k −2 k > X > k −1 k Мы хотим эти числа расставить по кругу с началом отсчета так, чтобы последним стояло X, а все суммы кроме суммы k − 1 пары лежали на отрезке [− k −2 k −1 X, 0]. Для этого сначала выберем пару, которая встанет k −1-й по номеру: достаточно взять ее меньше либо равной чем − 1 k −1 X, а такая найдется из среднего значения. Затем все остальные пары расставить как угодно, чтобы из сумма не выходила из коридоа – это возможно, потому что модуль чисел маленький. Теперь перейдем от расстановки пар к расстановки исходных чисел, поставив числа в каж- дой паре в порядке отрицательное-положительное. Поскольку до этого все суммы лежали на отрезке [ − k −2 k −1 X, 0], значит и на отрезке [ − k −2 k , 0], теперь они лежат на отрезке [ −1 − k −2 k , 0] – победа. Критерии. A В направлении примера (т.е. доказательства, что C > 2020 1011 ). Пример, показывающий что для меньшего C не работает – ∓ и 13 баллов. Любые меньшие значения C: 0 баллов. B Продвижения в направлении оценки. B0 Любае оценка не сильнее чем |a|+|b| где a – Максимальное из положительных чисел, а b – минимальное (т.е. максимальное по модулю) из отрицательных: +0 баллов. Любой алгоритм расстановки, обеспечивающий лишь что, что сумма на дугах с одним фиксированным концом не больше C: +0 баллов. |