Е. Р. Байсалов, да. ЕлиусизовМатематические олимпиады
 Скачать 2.18 Mb.
|
|
Задача 3 . Предположим, что одна из сторон треугольника имеет длину. Тогда его можно разрезать на равных треугольников, которые подобны исходному, и стороны, соответствующие стороне длины, имеют длину, равную 1. Решения задач АТМО Так как число 2005 представимо в виде 5 · 401, где 5 и 401 простые числа и оба имеют вид 4 k + 1, оно может быть представлено в виде суммы двух целых квадратов. Действительно 5 · 401 = (2 2 + 1)(20 2 + 1) = 40 2 + 20 2 + 2 2 + 1 = = (40 − 1) 2 + 2 · 40 + 20 2 + 2 2 = 39 2 + 22 Пусть — прямоугольный треугольник с катетами AB и BC с длинами и 22 соответственно. Проведём высоту, которая делит на два подобных треугольника. Разделим треугольник ABK на равных треугольников, как описано выше, и на 22 равных треугольников. Так как треугольник подобен треугольнику все 2005 треугольников будут равны. Задача 4 . Ответ n 2 + c 2 − nc − Максимальное число домов, которые можно спасти, равняется+ c 2 − nc − c. Это может быть достигнуто при следующем порядке защиты, (2, c + 1); (3, c − 1), (3, c + 2); (4, c − 2), (4, c + 3); . . . . . . (c + 1, 1), (c + 1, 2c); (c + 1, 2c + 1), . . . , (c + 1, Согласно стратегии имеются столбца (номера столбцов, c +1), при которых n−1 домов спасены столбца (номера столбцов 1, c + 2), при которых n − 2 домов спасены столбца (номера столбцов 1, 2 c), при которых n − c домов спасены 2c столбцов (номера столбцов n − 2c + 1, . . . , n), при которых n − домов спасены. Сложив соответствующие количества, получим 1) + (n − 2) + . . . + (n − c)] + (n − 2c)(n − c) = n 2 + c 2 − cn − c. Назовём дом, индексированный парой ( i, j), находящимся на уровне если − 1| + | j − c| = t. Пусть d(t) — количество домов на уровнена которых установлена защита к моменту времени, а p(t) — количество домов, находящихся на уровне больше чем, на которых установлена защита к моменту времени. Очевидно, что) ¶ t и p(t + 1) + d(t + 1) ¶ p(t) + 1. Решения задач АТМО 2005 Пусть) — количество домов на уровне t, которые не охватил пожар. Докажем, что) ¶ t − p(t) ¶ t для 1 ¶ t ¶ n − 1, используя индукцию. Это очевидно при 1. Предположим, что неравенство верно для k. Объединение соседей любых k − p(k) + 1 домов на уровне+ 1 содержит по крайней мере, k − p(k) + 1 вершин на уровне k. Так как) ¶ k − p(k), один из этих домов на уровне k горит. Поэтому лишь p(k) домов на уровне k + 1 не имеют охваченных пожаром соседей. Следовательно+ 1) ¶ k − p(k) + d(k + 1) = = (k + 1) − (p(k) + 1 − d(k + 1)) ¶ (k + 1) − p(k + Теперь докажем, что представленная выше стратегия является оптимальной. Так как) ¶ C 2 𝑛 = n(n + максимальное количество домов на уровнях, меньше или равных 1, которые можно спасти согласно любой стратегии, не больше числа+ 1)/2, которое реализовано стратегией, указанной выше. Более того, на уровнях, больших 1, поданной стратегии спасён каждый дом. Ниже приведём пример, когда 11 и c = Рис. Рис. На рис. 5 дома, помеченные значком , сгорели. Дома, помеченные значком, заблокированы, следовательно, дома ниже их спасены. Задача 5 . Ответ: MN BC = r 1 − 2 r R Пусть ω, O и I — описанная окружность и центры описанной и вписанной окружностей треугольника соответственно (см. рис Решения задач АТМО Пусть — точка пересечения прямой BI и окружности (D 6= Тогда — середина дуги AC. Следовательно, OD ⊥ CN и OD = Для начала покажем, что треугольники и IOD подобны. Так как BM, прямая BI биссектриса ∠MBC) перпендикулярна прямой. Так как OD ⊥ CN и ID ⊥ MC, получаем, что = Пусть ∠ABC = 2β. В треугольнике BCM справедливо равенство 2 sin Так как ∠DIC = ∠DCI, получаем, что ID = CD = AD. Пусть E — точка пересечения прямой и окружности (E 6= D). Тогда DE — диаметр окружности и ∠DEC = ∠DBC = β. Таким образом sin β R = 2 sin Объединив уравнения (1), (2) и (3), можно увидеть, что треугольники и IOD подобны. Отсюда следует, что MN BC = MN NC = IO OD = IO R Известная формула Эйлера утверждает, что R 2 − 2Rr. Таким образом, MN BC = r 1 − 2 r R Задача_1'>18-я олимпиада, 2006 год Задача 1 . Ответ f (n) = ( если чётно, 1 если нечётно. Предположим, что чётно. Если a 𝑖 = 1/2 для всех i, то сумма+ a 2 + . . . + является целым числом. Так как 1/2| = 0 для всех, получаем, что f (n) = 0 при всех чётных Теперь предположим, что нечётно. Допустим, что 1/2| < < 1/(2n) для всех i, 1 ¶ i ¶ n. Так как сумма является целым числом, получаем, что 2 ¶ 𝑛 X 𝑖 =1 a 𝑖 − n 2 ¶ 𝑛 X 𝑖 =1 a 𝑖 − 1 2 < 1 2 n · n = 1 2 , Решения задач АТМО 2006 57 — противоречие. Следовательно 1/2| ¾ 1/(2n) при некотором С другой стороны, при 2m + 1 положим a 𝑖 = m/(2m + 1) для всех и тогда получим m. При этом 2 = 1 2 − m 2 m + 1 = 1 2(2 m + 1) = 1 для всех, те) является искомым значением при любом нечётном n. Задача 2 . Докажем утверждение задачи методом математической индукции, при этом будем использовать тождество τ + Если 1, то 1 = Предположим, что 1 можно представить в виде конечной суммы различных целых степеней числа, скажем 1 где {0, 1} и n ¾ 2. Запишем соотношение (1) в виде 1 = a 𝑘 . . . a 1 a 0 a −1 a −2 . . . Например, 1 = 1.0 = 0.11 = 0.1011 = Для начала докажем, что в правой части равенства (2) всегда можно считать, что две единицы не стоят подряд. В самом деле, возь- мм крайнюю левую пару стоящих рядом единиц. Так как левее этих единиц либо ничего нет, либо стоит 0, мы можем заменить 11 либо, соответственно, 011 на 100, используя тождество+ τ 𝑖 = τ 𝑖 +2 . Повторяя эту операцию, мы получим представление, в котором парных единиц нет 1 где {0, 1} и b 𝑖 b 𝑖 +1 = 0 для всех Если в формуле (3) коэффициент b 0 равен 0, то мы просто прибавим к обеим частям равенства (3) и получим необходимое представление для числа n. Предположим, что в нулевой позиции представления (3) присутствует, те. Если справа от него стоят два нуля, те, то мы можем заменить 1.00 на 0.11, так как τ −1 + τ −2 . После этого мы можем получить необходимое тождество, поскольку в нулевой позиции присутствует 0. Таким образом, можно считать, что 1 = . . . 1.010 . . . Решения задач АТМО Аналогичным образом, если мы имеем представление 1 = . . . 10100 . . . то его можно преобразовать к виду 1 = . . . 1.0100 . . . = . . . 1.0011 . . . = . . . 0.1111 . . и получить 0 в нулевой позиции. Нам остаётся рассмотреть случай 1 = . . . 1.01010 . . . Но поскольку количество единиц конечно, в итоге мы получим комбинацию в конце, те. Тогда мы можем сдвинуть все единицы вправо и получить 0 в нулевой позиции, те. Прибавив к этому тождеству 1 = τ 0 , получим необходимое представление для n. Задача 3 . Заметим, что r =C 𝑝 𝑝 2 − p. Следовательно, нам достаточно доказать, что 1)(p 2 − 2) . . . (p 2 − (p − 1)) − (p − 1)! ≡ 0 (mod Теперь введём такую функцию (x), что (x) =(x −1)(x −2) . . . (x −(p−1))= x 𝑝 −1 +s 𝑝 −2 x 𝑝 −2 +. . .+s 1 x +s 0 . (Тогда сравнение (1) эквивалентно сравнению (p 2 ) − s 0 ≡ 0 (mod Следовательно, достаточно доказать, что 0 (mod p 4 ) или Поскольку 1 (mod p) для всех a, 1 ¶ a ¶ p − 1, мы имеем разложение разложить 1 ≡ (x − 1)(x − 2) . . . (x − (p − 1)) (mod Сравнивая коэффициенты левой части сравнения (3) с коэффициентами правой части равенства (2), получим, что. p для всех i, 1 ¶ i ¶ p − 2 и s 0 ≡ −1 (mod p). С другой стороны, подставляя вместо в равенство (2), получим (p) = (p − 1)! = s 0 = p 𝑝 −1 + s 𝑝 −2 p 𝑝 −2 + . . . + s 1 p + откуда следует, что+ s 𝑝 −2 p 𝑝 −2 + . . . + s 2 p 2 = Так как ¾ 5 и s 2 . p, получаем, что s 1 ≡ 0 (mod p 2 ), что и требовалось доказать Решения задач АТМО 2006 Рис. Задача. Пусть S — точка касания окружностей O и O 1 , а точка пересечения окружности и прямой SP, отличная от S (см. рис. 7 ). Пусть — точка касания l и O 1 , а — середина отрезка Так как ∠TBP =∠ASP, треугольник TBP подобен треугольнику Следовательно : PB = PA : PS. Так как прямая l касается в точке, получаем, что = 90 ◦ − ∠XSP = 90 ◦ − ∠APM = Откуда следует, что треугольник подобен треугольнику SPX . Поэтому и XP : PS = MA : AP. Из этого и из предыдущего наблюдения следует, что Пусть точка пересечения окружности и серединного перпендикуляра к хорде, так что A и лежат по одну сторону от прямой, а N — точка пересечения прямых A 0 Q и CT . Так как = ∠TCB = ∠TCA = ∠TBA = и XAP 2 = ∠PAM = треугольник подобен треугольнику TBP и треугольник CA 0 Q подобен треугольнику . Следовательно, QN : QC = PT : PB и QC :QA 0 = = XS : XP. Тогда из соотношения (1) следует равенство QA 0 = 2QN. Решения задач АТМО Из этого вытекает, что точка является серединой отрезка QA 0 . Пусть окружность O 2 касается отрезка в точке Y. Так как ACN = ∠ ACT = ∠BCT = и CQ, получаем, что треугольники YCN и QCN равны, следовательно и NY = NQ = NA 0 . Тогда является центром окружности, что завершает доказательство. Задача 5 . Ответ Пусть — искомое множество n клоунов. Пронумеруем имеющиеся цвета числами 1, 2, 3, . . . , 12. Для каждого цвета i = 1, 2, . . . , обозначим через F 𝑖 множество клоунов, которые используют цвет i. Для каждого подмножества множества, 2, . . . , 12} обозначим через множество клоунов, которые используют в точности все цвета из. Если S 6= S 0 , то E 𝑆 0 = ∅, и мы имеем = |C| = где пробегает все подмножества множества, 2, . . . , 12}. Для каждого включение E 𝑆 ⊆ выполняется тогда и только тогда, когда следовательно = X 𝑖 ∈ По условию задачи мы знаем, что ¶ 20 и если E 𝑆 6= ∅, то |S| ¾ Из этого следует, что 12 ¾ 12 X 𝑖 =1 |F 𝑖 | = 12 X 𝑖 =1 X 𝑖 ∈ 𝑆 |E 𝑆 | ¾ 5 X 𝑆 |E 𝑆 | = Таким образом ¶ Теперь определим последовательность цветов {c 𝑖 } 52 𝑖 =1 следующим способом 2 3 4 | 5 6 7 8 | 9 10 11 12 | 4 1 2 3 | 8 5 6 7 | 12 9 10 11 | 3 4 1 2 | 7 8 5 6 | 11 12 9 10 | 2 3 4 1 | 6 7 8 5 | 10 11 12 9 | 1 2 3 Первая строка состоит из цветов. . . , в порядке возрастания, вторая строка состоит из цветов. . . , в указанном порядке, третья строка состоит из цветов. . . , в указанном порядке Решения задач АТМО 2007 наконец, четвёртая строка состоит из цветов. . . , в указанном порядке. Для каждого, 1 ¶ j ¶ 48, назначим j-му клоуну цвета c 𝑗 , c 𝑗 +1 , c 𝑗 +2 , c 𝑗 +3 , c 𝑗 +4 . Нетрудно проверить, что данное распределение цветов удовлетворяет всем условиям задачи. Таким образом, 48 является наибольшим значением для n. 19-я олимпиада, 2007 год Задача 1 . Не теряя общности, можем считать, что S содержит только натуральные числа (при этом, возможно, с двойными повторами. Пусть {2 𝑎 𝑖 3 𝑏 𝑖 | a 𝑖 , b 𝑖 ∈ Z, a 𝑖 , b 𝑖 ¾ 0, 1 ¶ i ¶ Достаточно доказать, что существуют такие, 1 ¶ i 1 , i 2 , i 3 ¶ что+ a 𝑖 2 + a 𝑖 3 ≡ b 𝑖 1 + b 𝑖 2 + b 𝑖 3 ≡ 0 (mod Для произвольного 2 𝑎 3 𝑏 ∈ S будем называть пару (a (mod 3), b (mod 3)) типом числа n. Тогда существует 9 различных типов, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, Пусть, j) обозначает количество целых чисел в S типа (i, j). Произведение трёх чисел является точным кубом, если выполнится хотя бы одно из четырёх условий, j) ¾ 3 при некоторых i, j; (2) N(i, 0)N(i, 1)N(i, 2) 6= 0 при некотором i = 0, 1, 2; (3) N(0, j)N(1, j)N(2, j) 6= 0 при некотором j = 0, 1, 2; (4) N(i 1 , j 1 ) N(i 2 , j 2 ) N(i 3 , j 3 ) 6=0, где {i 1 , i 2 , i 3 }={ j 1 , j 2 , j 3 }={0, 1, Допустим, что ни одно из условий (1)–(3) не выполняется. Так как, j) ¶ 2 для всех типов (i, j), существует не менее пяти ненулевых чисел, j). Более того, среди ненулевых чисел N(i, j) никакие три не имеют одинаковые значения и никакие три не имеют одинаковые значения. Используя данные факты, нетрудно доказать, что условие) должно выполняться. (Например, если расположить ненулевые числа, j) соответственно в (i, е позиции таблицы 3 × 3, строки и столбцы которой пронумерованы числами 0, 1 и 2, то всегда можно найти три ячейки с различными строками и столбцами, в которых расположены ненулевые числа, j). Откуда следует условие (Задача. Пусть D — точка пересечения прямых AH и BC, а K точка пересечения описанной окружности треугольника и пря- Решения задач АТМО Рис. мой см. рис. Прямая, перпендикулярная прямой и проходящая через точку, пересекает прямую BC и меньшую дугу в точках и N соответственно. Тогда получим = 180 ◦ − (∠IBC + ∠ICB) = = 180 ◦ − 1 2 (∠ABC + ∠ACB) = 90 ◦ + 1 2 ∠BAC = а также ∠BNC = 180 ◦ − ∠BAC = 120 ◦ = ∠BIC. Так как IN ⊥ BC, получаем, что четырёхугольник BICN — дельтоид, следовательно, IE = Поскольку — точка пересечения высот треугольника ABC, получаем, что DK. Так как ED ⊥ IN и ED ⊥ HK, получаем, что является равнобокой трапецией с боковыми сторонами Следовательно, ∠AHI = 180 ◦ − ∠IHK = 180 ◦ − ∠AKN = Так как EN и BE ⊥ IN, треугольники IBE и NBE равны. Следовательно, и тогда ∠ AHI = = ∠ABN = 3 2 ∠ Задача. Ответ 1)(n − 2) 2 Назовём множество кругов, удовлетворяющее данному условию, n-конфигурацией. Для произвольной конфигурации {C 1 , C 2 , . . . , пусть {(i, j) | целиком содержит C 𝑗 } (множество пар ( i, j) для которых круг целиком содержит круг C 𝑗 ). Тогда весом n-конфигурации C является количество элементов множества Решения задач АТМО 2007 Докажем следующие утверждения) существует n-конфигурация C, при которой = ( n − 1)(n − 2) 2 ; (ii) |S 𝐶 | ¶ ( n − 1)(n − для произвольной n-конфигурации Выберем в качестве C 1 произвольный круг. При любом, 2 ¶ i < < n − 1 выберем C 𝑖 внутри C 𝑖 −1 так, чтобы окружность, являющейся границей круга, содержала центр круга. Наконец, выберем C 𝑛 так, чтобы его центр лежал на окружности, являющейся границей круга, а ограничивающая его окружность содержала центр круга. При этом получим множество {(i, j) | 1 ¶ i < j ¶ n − размера ( n − 1)(n − 2)/2, что доказывает утверждение (i). Для n-конфигурации C множество должно удовлетворять следующим условиям) ( i, i) /∈ S 𝐶 ; (2) ( i + 1, i) /∈ S 𝐶 , (1, n) /∈ S 𝐶 ; (3) если ( i, j), ( j, k) ∈ S 𝐶 , то ( i, k) ∈ S 𝐶 ; (4) если ( i, j) ∈ S 𝐶 , то ( j, i) /∈ Теперь докажем, что если множество упорядоченных пар натуральных чисел от 1 до удовлетворяет условиям 1–4, то оно не может иметь более ( n −1)(n−2)/2 элементов. Предположим обратное пусть существует множество, удовлетворяющее условиям 1–4, имеющее более ( n − 1)(n − 2)/2 элементов. Пусть n — наименьшее натуральное число, при котором такое множество существует. Заметим, что должно содержать ( i, i + 1) для некоторого i, 1 ¶ i < n, или (n, 1), так как в противном случае должно содержать не более n = n(n − 3) 2 < ( n − 1)(n − элементов. Без ограничения общности можно считать, что ( n, 1) ∈ Тогда (1, n − 1) / ∈ G, так как в противном случае из условия 3 следует, что ( n, n − 1) ∈ G, а это противоречит условию 2. Теперь рассмотрим множество {(i, j) ∈ G | 1 ¶ i < j ¶ n − которое удовлетворяет условиям 1–4 для ( n − 1)-конфигурации. Покажем, что − G 0 | ¶ n − Предположим, что − G 0 | > n − 2, тогда |G − G 0 | = n − 1 и для каждого 1 ¶ i ¶ n − 1 либо (i, n), либо (n, i) должно принадлежать Мы также знаем, что ( n, 1) ∈ G итак как (n, n − 1) / ∈ G). Решения задач АТМО Отсюда следует, что ( n, n − 2) / ∈ G и (n − 2, n) ∈ G. Продолжая данный процесс, получим, что (1, n) ∈ G, те. придём к противоречию. Так как − G 0 | ¶ n − 2, получаем, что > ( n − 1)(n − 2) 2 − (n − 2) = ( n − 2)(n − Это, однако, противоречит условию минимальности и, следовательно, доказывает утверждение (Задача. Для начала заметим, что+ yz p2x 2 ( y + z) = x 2 − x( y + z) + yz p2x 2 ( y + z) + x( y + z) p2x 2 ( y + z) = = ( x − y)(x − z) p2x 2 ( y + z) + È y + z 2 ¾ ( x − y)(x − z) p2x 2 ( y + Аналогично получим, что+ zx p2 y 2 ( z + x) ¾ ( y − z)( y − x) p2 y 2 ( z + x) + p z + p x 2 , (2) z 2 + xy p2z 2 ( x + y) ¾ ( z − x)(z − y) p2z 2 ( x + y) + p x + Сложим неравенства (1)–(3): x 2 + yz p2x 2 ( y + z) + y 2 + zx p2 y 2 ( z + x) + z 2 + xy p2z 2 ( x + y) ¾ ¾ ( x − y)(x − z) p2x 2 ( y + z) + ( y − z)( y − x) p2 y 2 ( z + x) + ( z − x)(z − y) p2z 2 ( x + y) + p x + p y + p z = = ( x − y)(x − z) p2x 2 ( y + z) + ( y − z)( y − x) p2 y 2 ( z + x) + ( z − x)(z − y) p2z 2 ( x + y) + Следовательно, достаточно доказать, что y)(x − z) p2x 2 ( y + z) + ( y − z)( y − x) p2 y 2 ( z + x) + ( z − x)(z − y) p2z 2 ( x + y) ¾ Теперь предположим, не теряя общности, что ¾ y ¾ z. Тогда имеем y)(x − z) p2x 2 ( y + z) ¾ и z)( y − x) p2 y 2 ( z + x) + ( z − x)(z − y) p2z 2 ( x + y) = ( y − z)(x − z) p2z 2 ( x + y) − ( y − z)(x − y) p2 y 2 ( z + x) ¾ Решения задач АТМО 2007 65 ¾ ( y − z)(x − y) p2z 2 ( x + y) − ( y − z)(x − y) p2 y 2 ( z + x) = = (y − z)(x − y) 1 p2z 2 ( x + y) − 1 p2 y 2 ( z + Последнее выражение неотрицательно, так как+ x) = y 2 z + y 2 x ¾ yz 2 + z 2 x = z 2 ( x + что завершает доказательство. |