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

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

1. Если n составное, то n
= mk для 1 < m, k < n. Тогда из неравенства) следует, что (n) ¾ f (m) f (k) ¾ m
2
k
2
= n
2
2. Если n — простое число вида 4k
+ 1, то по теореме Ферма найдутся такие, y
∈ N, что n = x
2
+ y
2
. Тогда из неравенства (следует, что (n)
= f (x
2
+ y
2
) ¾ ( f (x) + f ( y))
2
¾ (x
2
+ y
2
)
2
= n
2
3. Если же n — простое число вида 4k
+ 3, то n
2
+ 1 = 2p
1
. . . для простых 4k
𝑖
+ 1, i = 1, . . . , k. Тогда найдутся такие x
𝑖
,
y
𝑖
∈ что+ y
2
𝑖
= p
𝑖
¶ (n
2
+ 1)/2 < n
2
, что ведёт к неравенствам а значит (p
𝑖
) ¾ f (x
2
𝑖
+ y
2
𝑖
) ¾ ( f (x
𝑖
)
+ f (y
𝑖
))
2
¾ (x
2
𝑖
+ y
2
𝑖
)
2
= Из неравенства (
7
) следует, что (n
2
+ 1) ¾ f (2) f (p
1
)
. . . f (p
𝑘
) ¾ 2 2
p
2 1
. . . p
2
𝑘
= (n
2
+ а из равенства (
4
) — что (n)
=
p
f (n
2
+ 1) − 1 ¾ Лемма 3. Если a, b
∈ A, то ab ∈ A и a
2
+ b
2
∈ Доказательство. Из определения множества A следует, что (an)
= a
2
f (n),
f (bn)
= b
2
f при всех Тогда (abn)
= a
2
f (bn)
= a
2
b
2
f (n), следовательно, ab
∈ A. При x = an,
y
= bn получим (xy)
= f (abn
2
)
= (ab)
2
f (n)
2
=
= (a
2
f (n))(b
2
f (n))
= f (an) f (bn) = f (x) f По лемме 1 имеем ((a
2
+ b
2
)
n
2
)
= f (x
2
+ y
2
)
= ( f (x) + f (y))
2
= (a
2
+ b
2
)
2
· f а значит, по лемме 2 выполняется включение+ b
2
∈ Лемма 4. Если k
∈ A и d является делителем числа k, то d ∈ A.

Решения задач МОШП 2014 Доказательство. Из неравенства (
8
) имеем (n)
= f (kn) ¾ f (dn) f
€
k
d
Š
¾
€
k
d
Š
2
f откуда получим (n) ¾ f (dn) ¾ f (d) f (n) ¾ d
2
f или (dn)
= d
2
f (n), поэтому d
∈ Построим такую бесконечную последовательность различных простых чисел, что 2 и для всех k число p
𝑘
+1
— простой делитель числа (
p
1
. . . p
𝑘
)
2
+ 1. Тогда p
𝑖
≡ 1 (mod 4). Докажем индукцией по, что Для 1 это верно. По лемме 3, так как p
𝑖
∈ A для i = 1, . . . , k и 1 ∈ имеем. . . p
𝑘
∈ A и x = (p
1
. . . p
𝑘
)
2
+ 1 ∈ A. Отсюда по лемме 4 получаем, что Лемма 5. Если r
= a
2
+ b
2
∈ A
1
, то a, b
∈ Доказательство. Так как r
∈ A
1
, получаем, что (r)
= r
2
. Из соотношений) и (
8
) следует, что f (r) = f (a
2
+ b
2
) ¾ ( f (a) + f (b))
2
¾ (a
2
+ b
2
)
2
= откуда немедленно получаем равенства (a)
= a
2
,
f (b)
= b
2
. Значит, b
∈ Лемма 6. Если r
∈ и d является делителем числа r, то d
∈ Доказательство. Число r представимо в виде r
= kd. Тогда f (d) ¶
f (r)
f (k)
=
r
2
f (k)
¶
r
2
k
2
= следовательно (d)
= Из включения (
9
) следует, что для любого выполняется равенство и при ¾ 2 имеет место сравнение 1 (mod 4), следовательно, для всех i найдутся такие x
𝑖
,
y
𝑖
∈ N, что x
2
𝑖
+ y
2
𝑖
. Рассмотрим произвольное N и числа ( y
𝑖
,
n). Среди них какое-то число встречается бесконечно много раз, пусть это
d.
Рассмотрим бесконечное множество {i | i ∈ N, (y
𝑖
,
n)
= d} и y
𝑖
= для всех B, (z
𝑖
,
n)
= 1. Тогда существуют такие i < j (i, j ∈ B), что x
𝑗
/z
𝑗
(mod
n), поэтому |x
𝑖
y
𝑗
− x
𝑗
y
𝑖
| = |d(x
𝑖
z
𝑗
− x
𝑗
z
𝑖
)
|

Решения задач МОШП делится на и t
= x
𝑖
x
𝑗
+ y
𝑖
y
𝑗
. Тогда s
2
+ t
2
. Значит 0. Так как A, по лемме 3 получаем, что p
𝑖
p
𝑗
∈ A, и тогда f (p
𝑖
p
𝑗
)
= (откуда следует, что A
1
. По лемме 5 имеем, t
∈ итак как
s
делится на, по лемме 6 имеем n
∈ A
1
, следовательно (n)
= для любого натурального. Легко видеть, что ответ удовлетворяет начальным условиям.
Задача_2'>Задача_1'>14-я олимпиада, 2015 год
Задача
1
. Заметим, что 3 3
È
a
b
·
b
c
·
c
d
= 3 откуда 3 3
pa/d < 6 или a/d < 8. Аналогично получим неравенства < 8, c/b < 8 и b/a < 8. Из последних четырёх неравенств получим 32.
Противоречие.
Задача
2
. Пусть и первый член и разность прогрессии
{a
𝑛
}
соответственно. Аналогично определим
b
1
и
d
𝑏
. Заметим, что a
𝑛
b
𝑛
+1
=
= (a
1
+ nd
𝑎
)(
b
1
+ (n − 1)d
𝑏
)
− (a
1
+ (n − 1)d
𝑎
)(
b
1
+ nd
𝑏
)
=
= −a
1
d
𝑏
+ b
1
d
𝑎
= C = const . (Воспользуемся известным тождеством+ y
2
)(
z
2
+ t
2
)
= (xz + yt)
2
+ (xt − Тогда (a
2
𝑛
+ a
2
𝑛
+1
)(
b
2
𝑛
+ b
2
𝑛
+1
)
=
= (a
𝑛
b
𝑛
+ a
𝑛
+1
b
𝑛
+1
)
2
+ (a
𝑛
+1
b
𝑛
− b
𝑛
+1
a
𝑛
)
2
=
= (a
𝑛
b
𝑛
+ a
𝑛
+1
b
𝑛
+1
)
2
+ Аналогично (a
2
𝑛
+ b
2
𝑛
)(
a
2
𝑛
+1
+ b
2
𝑛
+1
)
= (a
𝑛
+1
a
𝑛
+ b
𝑛
+1
b
𝑛
)
2
+ Определим новую последовательность
{x
𝑛
}
𝑛¾1
следующим образом:
если
p
𝑛
— полный квадрат, то a
𝑛
+1
b
𝑛
+1
+ a
𝑛
b
𝑛
, а в противном слу-

Решения задач МОШП 2015 чае a
𝑛
+1
a
𝑛
+ b
𝑛
+1
b
𝑛
. Тогда по условию+ C
2
— полный квадрат для любого натурального. Обозначим+ C
2
= Предположим, что 0. Тогда y
𝑛
> для любого натурального
n,
т. е x
𝑛
+ 1. Поэтому y
2
𝑛
− x
2
𝑛
= (y
𝑛
− x
𝑛
)(
y
𝑛
+ x
𝑛
) ¾ 2x
𝑛
+ что невозможно, ввиду того что последовательность неограни- чена. Значит 0, и поэтому справедливо равенство a
1
d
𝑏
= Но по условию задачи (
a
1
,
d
𝑎
)
= (b
1
,
d
𝑏
)
= 1. Таким образом, a
1
= и d
𝑏
, откуда следует утверждение задачи.
Задача
3
. Ответ f (n)
= n · Нетрудно заметить, что для любых последовательностей, b
∈ все элементы строк
"
0
"
1
"
𝑛
и
δ
0
δ
1
δ
𝑛
будут равны 0 или Для каждой последовательности определим сопряжённую ей последовательность так, чтобы каждый элемент сопряжён- ной последовательности дополнял в сумме до 1 соответствующий ей элемент исходной последовательности. Для каждой пары последовательностей определим четвёрку пари. Заметим, что для каждой такой четвёрки при любом фиксированном, только одно из равно 1, а остальные три
"
𝑖
равны Количество всевозможных пар, b
∈ равно 4
𝑛
, и они разбиваются на 4
𝑛
−1
четвёрок. Для каждой четвёрки
w(a, b)
+ w(a, b) + w(a, b) + w(a, b) = так как для всех пара для каждого i, 1 ¶ i ¶ n, только одно из
"
𝑖
равно 1. Следовательно (n)
=
X
𝑎
,𝑏
∈ 𝑏
𝑛
w(a, b)
=n · Задача. Отметим точки P и Q, симметричные вершине A относительно и C соответственно. Пусть M и N — середины сторон и AC соответственно (см. рис. В треугольнике проведём высоту. Заметим, что точки A, M, N и O лежат на окружности с диаметром. Поэтому ∠AON = ∠AMN = ∠APQ. Так как треугольники и APH прямоугольные и ∠AON = ∠APQ, получаем, что

Решения задач МОШП Рис. они подобны. Значит AH = AN · AP =
AC
2
· 2AB = AC · Рассмотрим композицию инверсии с центром в точке радиусом и симметрии относительно биссектрисы угла Такая композиция меняет местами точки и H, а также точки и. Значит, окружность, проходящая через точки B, O и C, перейдёт в окружность, проходящую через точки B, H и C те. в окружность девяти точек треугольника. Образом окружности при такой композиции является окружность, вписанная в угол и касающаяся (внешним образом) дуги окружности очевидно, что такая окружность единственна).
С другой стороны, в силу теоремы Фейербаха вневписанная окружность треугольника APQ соответствующая вершине A) касается
(внешним образом) дуги окружности. Значит, Γ — образок- ружности
ω. Следовательно, ω касается образа прямой PQ, те. описанной окружности треугольника так как AM
·AB= AB·AC= Таким образом, гомотетия с центром в точке, переводящая треугольник в ABC, переводит в Ω, что и завершает доказательство

Решения задач МОШП 2016 я олимпиада, 2016 год
Задача
1
. Ответ:
3
p
4.
Не теряя общности, можно предположить, что ¾ b ¾ c. Тогда из неравенства между средним арифметическими средним геометрическим получим (a − b)(b − c)(a − c) ¶
€
(
a
− b) + (b − c)
2
Š
2
· (a − c) =
(
a
− c)
3 а значит c ¾
3
p
4. Следовательно + |b| + |c| = (|a| + |c|) + |b| ¾ |a − c| + |b| ¾
3
p
4
+ 0 Заметим, что равенство выполнено при b = b − c, b = 0 и a − c Из последних трёх уравнений нетрудно понять, что существует единственная тройка чисел, для которых выполнены эти равенства 1/
3
p
2,
b
= 0, c = Задача. Пусть CD и NN
1
— диаметры описанной окружности середина стороны см. рис. Понятно, что четырёхуголь- ник прямоугольник. Поэтому и A
1
B
1
. Также понятно, что середина дуги меньшей дуги, а точка лежит на отрезке. Значит, ∠ACN
1
= ∠BCN
1
, и потому ∠ACA
1
=
= ∠BCB
1
. Следовательно, прямоугольные треугольники
ACA
1
и
BCB
1
A
B
C
D
M
A
1
B
1
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
A
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
B
2
N
N
1
N
1
M
1
K
Рис. 49

Решения задач МОШП подобны. Из подобия получаем, а значит, A
2
B
2
k Получается, что точка — центр гомотетии, переводящей треугольник в треугольник ABD; в частности, K лежит на отрезке и ∠B
1
KM
= Заметим, что из подобия треугольников также следует равенство ∠KB
1
C, те. точка K лежит на серединном перпендикуляре к отрезку. Так как середина, прямая M
1
K содержит среднюю линию прямоугольной трапеции, откуда следует,
что
M
1
K
⊥ A
1
B
1
. Значит равнобедренная трапеция.
Теперь для решения задачи достаточно показать, что ∠A
1
KN
=
= ∠BDM
1
. Из того, что AC и AD ⊥ AC, следует, что A
1
K
k Имеем A
1
KN
+ ∠DNK = ∠(DN, KA
1
)
= ∠ADN = ∠BDN = ∠BDM
1
+ Отсюда немедленно следует равенство ∠A
1
KN
= ∠BDM
1
, так как = Задача. Обозначим [
p
n]
= N. Тогда n = N
2
+ x для некоторого целого, 0 ¶ x ¶ 2N. Тогда из условия задачи следует, что для любого N выполняется условие (N
2
+ a + x)
. f (n + для всех целых 0 ¶ x ¶ Понятно, что существует такое N, что для любого n ¾ будет выполнено неравенство+ a > n + b. Докажем задачу индукцией по
n.
База:
n
= 1, a
1
= n
0
+ 2b. Предположим, что задача верна для всех чисел, небольших. Обозначим M
= a
1
a
2
. . . a
𝑛
. Построим последовательность следующим образом и (x
𝑖
− b)
2
+ a + 2(x
𝑖
− b) для любого i ∈ Тогда a
𝑛
¾ a
1
> 2b и индукцией легко доказать, что x
𝑖
+1
> По условию (1) имеем (x
𝑖
+1
)
. f (x
𝑖
) для любого N. Существует такое N, что x
𝑘
¾ M + b. Из условия (1) следует, что ((x
𝑘
− b)
2
+ a + t)
. f для любого, 0 ¶ t ¶ 2(x
𝑘
− b), те. это верно и для 0 ¶ t ¶ M. Из этих+ 1 последовательных чисел существует одно число вида pM + 1
(
p
∈ N). Тогда при a
𝑛
+1
= pM + 1 имеем (a
𝑛
+1
,
M)
= 1. Следовательно 1 для всех i, 1 ¶ i ¶ n, и (a
𝑛
+1
)
. f (x
𝑘
)
. f (x
1
)
. f (a
𝑛
).

Решения задач МОШП 2016 Задача. Для удобства положим P(0)
= 1. Рассмотрим бесконечный степенной ряд (производящую функцию P(0) + P(1)x + P(2)x
2
+ . . . Нетрудно доказать, что x)(1 − x
2
)(1
− x
4
)
=
Ì
Y
𝑚
=0 1
1
− Действительно, каждое разбиение можно записать так k
1
· 2
𝑚
+ k
2
· 2
𝑚
−1
+ . . . k
𝑚
−1
· 2 + k
𝑚
=
= 2
𝑚
+ . . . + 2
𝑚
|
{z
}
𝑘
1
+ 2
𝑚
−1
+ . . . + 2
𝑚
−1
|
{z
}
𝑘
2
+ . . . + 1 + . . . + где 0 ив тоже время 1
− Рассмотрим теперь новый ряди заметим, что
B(x)
=
Ì
X
𝑛
=0
(
−1)
𝑎
𝑛
x
𝑛
,
где
a
𝑛
— количество единиц в двоичной записи числа. Это верно,
поскольку при раскрытии скобок в x
2
𝑚
) степень
x
𝑛
можно собрать единственным способом из двоичного представления и (как раз будет означать количество этих множителей вида
−x
2
𝑚
Очевидно, что 1. Поэтому 
Ì
X
𝑛
=0
(
−1)
𝑎
𝑛
x
𝑛
‹
= Раскрывая скобки в левой части этого выражения, получаем, что коэффициент при любой степени 0) равен 0, ив тоже время он равен+ (−1)
𝑎
1
P(n
− 1) + (−1)
𝑎
2
P(n
− 2) + . . . + (−1)
𝑎
𝑛

Справочные материалы