Е. Р. Байсалов, да. ЕлиусизовМатематические олимпиады
 Скачать 2.18 Mb.
|
|
Рис. Пусть ∠CKH = x, ∠MKB = y. По теореме Менелая для треугольника и точек B, L, H имеем или sin ∠SKB KM · sin y · KM · sin(∠SKB − y) KC · sin ∠SKC · KC · sin x KS · sin(∠SKC − x) = Поэтому sin(∠SKB − y) · sin x = sin(∠SKC − x) · sin что можно переписать в следующем виде 2 (cos(∠SKB − x − y) − cos(∠SKB − y + x)) = Решения задач МОШП 2011 153 = 1 2 (cos(∠SKC − y − x) − cos(∠SKC − x + или cos(∠SKB − y + x) = cos(∠SKC − x + y). Из последнего уравнения легко получить, что y. Заметим, что треугольники AKB и BKC подобны и точка является серединой отрезка AB. Тогда из равенства y следует, что прямая KM проходит через середину отрезка Задача. Ответ M = Первое решение. При M = 2 равенство выполняется, когда a = = b = c = 1/3. Докажем, что неравенство выполняется всегда. Во-первых, если в точности одно или три из чисел bc, b − и ab не положительны, то данное неравенство очевидно. Более того, два из этих чисел точно положительны, так как, поскольку, и принадлежат интервалу (0, 1), a − bc > a − c ¾ 0, b − ac > b − c ¾ если считать, что — наименьшее число. Следовательно, мы можем предположить, что все три выражения положительны. Заметим, что+ b) 2 = 1 ( a + b)(1 − c) = 1 a − bc + b − ac ¶ 1 4 1 a − bc + 1 b − Следовательно, суммируя данное неравенство и аналогичные ему по, b, c, получаем+ b) 2 + 1 ( b + c) 2 + 1 ( c + a) 2 ¶ 1 2 1 a − bc + 1 b − ac + 1 c − Заметим, что bc + 1 b − ac + 1 c − ab ( a − bc)(b − ca)(c − ab) = = (a − bc)(b − ca) + (b − ca)(c − ab) + (a − bc)(c − ab) = = ab + bc + ca − a 2 ( b + c) − b 2 ( c + a) − c 2 ( a + b) + abc(a + b + c) = = ab + bc + ca − a 2 (1 − a) − b 2 (1 − b) − c 2 (1 − c) + abc = = ab + bc + ca − a 2 − b 2 − c 2 + a 3 + b 3 + c 3 + abc = = (a + b + c)(ab + bc + ca − a 2 − b 2 − c 2 ) + a 3 + b 3 + c 3 + abc = = 3abc − a 3 − b 3 − c 3 + a 3 + b 3 + c 3 + abc = Следовательно+ b) 2 + 1 ( b + c) 2 + 1 ( c + a) 2 ( a − bc)(b − ca)(c − ab) ¶ ¶ 1 2 1 a − bc + 1 b − ac + 1 c − ab ( a − bc)(b − ca)(c − ab) = 2abc. Решения задач МОШП Второе решение. Сделаем подстановку: tg α 2 = È bc a , tg β 2 = r ac b , tg γ 2 = È ab c , где α, β, γ ∈ (0; π/2). Тогда заметим, что tg α 2 tg β 2 + tg β 2 tg γ 2 + tg γ 2 tg α 2 = Следовательно, β, γ — углы некоторого остроугольного треугольника. Тогда по известному соотношению в треугольнике исходное неравенство перепишется в виде cos α cos β cos γ 1 sin 2 α + 1 sin 2 β + 1 sin 2 γ = = (p 2 − (2R + r) 2 ) h 2 𝑎 + h 2 𝑏 + h 2 𝑐 4 S 2 ¶ 2 r 2 · p 2 4 S 2 = 1 где — полупериметр, S — площадь, h 𝑎 , h 𝑏 , h 𝑐 — высоты, r — радиусы описанной и вписанной окружностей треугольника 4. Задача 4 . Первое решение. Любую функцию от двух переменных вида F(x, y) = ax 2 + bxy + с целыми коэффициентами, c назовём квадратичной формой или просто формой. Две формы и назовём эквивалентными, если для любых целых m, n существуют такие целые, что, n) = G(m 0 , n 0 ), и наоборот для любых целых, l существуют такие целые k 0 , l 0 , что, l) = Лемма 1. Любая квадратичная форма F(x, y) = ax 2 + bxy + с дискриминантом = b 2 − 4ac = −3 и a > 0 эквивалентна форме+ xy + Доказательство. Пусть G(x, y) = Ax 2 + Bxy + Cy 2 — квадратичная форма, эквивалентная, с дискриминантом = B 2 − 4AC = и минимальной суммой + |B| + |C|. Легко заметить, что A > и 0. Докажем, что |B| ¶ min{A, Предположим противное пусть > A. Выберем целые q, r таким образом, что < A, B = 2Aq + r, и рассмотрим следующую замену переменных x = X − qY, y = Тогда, y) = Ax 2 + Bxy + Cy 2 = αX 2 + β XY + γY 2 , Решения задач МОШП 2011 где = A, β = B − 2Aq и γ = Aq 2 − Bq + c. Легко проверить, что = β 2 − 4αγ = B 2 − 4AC = −3. Так как |β| = |r| ¶ A < |B|, получаем, что 0 < γ < C. Следовательно, |A| + |B| + |C| > |α| + |β| + |γ|, что противоречит минимальности суммы + |B| + Тогда ¶ A, |B| ¶ C и B 2 − 4AC = −3. Следовательно, B 2 ¶ и 4AC = −3 ¶ −3AC, или AC ¶ 1. Это означает, что A = C = 1 = Если 1, то мы получим требуемое утверждение. Если B = то произведём замену переменных x, y → − y для завершения доказательства. Замечание. Замена переменных ( 1 ) обратима x + q y, Y = что даёт нам эквивалентную форму. Лемма 2. Пусть p ≡ 1 (mod 3). Тогда существует такое нечётное целое число b ∈ {1, 2, . . . , p − 1} def = Z ∗ 𝑝 , что −3 (mod Доказательство. По малой теореме Ферма 1 (mod p) для любых ∈ Z ∗ 𝑝 . Многочлен 1 имеет не более (p − 1)/3 корней по модулю. Тогда для некоторого ∈ имеем 6≡ 1 (mod Пусть ∈ таково, что ≡ α (𝑝 −1)/3 (mod p). Тогда 6= 1 и 1 = (β − 1)(β 2 + β + 1) ≡ 0 (mod Следовательно +1≡0 (mod p). Поэтому (2β +1) 2 ≡−3 (mod Если 2 β +1< p, то возьмём b=2β +1. Иначе, если 2β +1> p, возьмём b = 2p − 2β − Следствие. Если p ≡1 (mod 3), то существует такое целое что b 2 + 3 делится на Теперь можно доказать, что любое простое 1 (mod 3) может быть представлено в виде+ mn + Пусть 1 (mod 3). В силу следствия существуют целые такие и, что b 2 +3=4pc. Для квадратичной формы F(x, y)= px 2 +bxy имеем, 0) = p и ∆ = b 2 − 4pc = −3. Тогда по лемме 1 форма эквивалентна форме+ xy + y 2 , те+ для некоторых целых, Замечание. Легко доказать, что если простое число p представимо в виде+ mn + n 2 , то 3 или p ≡ 1 (mod Второе решение. Назовём целое число хорошим, если оно может быть представлено в виде+ при некоторых целых, n. Для Решения задач МОШП начала докажем, что любое простое число 1 (mod 3) является хорошим. Лемма 3. Если хорошее число N чётно, то оно делится на 4 и целое число N /4 также является хорошим. Доказательство. Пусть N = m 2 + для некоторых целых, одинаковой чётности. Утверждение леммы очевидно, если, n чёт- ны. Предположим, что, n нечётны. Тогда m + n или m − n делится на 4. Используем тождество+ 3n 2 ) = (m ± 3n) 2 + 3(m ∓ Подставив (m ± 3n)/4, b = (m ∓ n)/4 с соответствующим выбором знаков, получим = a 2 + для некоторых целых, b, что и требовалось доказать. Лемма 4. Если хорошее число N делится на хорошее простое число p, то целое число N /p также является хорошим. Доказательство. Пусть N = и при некоторых целых, n, q, r. Используя тождество rm)(nq + rm) = n 2 ( q 2 + 3r 2 ) − r 2 ( m 2 + 3n 2 ) = n 2 p − и простоту числа, заметим, что nq − rm или nq + rm делятся на Используя тождество (q 2 + 3r 2 )( m 2 + 3n 2 ) = (mq ± 3nr) 2 + 3(nq ∓ подставим (mq ± 3nr)/p, b = (nq ∓ rm)/p с соответствующим выбором знаков и получим = a 2 + при некоторых целых, что и требовалось доказать. Лемма 5. Если нечётное простое число p делит хорошее число m 2 + 3 и не делит целое число m, то p ≡ 1 (mod Доказательство. Очевидно, что p > 3. Предположим, что m ∈ Для = (m−1)/2 ∈ имеем +1 ≡ 0 (mod p). Нетрудно понять, что β 6= 1, β 2 6≡ 1 (mod p) и β 3 ≡ 1 (mod p). Тогда по малой теореме Ферма p − 1 ≡ 0 (mod 3), что и требовалось доказать. Пусть теперь — простое и p ≡ 1 (mod 3). Последствию из леммы существует такое целое число Z ∗ 𝑝 , что+ 3 делится на Число+ 3 является хорошими. Тогда все простые делители числа (b 2 + 3)/(4p) меньше, чем p. Если p не является Решения задач МОШП 2012 хорошим, то по лемме 3 и лемме 4 некоторые нечётные простые делители числа, в частности q, не являются хорошими. Тогда по лемме имеем 1 (mod 3). Теперь методом бесконечного спуска мы можем доказать, что является хорошим. Лемма 6. Любое хорошее число может быть представлено в виде+ mn + при некоторых целых m, Доказательство. Пусть N = x 2 + для некоторых целых, При x − y, n = 2y имеем+ mn + n 2 = m(m + n) + n 2 = (x − y)(x + y) + (2y) 2 = x 2 + 3y 2 = что и требовалось доказать. Следствие. Любое простое число p ≡1 (mod 3) может быть представлено в виде m 2 + mn + при некоторых целых m, Замечание 1. Если число представимо в виде m 2 + mn + при некоторых целых, n, то оно имеет представление того же типа при неотрицательных целых, n. Действительно, пусть N = x 2 + + xy + при некоторых целых, y. Можем предположить, что 0. Если sign(x) = sign( y), то подставим m = |x|, n = | y|. Пусть 0 > y. Можем предположить, что x ¾ |y| (если это не так, то заменим) на ( − y, −x)). При a = x + y, b =− y имеем a ¾0, b >0 и+ ab + b 2 = a(a + b) + b 2 = (x + y)x + y 2 = x 2 + xy + y 2 = Замечание 2. Используя тот же метод, легко показать, что если число представимо в виде+ mn + при некоторых целых m и n, то оно является хорошим числом. Замечание 3. Если M = a 2 + ab + и c 2 + cd + d 2 , то X 2 + + XY + и ac − bd, Y = ad + bc + я олимпиада, 2012 год Задача_1'>Задача 1 . Заметим, что трапеция ABCD равнобокая, поскольку = 180 ◦ − ∠C = Пусть — середина стороны BC. Легко видеть, что M — основание перпендикуляра, опущенного из на BC см. рис. Имеем = ∠EBC = ∠ECF = 1 откуда = ∆FEC, а значит, BC = 2CM = 2CF. Решения задач МОШП Рис. Задача. Ответ существует 90 различных допустимых таблиц. Приведём решение, основанное на прямом подсчёте. Пусть две единицы первой строки допустимой таблицы стоят в столбцах и Покажем, что имеется ровно 15 допустимых таблиц с единицами в столбцах. Тогда понятно, что общее количество допустимых таблиц равно 15 · C 2 4 = 15 · 6 = 90, поскольку любые две пары столбцов равноправны. Без ограничения общности пусть a, y = b. Если найдётся ещё строка, единицы которой стоят в столбцах и b, то месторасположение остальных единиц таблицы однозначно определяется. Значит, таких таблиц (назовём их блочными) существует ровно Осталось показать, что существует ровно 12 неблочных таблиц с единицами в клетках, b1. Для некоторых i, j, 2 ¶ i ¶ 4, 2 ¶ j ¶ в клетки, bj должны быть вписаны единицы. Пусть i 6= j. Мы можем выбрать такие, j 6 способами, так как 3 · 2 = 6. Зафиксируем такую пару, j и покажем, что для них существуют ровно две возможности для расположения остальных единиц. Действительно, осталось единственное, не совпадающее с 1, i, j. Понятно, что в клетках ck и стоят единицы. А две оставшиеся единицы занимают либо клетки ci и dj, либо клетки cj и di, те. для них остались ровно две возможности. Итак, неблочных допустимых таблиц с единицами в клетках, имеется ровно 12 штук. Задача 3 . Ответ 2 𝑚 +1 , где — наибольшая степень числа на которую делится n. Пусть n = 2 𝑚 k и k — нечётное число. Заметим, что целые числа 2𝑛 и C 2𝑖 2𝑛 −1 связаны соотношением 2𝑛 = 2 n 2 i + 1 · C 2𝑖 2𝑛 −1 Решения задач МОШП 2012 Поскольку 2 i + 1 — нечётное число, каждое из чисел C 2𝑖 +1 делится на 2 𝑚 +1 . Докажем, что искомый НОД множества чисел равен Для этого достаточно доказать, что для любого нечётного простого p одно из чисел данного множества не делится на p. Пусть n = p 𝑠 t, где t не делится на p. Докажем, что число не делится на. Действительно (2n − 1) · . . . · (2n − p 𝑠 + 1) p 𝑠 · (p 𝑠 − 1) · . . . · 1 = 2 n p 𝑠 · 2 n − 1 p 𝑠 − 1 · . . . · 2 n − p 𝑠 + 1 и каждая дробь вида (2 n − j)/(p 𝑠 − j) равна несократимой дроби с числителем, не делящимся на. Значит, (целое) число не делится на, что и требовалось доказать. Задача 4 . Можем предполагать, что n > 1. Из биномиального разложения (см. теорему нас) получаем+ x) 𝑛 ¾ 1 + nx + n(n − 1) 2 x 2 > 1 + n(n − для любого положительного x. Пусть 𝑛 p n = 1 + x. Тогда (1 + x) 𝑛 > 1 + n(n − а значит 1) n(n − Как следствие, для любого целого положительного имеем 1 +С помощью последней оценки получаем+ . . . + 𝑛 p n < n + p 2 1 p 1 + 1 p 2 + 1 p 3 + . . . + 1 p n . (1) C помощью неравенства+ 1 < 2 p n + 1 + p n = 2( p n + 1 индукцией легко доказать следующее неравенство+ . . . + 1 p n < Из неравенств (1) и (2) вытекает, что+ . . . + 𝑛 p n < n + 2 p 2 p n, Решения задач МОШП или+ . . . + 𝑛 p n n < 1 +что и требовалось доказать. 12-я олимпиада, 2013 год Задача 1 . Ответ условие выполнено для всех натуральных чисел и n, для которых числа m /(m, n) и n/(m, n) являются нечёт- ными (или наибольшие степени числа 2 в разложениях чисел и n равны). Пусть d = (m, n). Из условия задачи имеем+ 1 | (2 𝑚 + 1, 2 𝑛 + Следовательно (2 𝑑 ) 𝑚 /𝑑 ≡ (−1) 𝑚 /𝑑 ≡ −1 (mod 2 𝑑 + Это означает, что и n/d нечётные. Теперь докажем, что это условие достаточно. Далее будем пользоваться легко доказуемыми леммами. |