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

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

Задача
5
. Сначала заметим, что если i
6= j, то a
𝑖
a
𝑗
¶ (a
2
𝑖
+ и значит a
𝑖
a
𝑗
¾ n −
a
2
𝑖
+ a
2
𝑗
2
¾ n −
n
2
=
n
2
> Если обозначить |a
𝑖
| (i = 1, 2, . . . , n), то 1
+ b
2 2
+ . . . + b
2
𝑛
= n и a
𝑖
a
𝑗
¶
1
n
− b
𝑖
b
𝑗
,

Решения задач АТМО 2012 откуда следует, что утверждение задачи достаточно доказать для случая, когда. . . , a
𝑛
— неотрицательные действительные числа.
Теперь можно предположить, что все числа. . . , являются неотрицательными действительными числами.
Умножая обе части доказываемого неравенства на, получим a
𝑖
a
𝑗
¶
n
2 Так как a
𝑖
a
𝑗
= 1 +
a
𝑖
a
𝑗
n
− после уменьшения обеих частей неравенства на 1)/2 получим следующее эквивалентное неравенство Докажем справедливость неравенства (Если для некоторого выполняется равенство a
2
𝑖
= n, то a
𝑗
= для всех i, и неравенство (1) доказывается тривиально. Значит,
можно предположить, что n для всех В дальнейших рассуждениях j. Так как ¶ a
𝑖
a
𝑗
¶
€
a
𝑖
+ a
𝑗
2
Š
2
¶
a
2
𝑖
+ получаем, что a
𝑖
a
𝑗
¶
a
𝑖
a
𝑗
n
−
a
2
𝑖
+ a
2
𝑗
2
¶
€
a
𝑖
+ a
𝑗
2
Š
2
n
−
a
2
𝑖
+ a
2
𝑗
2
=
1 2
·
(
a
𝑖
+ a
𝑗
)
2
(
n
− a
2
𝑖
)
+ (n − Так как a
2
𝑖
>0, n−a
2
𝑗
>0, из неравенства Коши — Буняковского имеем a
2
𝑖
+
a
2
𝑖
n
− a
2
𝑗

((
n
− a
2
𝑖
)
+ (n − a
2
𝑗
)) ¾ (a
𝑖
+ Отсюда следует, что+ a
𝑗
)
2
(
n
− a
2
𝑖
)
+ (n − a
2
𝑗
)
¶

a
2
𝑗
n
− a
2
𝑖
+
a
2
𝑖
n
− Объединяя неравенства (2) и (3), получаем a
𝑖
a
𝑗
¶
1 2
X
1¶𝑖<𝑗¶𝑛

a
2
𝑗
n
− a
2
𝑖
+
a
2
𝑖
n
− a
2
𝑗

=

Решения задач АТМО 2013
=
1 2
X
𝑖
6= 𝑗
a
2
𝑗
n
− a
2
𝑖
=
1 2
𝑛
X
𝑖
=1
n
− a
2
𝑖
n
− что и доказывает требуемое неравенство (я олимпиада, 2013 год
Задача
1
. Первое решение. Пусть M и N — середины сторон и соответственно (см. рис.
25
).
A
B
C
D
E
F
M
N
O
Рис. Заметим, что ∠MOC =
1 2
∠BOC = ∠EAB, ∠OMC = 90
◦
= ∠AEB. Следовательно, откуда OM : AE = OC : AB. Аналогично ∼ 4BDA, откуда ON : BD = OA : BA. Поэтому OM : AE = ON : или OM = AE · Пусть площадь треугольника. Заметим, что 2
BD
· OM =
1 2
AE
· ON = Аналогично и Второе решение. Пусть R — радиус описанной окружности треугольника будем кратко обозначать через ∠A, ∠B, ∠C углы CAB,
ABC, BCA соответственно, а через a, b, c — стороны BC, CA, AB соответственно. Тогда площадь треугольника равна 2
· OC · CD · sin ∠OCD =
1 2
R
· CD · sin Далее b cos ∠C, и =
180
◦
− 2∠A
2
= 90
◦
− ∠A

Решения задач АТМО 2013 поскольку треугольник равнобедренный и ∠BOC = 2∠A). Таким образом 2
Rb cos ∠C sin(90
◦
− ∠A) =
1 2
Rb cos ∠C cos С помощью аналогичных вычислений получаем 2
OA
· AF · sin ∠OAF =
=
1 2
R
· (b cos ∠A) sin(90
◦
− ∠C) =
1 2
Rb cos ∠A cos поэтому S
𝑂𝐴𝐹
. Таким же способом получаем, что и Задача_3'>Задача. Ответ таких натуральных чисел не существует.
Докажем, что натуральных, удовлетворяющих указанному условию, не существует.
Пусть
m
= [
p
n] и a
= n − m
2
. Имеем ¾ 1, так как n ¾ 1. Из соотношения) следует, что наше условие эквивалентно тому, что (
a
− 2)
2
+ 1 делится на m
2
+ Поэтому (a − 2)
2
+ 1 ¶ max{2 2
, (2
m
− 2)
2
} + 1 ¶ 4m
2
+ 1 < 4(m
2
+ Тогда соотношение (
a
− 2)
2
+ 1 = k(m
2
+ 2) может выполняться лишь с 1, 2 или 3. Докажем, что все три случая невозможны.
Случай 1: k
=1. Имеем (a−2)
2
−m
2
=1. Это означает, что a−2=±1,
m
= 0. Последнее же противоречит тому, что m ¾ Случай 2: k
= 2. Имеем (a − 2)
2
+ 1 = 2(m
2
+ 2), однако каждый полный квадрат сравним с 0, 1, 4 (mod 8), откуда получаем, что 2)
2
+ 1 ≡ 1, 2, 5 (mod 8), в то время как 2(m
2
+ 2) ≡ 4, 6 (mod Значит, этот случай также невозможен.
Случай 3: k
= 3. Тогда (a − 2)
2
+ 1 = 3(m
2
+ 2). Поскольку каждый полный квадрат сравним с 0 или 1 по модулю 3, получим, что, 2 (mod 3), однако 3(m
2
+2)≡0 (mod 3). Значит, и этот случай не имеет места.
Задача
3
. Обозначим A
= и P
𝑘
𝑖
=1
b
𝑖
. Просуммируем следующие неравенства по от 1 до k :
a
𝑖
n
+ b
𝑖
− 1 < [a
𝑖
n
+ b
𝑖
] ¶ a
𝑖
n
+ откуда получим+ B − k < X
𝑛
< An + B. Предположим, что {X
𝑛
} арифметическая прогрессия с разностью, тогда nd
= X
𝑛
+1
− и

Решения задач АТМО 2013
A
+ B − k < X
1
¶ A + B. Используя полученные выше неравенства,
получаем, что+ 1) + B − k < nd + X
1
< A(n + 1) + или k ¶ An + (A + B − X
1
)
− k < nd < An + (A + B − X
1
)
< An + откуда заключаем, что − d| < k/n. Поскольку это неравенство выполняется для всех натуральных, должно выполняться равенство d. Поскольку {X
𝑛
} — последовательность целых чисел, d — целое число, поэтому также целое число.
Задача_5'>Задача
4
. Первое решение. Пусть {n − a: n ∈ A} и B
∗
= {n + b: n ∈ Тогда согласно условию 1 имеем B ⊆ A
∗
∪ и согласно условию получаем ∪ B| ¶ |A
∗
∪ B
∗
| ¶ |A
∗
| + |B
∗
| = |A| + |B| = |A ∪ Следовательно B = A
∗
∪ B
∗
, и
A
∗
и
B
∗
не имеют общих элементов.
Для любого конечного числового множества введём обозначение (X)
= P
𝑥
∈ 𝑋
x. Тогда B) =
=
X
(
A
∗
∪ B
∗
)
=
X
(
A
∗
)
+
X
(
B
∗
)
=
=
X
(
A)
− a|A| +
X
(
B)
+ Следовательно = Второе решение. Рассмотрим ориентированный граф, вершинам которого присвоены элементы из B ив котором ребро от к проведено в томи только в том случае, когда j
∈ A и j = i + a или B и j = i − b. Согласно условию 2 для каждой вершины имеется не менее одного исходящего ребра, и согласно условию 1 для каждой вершины имеется не более одного входящего ребра. Поскольку сумма по вершинам количеств исходящих рёбер равна сумме по вершинам количеств входящих рёбер, каждая вершина имеет ровно по одному исходящему и по одному входящему ребру. Это возможно лишь в том случае, когда граф является объединением непересекающихся циклов. . . , G
𝑛
. Обозначим через количество элементов A

Решения задач АТМО 2013 из, а через — количество элементов B из G
𝑘
. При обходе направленного цикла
G
𝑘
числа увеличиваются на в вершинах рази уменьшаются на соответственно раз. Поскольку это цикл, получаем, что = b|B
𝑘
|. Просуммировав по всем циклам, получаем требуемый результат.
Задача
5
. Условие принадлежности точек B, E, R одной прямой равносильно тому, что прямые, BE, CQ пересекаются водной точке. Пусть пересекает AD в точке R, а BE пересекает AD в точке см. рис. Покажем, что : RA
= R
0
D : R
0
A, откуда будет следовать,
что
R
= Рис. Поскольку ∼ 4PDC и 4PAB ∼ 4PBC, имеем AD : DC =
= PA : PD = PA : PB = AB : BC. Следовательно, AB · DC = BC · По теореме Птолемея (см. теорему нас Аналогично ED = CE · AD =
1 2
AE
· DC.
Поэтому
DB
AB
=
2
DC
CA
,
(1)
и
DC
CA
=
2
ED
AE
(2)
Поскольку треугольники и RCA подобны, получаем
RD
RC
=
DC
CA
=
RC
RA
Отсюда, используя равенство (2), получим RA
RA
2
=
€
RC
RA
Š
2
=
€
DC
CA
Š
2
=
€
2
ED
AE
Š
2
(3)

Решения задач АТМО Из подобия треугольников
ABR
0
и
EDR
0
имеем
R
0
D : R
0
B
= ED : а из подобия треугольников
DBR
0
и
EAR
0
получаем
R
0
A : R
0
B
= EA : Согласно равенствами) имеем DB
EA
· Из соотношений (3) и (4) следует, что я олимпиада, 2014 год
Задача
1
. Возьмём достаточно большое натуральное число k и для каждого 2, 3, . . . , n выберем в качестве натуральное число, десятичная запись которого состоит из+ i − 2 цифр 2 и из 2
𝑘
+𝑖−1
−
− 2(k + i − 2) цифр 1. Имеем S(a
𝑖
)
= и для каждого В качестве
a
1
выберем натуральное число, десятичная запись которого состоит из+ n − 1 цифр 2 и 2
𝑘
− 2(k + n − 1) цифр Тогда и 2
𝑘
+𝑛−1
. Такой выбор
a
1
возможен, если
k
достаточно велико, чтобы выполнялось неравенство 2
𝑘
> 2(k + n − Нетрудно убедиться, что числа. . . , удовлетворяют требованиям задачи.
Задача
2
. Ответ 108
· Для каждого подмножества обозначим через r(X ) его представителя. Положим Сначала докажем следующее утверждение:
если
x
1
∈ X и X ⊆ S, то x
1
= Если |¶2012, то S можно представить как объединение X и ещё
двух подмножеств множества, причём попарные пересечения в этой тройке будут пустыми, следовательно r(X). Если |X| = 2013, то выберем X ( y 6= x
1
). Подмножество можно представить как объединение и ещё двух подмножеств. По доказанному выше) = поскольку = 2 < 2012), следовательно, y 6= r(X для всех X , кроме x
1
. Утверждение доказано.
Заметим, что это утверждение верно ив случае, когда множество содержит не менее 5 элементов.
Существует ровно 2014 способов выбрать r(S). Для x
1
∈ X ⊆ имеем )
= x
1
. Пусть S\{x
1
}. Аналогично существует ровно способов выбора, и для X имеем )
= x
2
. Про

Решения задач АТМО 2014 99
должая этот процесс, получаем, что существует ровно 2014
·2013·. . способов выбора таких элементов. . . , x
2010
∈ S, что для всех 1, 2, . . . , 2010 выполняется равенство x
𝑖
= r(X) для каждого X ⊆
⊆ S\{x
1
,
. . . , x
𝑖
−1
} и x
𝑖
∈ X .
Остаётся рассмотреть четырёхэлементное множество Существует ровно 4 способа выбора ). Пусть y
1
= r(Y ). Тогда очевидно, что r({y
1
,
y
2
}) = r({ y
1
,
y
3
}) = r({ Только у подмножеств y
1
,
y
2
,
y
3
}, { y
1
,
y
2
,
y
4
}, { y
1
,
y
3
,
y
4
}, { y
2
,
y
3
,
y
4
},
{ y
2
,
y
3
}, { y
2
,
y
4
}, { y
3
,
y
4
} ещё не указаны представители. Их можно выбрать как угодно, что даёт 3 4
· 2 3
способов.
Итак, общее число возможных назначений представителей равно 2013 · . . . · 4 · 3 4
· 2 3
= 108 · Задача. Ответ все натуральные числа вида n
= 3
𝑏
, где неотрицательное целое число.
Другими словами, нужно найти такие, что множество {a
3
+ a | a ∈ является полной системой вычетов по модулю те. это множество содержит всевозможные остатки при делении на. Будем называть это свойство свойством (
∗). Нетрудно увидеть, что n = 1 обладает свойством (
∗), а n = 2 — нет. Также ясно, что для выполнения свойства) число n должно быть нечётным.
Если
a
≡ b (mod n), то a
3
+ a ≡ b
3
+ b (mod n). Таким образом обладает свойством (
∗) тогда и только тогда, когда не существует таких чисел, b
∈ {0, . . . , n − 1}, что a 6= b и a
3
+ a ≡ b
3
+ b (mod Покажем, что обладает свойством (
∗) для всех j ¾ 1. Пусть+ a ≡ b
3
+ b (mod 3
𝑗
) для b. Тогда b) · (a
2
+ ab + b
2
+ 1) ≡ 0 (mod Легко проверяется, что+ ab + b
2
+ 1 не делится на Теперь заметим, что если множество не содержит полной системы вычетов по модулю, то оно не содержит и полной системы вычетов по модулю любого числа, кратного. Иными словами, достаточно доказать, что любое простое число 3 не удовлетворяет свойству (
∗).

Решения задач АТМО Если 1 (mod 4), то существует такое b, что b
2
≡ −1 (mod Тогда возьмём
a
= 0 и получим сравнение a
3
+ a ≡ b
3
+ b (mod Предположим, что 3 (mod 4). Докажем, что существуют такие целые числа, b
6≡ 0 (mod p), что a
2
+ ab + b
2
≡ −1 (mod p). Заметим,
что можно положить b (mod p), так как в противном случае, если+ ab + b
2
+ 1 ≡ 0 (mod p), получаем, что (2a)
2
+ 2a · (−a) + a
2
+ 1 ≡ 0
(mod
p) и 2a
6≡ −a (mod p). Полагая c обратным к b по модулю p те, получим эквивалентное соотношение (ac)
2
+ ac + 1 ≡
≡−c
2
(mod
p). Заметим, что
−c
2
может принимать все значения квадратичных невычетов по модулю. Если мы сможем найти такое что+ x + 1 является квадратичным невычетом по модулю p, то эти значения и c подходят.
Заметим, что если y и x, y ∈ {0, . . . , p − 1} = B, то+ x + 1 ≡ y
2
+ y + 1 (mod тогда и только тогда, когда делит x
+ y +1. Следовательно, x
2
+ x принимает ровно (
p
+ 1)/2 значений по модулю p, когда x пробегает. Поскольку существует ровно (p
− 1)/2 квадратичных невычетов по модулю, среди (p
+ 1)/2 значений x
2
+ x + 1 должен быть 0 и все квадратичные вычеты.
Пусть
C — множество квадратичных вычетов по модулю p и и пусть C. Предположим, что y ≡ z
2
(mod
p), и выберем z
≡ 2w + 1
(mod
p) (такое w всегда существует. Тогда+ 3 ≡ 4(w
2
+ w + 1) (mod Из предыдущей части решения известно, что 4(
w
2
+ w + 1) ∈ C. Это означает, что C, следовательно, y + 3 ∈ C. Из этого соотношения следует, что все элементы множества лежат в C. Полученное противоречие завершает доказательство.