Е. Р. Байсалов, да. ЕлиусизовМатематические олимпиады

• Название: Е. Р. Байсалов, да. ЕлиусизовМатематические олимпиады
• Дата: 07.03.2023
• Размер: 2.18 Mb.
• Имя файла: 67778_cc52cacd3756a57b6cf807ed1a3bdeb3 2.pdf
• Тип: Книга; #973406
• страница: 17 из 25

Доказательство. Пусть x
= p
𝑎
1 1
. . . p
𝑎
𝑡
𝑡
— каноническое разложение числа на простые сомножители. Имеем a
= НОД(a
1
,
. . . , a
𝑡
),
a
𝑗
= при 0 ¶ j ¶ t и y = p
𝑏
1 1
. . . p
𝑏
𝑡
𝑡
. Поэтому тогда и только тогда, когда и m = y
𝑎
/𝑛
. Тогда оба множества имеют) − элементов, где) обозначает количество натуральных делителей числа. Таким образом, утверждение доказано.
Следовательно,
X
𝑘
∈ 𝐴
X
𝑖¾1 1
k
𝑖
=
X
𝑚¾2
X
𝑛¾2 1
m
𝑛
=
X
𝑚¾2 1
/m
2 1
− 1/m
=
X
𝑚¾2 1
m(m
− Но нетрудно понять, что 1
m(m
− 1)
=
𝑙
X
𝑚
=2
€
1
m
− 1
−
1
m
Š = lim
𝑙
→
Ì
€
1
−
1
l
Š = я олимпиада, 2004 год
Задача
1
. Ответ f (x)
= ax
2
+ bx для произвольных a, b ∈ Для произвольных и b функция f (x)
= ax
2
+ bx удовлетворяет условию задачи. Покажем, что других функций не существует

Решения задач МОШП 2004 Пусть удовлетворяет условию задачи. Положим (1)
− f (−1)
2
,
b
=
f (1)
+ f (−1)
2
,
g(x)
= f (x) − ax − Тогда удовлетворяет условию задачи и g(1)
= g(−1) = Теперь покажем, что 0. Подставив 1 вместо y в тождество+ y)(g(x) − g(y)) = (x − y)g(x + получим+ 1)g(x) = (x − 1)g(x + а подставляя вместо y и x + 1 вместо x, получим+ 1) = (x + Но тогда+ 1)g(x) = x(x − 1)g(x + 1) = (x + 2)(x − при всех действительных. Следовательно, g(x)
≡ 0 при всех действительных. Ответ p
= 2, 5, Перебрав все целые числа, |n| ¶ 3, найдём решения 1 2
+ 1 2
,
5
= 1 2
+ 2 2
,
13
= (−3)
2
+ (Покажем, что других простых чисел, удовлетворяющих условиям,
не существует.
По условию задачи m
2
+ n
2
, те Так как+ n
3
− 4 = (m + n)
3
− 3mn(m + n) − 4 =
−(m + n)
3
+ 3p(m + n) − 8 из второго условия задачи имеем (m + n)
3
+ 8. Следовательно m + n + 2 или p | (m + n)
2
− 2(m + n) + Положив 2, рассмотрим каждый случай отдельно.
Случай 1: p
| m + n + 2. В этом случае получаем неравенство+ n
2
¶ |m + n + 2|. Если сумма m + n + 2 неотрицательна, то+ n
2
¶ m + n + 2 ⇔ (2m − 1)
2
+ (2n − 1)
2
¶ 10.

Решения задач МОШП Тогда возможны варианты ¶ m, n ¶ 2, которые мы рассмотрели вначале. Если же сумма+ n + 2 отрицательна, то+ n
2
¶ −(m + n + 2) ⇔ (2m + 1)
2
+ (2n + 1)
2
¶ Очевидно, последнее неравенство не имеет решений.
Случай 2: p
|(m + n)
2
−2(m + n)+4. В этом случае p | mn − m − n Поэтому |mn − m − n + 2|. Также как ив первом случае, если подмодульное выражение неотрицательно, тот. е ¶ m, n ¶ 1. Этот случай также рассмотрели вначале. Если же подмодульное выражение отрицательно, то+ n
2
¶ −(mn − m − n + 2) ⇔ (2m + n − 1)
2
+ 3
€
n
−
1 3
Š
2
¶ −
20 чего не может быть.
Задача
3
. Введём обозначения BC
= a, AC = b, AB = c и ∠CAB = α,
∠ ABC = β , ∠BCA = γ. Пусть D — точка пересечения прямых BL и Заметим, что равнобедренный (см. рис. Также имеем = ∠ APK − ∠ ABK =
π − α
2
−
β
2
=
α + β + γ − α − γ
2
=
γ
2
=
∠ Рис. 36

Решения задач МОШП 2004 Так как ∠IKL = ∠BKL = ∠ACB/2 = ∠ACI, точки I, K, Q и C лежат на одной окружности, следовательно, ∠IKC = ∠IQC = π/2. Аналогично = Следовательно, точки, L, K и C лежат на одной окружности,
так же как точки, L, D и K. В частности, BC является диаметром описанной окружности треугольника, а ID является диаметром описанной окружности треугольника
ILK.
Используя теорему синусов в, получим ∠LDK
=
LK
cos а из получим a =
LK
sin ∠LCK
. Следовательно a tg Так как sin ∠LCK = sin ∠IQK = sin(α/2), можно записать ID =
= a tg(α/2). С другой стороны, r = AQ tg(α/2) и AQ = (b + c − где — радиус вписанной окружности треугольника Теперь заметим, что описанная окружность треугольника
ILK
касается вписанной окружности треугольника тогда и только тогда, когда диаметр описанной окружности треугольника равен радиусу вписанной окружности треугольника |ID| ⇔
b
+ c − a
2
= a ⇔ b + c = Задача. Ответ N
= 2n − Пусть ¾ 2n. Рассмотрим A = {1, 2, . . . , N}, где i и j знакомы друг с другом тогда и только тогда, когда 1 ¶ i, j ¶ n или n + 1 ¶ i, j ¶ 2n. Тогда группа является компактной, ноне содержит n
+ 1 знакомых каждый с каждым людей.
Теперь докажем, что любая
n-компактная группа A, состоящая из 2
n
− 1 людей, включает n + 1 людей, которые знакомы каждый с каждым. Пусть. . . , C
𝑚
— последовательность всех
n-элемент- ных подмножеств множества, которые знакомы каждый с каждым.
Пусть
B
𝑘
= (C
1
∩ C
2
∩ . . . ∩ C
𝑘
)
∪ ((C
1
∪ C
2
∪ . . . ∪ C
𝑘
)
∩ при 1 ¶ k < Любые два члена группы
B
𝑘
знакомы друг с другом, так как либо они оба принадлежат C
2
∩ . . . ∩ C
𝑘
⊂ C
1
, либо они оба принадлежат. . .∪C
𝑘
)
∩C
𝑘
+1
⊂ C
𝑘
+1
, либо один принадлежит C
2
∩ . . . ∩ а другой принадлежит (
C
1
∪ C
2
∪ . . . ∪ C
𝑘
)
∩ C
𝑘
+1
; в последнем случае они оба принадлежат некоторому, 1 ¶ j ¶ k.

Решения задач МОШП Мы утверждаем, что ¾ n + 1, хотя бы при одном k, 1 ¶ k < Предположим противное, тогда = |C
1
∩ C
2
∩ . . . ∩ C
𝑘
| +
+ |(C
1
∪ C
2
∪ . . . ∪ C
𝑘
)
∩ C
𝑘
+1
| − |C
1
∩ C
2
∩ . . . ∩ C
𝑘
+1
| =
= |C
1
∩ C
2
∩ . . . ∩ C
𝑘
| + |C
1
∪ C
2
∪ . . . ∪ C
𝑘
| + |C
𝑘
+1
| −
− |C
1
∪ C
2
∪ . . . ∪ C
𝑘
+1
| − |C
1
∩ C
2
∩ . . . ∩ C
𝑘
+1
| ¶ при всех 1 ¶ k < m. Следовательно C
2
∩ . . . ∩ C
𝑘
| + |C
1
∪ C
2
∪ . . . ∪ C
𝑘
| ¶
¶ |C
1
∩ C
2
∩ . . . ∩ C
𝑘
+1
| + |C
1
∪ C
2
∪ . . . ∪ при всех 1 ¶ k < m. В частности |C
1
| + |C
1
| ¶ |C
1
∩ C
2
∩ . . . ∩ C
𝑚
| + |C
1
∪ C
2
∪ . . . ∪ C
𝑚
| ¶ 2n − так как множество C
2
∩ . . . ∩ является пустым в силу
n-ком- пактности
A. Противоречие.
Задача_1'>4-я олимпиада, 2005 год
Задача
1
. Для удобства пронумеруем условия+ 2
𝑛
−1
+ . . . + (n − 1)
𝑛
−1
)
+ 1 делится на n,
(1)
n
p
− 1 делится на p и 1 делится на p − Пусть Ap. Для начала заметим, что −A (mod p), если n − 1 делится на p − 1,
0 (если 1 не делится на p − Первый случай следует из малой теоремы Ферма. Второй случай можно доказать, например, следующим образом пусть — первообразный корень по модулю см. определение нас, тогда А из того, что 6≡ 1 (mod p), следует, что 0 (mod Допустим, что выполняется условие (1). Тогда либо 1 делится на 1 и A − 1 делится на p, либо n − 1 не делится на p − 1 и делится на. Поэтому n
− 1 делится на p − 1 и A − 1 делится на p.

Решения задач МОШП 2005 Следовательно 1 = (p − 1)A + A − 1 делится на p − 1, поэтому 1 делится на p − 1, и мы получаем условие (Теперь предположим, что выполняется условие (2). Тогда делится на. Следовательно, n не делится нате не делится на квадраты простых чисел. Число 1 делится на p − 1. Тогда 1) = n − 1 − (p − 1) делится на p − 1. Поэтому n − 1 делится на 1. Следовательно 1 − A ≡ 0 (mod так как 1 делится на p. Поскольку это справедливо для всех простых делителей числа n и n не делится на квадраты простых чисел,
по китайской теореме об остатках (см. теорему нас, получаем условие (Задача. Ответ хотя бы одно из них чётно.
Назовём раскраску доски хорошей, если она удовлетворяет условию задачи. Если произведение является чётным, то доска имеет хорошую раскраску. Предположим, что количество строк чётно. Тогда покрасим первую и вторую строки в белый цвет, третью и четвёртую строки в чёрный, пятую и шестую строки в белый цвет итак далее.
Получим хорошую раскраску.
Теперь допустим, что произведение является нечётным и доска имеет хорошую раскраску. Тогда количество белых либо количество чёрных клеток является нечётным. Не теряя общности, предположим,
что количество белых клеток нечётно. Рассмотрим множество множество упорядоченных пар различных белых клеток, которые не являются соседними.
Так как каждая пара клеток встречается в по два раза, W имеет чётное количество элементов. С другой стороны, имеется нечётное количество белых клеток, итак как раскраска хорошая, для каждой белой клетки существует нечётное количество других не соседних с ней белых клеток. Следовательно имеет нечётное количество элементов. Противоречие.
Задача
3
. Ответили Если острый, то ∠CO
1
A
0
= 2∠CAA
0
= 2∠CBB
0
= Если же тупой, то 2(180
◦
− ∠CAA
0
)
= 2(180
◦
− ∠CBB
0
)
= ∠CO
2
B
0

Решения задач МОШП Рис. В любом случае ∠CO
1
A
0
= ∠CO
2
B
0
. (Легко показать, что 6= при ∠CAA
0
= 90
◦
.) Поскольку оба треугольника
CO
1
A
0
и
CO
2
B равнобедренные, они подобны.
Следовательно, ∠O
1
CO
2
= и CB
0
:
CO
2
. Это означает, что треугольники
A
0
CB
0
и
O
1
CO
2
также подобны. Ноу подобных треугольников площади равны только в том случае, когда эти треугольники равны. Следовательно ∆O
1
CO
2
, а значит CA
0
, т. е.
4CO
1
A
0
правильный, и потому ∠CO
1
A
0
= Итак, ∠CAA
0
= 30
◦
, если острый, и ∠CAA
0
= 150
◦
, если
∠CAA
0
тупой.
Задача
4
. Для начала докажем, что+ 1) − a(n) = 0 или при всех натуральных. Это верно при n
= 1, 2, так как a(3) = Предположим, что ¾ 3 и условие (1) верно при всех k ¶ n. В частности при всех k ¶ n, и рекуррентная формула имеет место. Тогда+ 1) − a(n) =
= a(a(n)) − a(a(n − 1)) + a(n + 1 − a(n)) − a(n − a(n − 1)) =
=
¨ a(n − a(n) + 1) − a(n − a(n)), если a(n) = a(n − 1),
a(a(n
− 1) + 1) − a(a(n − 1)), если a(n) = a(n − 1) + откуда условие (1) следует по индукции.
Теперь допустим, что) ¶ 2a(n) не при всех n ¾ 1, и пусть m наименьшее натуральное число, для которого данное утверждение

Решения задач МОШП 2006 ложно. Следовательно 2a(m), и 1)) ¶ 2a(m − При этом если a(m − 1) + 1, то 2a(m) = 2(a(m − 1) + 1) ¾ a(2(m − 1)) + и мы получаем противоречие с условием (1). Следовательно a(m − Пусть a(m) = a(m − 1). Так как a(2m) > 2M и a(2m − 2)) ¶ получим 1) = 2M или 2M + Если 1) = 2M, то a(2M) + a(2m − 2M) ¶ 2a(M) + 2a(m − M) =
= 2 a(a(m − 1)) + a(m − a(m − 1))

= что противоречит нашему предположению Если 1) = 2M + 1, то a(2m − 2) = 2M и 1) = a(2M) + a(2m − 1 − 2M) ¶ a(2M) + a(2m − 2M) ¶
¶ 2a(M) + 2a(m − M) = а значит, 2
M
+ 1 ¶ 2M, и мы вновь получаем противоречие.
5-я олимпиада, 2006 год
Задача
1
. Ответ f (x)
= x при всех x ∈ Первое решение. С помощью тождества+ xy = (−x − y)
2
+ (−x − получаем следующее тождество для нашей функции :
(
f (x))
2
+ x f (y) = ( f (−x − y))
2
− (x + y) f ( Выпишем некоторые полезные частные случаи последнего тождества.
При
y
= −x получим (x))
2
+ x f (−x) = ( f При 0 получим (x))
2
+ x f (0) = ( f (−x))
2
− x f Из равенства (1) вытекает соотношение (x))
2
+ x f (−x) = ( f (−x))
2
− x f (x),

Решения задач МОШП которое эквивалентно следующему (x)
+ f (−x))( f (x) − f (−x) + x) = Допустим, что при 0 верно равенство f (a) − f (−a) + a = 0. Тогда из соотношения (2) получаем (a))
2
+ 2a f (0) = ( f (−a))
2
= ( f (a) + откуда вытекает, что (0)
= 2 f (a) + После выражения значений (0) ив формуле (1) через a, f получаем a
2
/4. Следовательно, a = Полученное противоречие означает, что (x)
+ f (−x) = 0 для любого 0. Теперь из формулы (2) получаем f (0) = 0. Тождество) принимает вид (x)
· ( f (x) − x) = 0. Если положить вис- ходном уравнении 0, то получим f ( f (y)) = y, откуда следует инъ- ективность функции см. определение нас. Значит, при имеем (x)
6= 0. Итак, f (x) ≡ x, что, очевидно, удовлетворяет исходному тождеству.
Второе решение. При x
= 0 получаем f ( f (y)) = y + ( f (0))
2
, инъ- ективность и сюръективность функции . Пусть f (a)
= 0, тогда при подстановке y = a получаем f (2a
2
)
= a. Отсюда следует, что+ ( f (0))
2
= 0, или a = f (0) = 0. В частности, f ( f (y)) = Подстановка 0 в исходное уравнение приводит к тождеству (x
2
)
= ( f (x))
2
, откуда с помощью инъективности получаем (x)
=
= − f При подстановке −x получаем f (x) · ( f (x) − x) = 0, и снова по инъективности, применяя неравенство 0, те, приходим к равенству (x)
≡ Задача. Первое решение. Пусть x, y, z — такие положительные действительные числа, что y/x, b = z/y, c = x/z. После подстановки и упрощений исходное неравенство перепишется в следующем виде+ y + z)
3
p
xyz ¶ 3(x + y)
2
/3
(
y
+ z)
2
/3
(
z
+ Для треугольника со сторонами x + y, v = y +z, w =z + x последнее неравенство приобретает вид u)(p − v)(p − w) ¶ 3(uvw)
2
/3
,

Решения задач МОШП 2006 где — полупериметр этого треугольника. С учётом формулы Герона это неравенство эквивалентно следующему неравенству (где — площадь треугольника, R — радиус описанной окружности.
А неравенство+ v + w = 2p ¶ широко известное и существует множество вариантов его доказатель- ства.
Второе решение. Если возвести обе части в куб, то из-за условия 1 мы избавляемся от радикалов. После упрощений получим следующее неравенство+ 30
X
cyc
€
a
+
1
a
Š + 10
X
cyc
a
b
¶ 54
X
cyc
b
a
+ Последнее неравенство является прямым следствием следующих простейших неравенств ¶
X
cyc
b
a
,
a
+
1
a
¶
1 4
€
a
2
+
1
a
2
+ 6
Š
,
2 ¶ Задача. Ответ Рассмотрим подмножество {(p + 1)/2, . . . , p − 2, p − 1}. Тогда (−1)
(𝑝
−1)/2
€
p
− 1 2
Š
!
= −
€
p
− 1 2
Š
!
≡ a (mod p),
Π
𝑠
=
€
p
− 1 2
Š
!
≡ −a (mod По теореме Вильсона 1 (mod p), поэтому возможны два случая.