Файл: Сборник содержит материалы для проведения заключительного этапа xlix всероссийской олимпиады школьников по математике.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 12
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Материалы для проведения заключительного этапа ВСЕРОССИЙСКОЙ
МАТЕМАТИЧЕСКОЙ
ОЛИМПИАДЫ ШКОЛЬНИКОВ учебный год
Второй день
Сириус,
21–27 апреля 2023 г.
Москва, 2023
МАТЕМАТИЧЕСКОЙ
ОЛИМПИАДЫ ШКОЛЬНИКОВ учебный год
Второй день
Сириус,
21–27 апреля 2023 г.
Москва, 2023
Сборник содержит материалы для проведения заключительного этапа XLIX Всероссийской олимпиады школьников по математике.
Задания подготовлены Центральной предметно-методической комиссией по математике Всероссийской олимпиады школьников.
Сборник составили Н. Х. Агаханов, С. Л. Берлов, И. И. Богданов, КА. Кноп, ПА. Кожевников, АС. Кузнецов, Ф. В. Петров,
О. К. Подлипский, КА. Сухов, АИ. Храбров, Д. Г. Храмцов.
А также А. В. Антропов, Д. Ю. Бродский, ДА. Демин, МА. Ди- дин, И. А. Ефремов, П. Ю. Козлов, Т. С. Коротченко, Е. Г. Молчанов,
А. В. Пастор, ДА. Терешин, И. И. Фролов, МА. Туревский, ГР. Челноков, О. И. Южаков.
В скобках после каждой задачи указана фамилия ее автора.
Компьютерный макет И. И. Богданов, АИ. Голованов Авторы и составители, 2023
© И. И. Богданов, АИ. Голованов, 2023, макет
Задания подготовлены Центральной предметно-методической комиссией по математике Всероссийской олимпиады школьников.
Сборник составили Н. Х. Агаханов, С. Л. Берлов, И. И. Богданов, КА. Кноп, ПА. Кожевников, АС. Кузнецов, Ф. В. Петров,
О. К. Подлипский, КА. Сухов, АИ. Храбров, Д. Г. Храмцов.
А также А. В. Антропов, Д. Ю. Бродский, ДА. Демин, МА. Ди- дин, И. А. Ефремов, П. Ю. Козлов, Т. С. Коротченко, Е. Г. Молчанов,
А. В. Пастор, ДА. Терешин, И. И. Фролов, МА. Туревский, ГР. Челноков, О. И. Южаков.
В скобках после каждой задачи указана фамилия ее автора.
Компьютерный макет И. И. Богданов, АИ. Голованов Авторы и составители, 2023
© И. И. Богданов, АИ. Голованов, 2023, макет
Заключительный этап, 2022–2023 учебный год. Второй день
Условия и решения задач класс. Если на столе лежит несколько кучек камней, считается, что на столе много камней, если можно найти 50 кучек и пронумеровать их числами от 1 до 50 так, что впервой кучке есть хотя бы один камень, во второй — хотя бы два камня, . . . , в пятидесятой хотя бы пятьдесят камней. Пусть исходно на столе лежат кучек по 100 камней в каждой. Найдите наибольшее n 6 10 000 такое, что после удаления из исходных кучек любых n камней на столе все равно останется много камней. (При удалении камней кучка не распадается на несколько.)
(Д. Храмцов)
Ответ. n = Решение. Если удалить полностью 51 кучку, то, очевидно,
не останется много камней. Значит, искомое значение n меньше. (Альтернативно, можно удалить из всех кучек по 51 кам- ню.)
Осталось показать, что при удалении любых n = 5099 камней останется много камней. Пусть в кучках осталось a
1
, a
2
, . . . камней соответственно можно считать, что 0 6 a
1 6 a
2 6
6 ... 6 a
100 6 100. Покажем, что a i+50
> i при i = 1, 2, . . . , то есть кучки с номерами от 51 до 100 удовлетворяют требова- ниям.
Пусть это не так, то есть a i+50 6 i−1. при некотором i 6 Это значит, что каждая из первых i + 50 кучек содержит не более i − 1 камня, то есть из нее удалено хотя бы 101 − i камней.
Поэтому общее количество удаленных камней не меньше, чем + 50)(101 − i) = 5100 − (i − 1)(i − 50) > 5100. Противоречие. Рассмотрим все 100-значные числа, делящиеся на 19. Докажите,
что количество таких чисел, не содержащих цифр 4, 5 и 6, равно количеству таких чисел, не содержащих цифр 1, 4 и И. Ефремов)
Решение. Каждому остатку a отделения на 19 сопоставим остаток b(a) такой, что b(a) ≡ 3a
(mod 19). Заметим, что остаткам 0, 1, 2, 3, 7, 8, 9 сопоставлены остатки 0, 3, 6, 9, 2, 5, 8 со
XLIX Всероссийская математическая олимпиада школьников ответственно. Более того, по остатку b восстанавливается остаток) такой, что a(b(a)) ≡ −18a ≡ a
(mod 19) и b(a(b)) = b (из аналогичных соображений).
Обозначим теперь через A множество чисел из условия, не содержащих цифра через B — множество таких чисел,
не содержащих 1, 4, 7. Каждому числу A =
a
99
a
98
. . . a
0
∈ A сопоставим число B = b(a
99
)b(a
98
) . . . b(a
0
). Заметим, что b(a i
) цифра (причем b(a
99
) 6= 0), так что получилось 100-значное число. Кроме того = b
0
+ 10b
1
+ . . . + 10 99
b
99
≡
≡ 3(a
0
+ 10a
1
+ . . . + 10 99
a
99
) = 3A
(mod так что B делится на 19 и B ∈ B. Поскольку разным числам из соответствуют разные числа из B, количество чисел вне меньше, чем в Наконец, каждому числу B =
b
99
b
98
. . . b
0
∈ B соответствует число A =
a(b
99
)a(b
98
) . . . a(b
0
), которое по аналогичным причинам лежит в A. Отсюда следует, что количества чисел в A и равны. Дана трапеция ABCD, в которой AD k BC, а лучи AB и пересекаются в точке G. Общие внешние касательные к окружностям, описанным около треугольников ABC и ACD, пересекаются в точке E. Общие внешние касательные к окружностям,
описанным около треугольников ABD и BCD, пересекаются в точке F . Докажите, что точки E, F и G лежат на одной пря- мой.
(А. Кузнецов)
Решение. Пусть прямая EC повторно пересекает окружность) в точке X, а прямая EA повторно пересекает окружность (ACD) в точке Y (мы разберем расположение точек, указанное на рис. 1; другие случаи рассматриваются ана- логично).
Рассмотрим гомотетию с центром E, переводящую (в (ACD). При такой гомотетии точка X переходит ваточка в Y . Отсюда AX k Y C и = ∠AY C − ∠ECY =
= ∠AY C − Но = 180
◦
− ∠ABC и ∠AY C = 180
◦
− ∠ADC. Значит. Из
Условия и решения задач класс. Если на столе лежит несколько кучек камней, считается, что на столе много камней, если можно найти 50 кучек и пронумеровать их числами от 1 до 50 так, что впервой кучке есть хотя бы один камень, во второй — хотя бы два камня, . . . , в пятидесятой хотя бы пятьдесят камней. Пусть исходно на столе лежат кучек по 100 камней в каждой. Найдите наибольшее n 6 10 000 такое, что после удаления из исходных кучек любых n камней на столе все равно останется много камней. (При удалении камней кучка не распадается на несколько.)
(Д. Храмцов)
Ответ. n = Решение. Если удалить полностью 51 кучку, то, очевидно,
не останется много камней. Значит, искомое значение n меньше. (Альтернативно, можно удалить из всех кучек по 51 кам- ню.)
Осталось показать, что при удалении любых n = 5099 камней останется много камней. Пусть в кучках осталось a
1
, a
2
, . . . камней соответственно можно считать, что 0 6 a
1 6 a
2 6
6 ... 6 a
100 6 100. Покажем, что a i+50
> i при i = 1, 2, . . . , то есть кучки с номерами от 51 до 100 удовлетворяют требова- ниям.
Пусть это не так, то есть a i+50 6 i−1. при некотором i 6 Это значит, что каждая из первых i + 50 кучек содержит не более i − 1 камня, то есть из нее удалено хотя бы 101 − i камней.
Поэтому общее количество удаленных камней не меньше, чем + 50)(101 − i) = 5100 − (i − 1)(i − 50) > 5100. Противоречие. Рассмотрим все 100-значные числа, делящиеся на 19. Докажите,
что количество таких чисел, не содержащих цифр 4, 5 и 6, равно количеству таких чисел, не содержащих цифр 1, 4 и И. Ефремов)
Решение. Каждому остатку a отделения на 19 сопоставим остаток b(a) такой, что b(a) ≡ 3a
(mod 19). Заметим, что остаткам 0, 1, 2, 3, 7, 8, 9 сопоставлены остатки 0, 3, 6, 9, 2, 5, 8 со
XLIX Всероссийская математическая олимпиада школьников ответственно. Более того, по остатку b восстанавливается остаток) такой, что a(b(a)) ≡ −18a ≡ a
(mod 19) и b(a(b)) = b (из аналогичных соображений).
Обозначим теперь через A множество чисел из условия, не содержащих цифра через B — множество таких чисел,
не содержащих 1, 4, 7. Каждому числу A =
a
99
a
98
. . . a
0
∈ A сопоставим число B = b(a
99
)b(a
98
) . . . b(a
0
). Заметим, что b(a i
) цифра (причем b(a
99
) 6= 0), так что получилось 100-значное число. Кроме того = b
0
+ 10b
1
+ . . . + 10 99
b
99
≡
≡ 3(a
0
+ 10a
1
+ . . . + 10 99
a
99
) = 3A
(mod так что B делится на 19 и B ∈ B. Поскольку разным числам из соответствуют разные числа из B, количество чисел вне меньше, чем в Наконец, каждому числу B =
b
99
b
98
. . . b
0
∈ B соответствует число A =
a(b
99
)a(b
98
) . . . a(b
0
), которое по аналогичным причинам лежит в A. Отсюда следует, что количества чисел в A и равны. Дана трапеция ABCD, в которой AD k BC, а лучи AB и пересекаются в точке G. Общие внешние касательные к окружностям, описанным около треугольников ABC и ACD, пересекаются в точке E. Общие внешние касательные к окружностям,
описанным около треугольников ABD и BCD, пересекаются в точке F . Докажите, что точки E, F и G лежат на одной пря- мой.
(А. Кузнецов)
Решение. Пусть прямая EC повторно пересекает окружность) в точке X, а прямая EA повторно пересекает окружность (ACD) в точке Y (мы разберем расположение точек, указанное на рис. 1; другие случаи рассматриваются ана- логично).
Рассмотрим гомотетию с центром E, переводящую (в (ACD). При такой гомотетии точка X переходит ваточка в Y . Отсюда AX k Y C и = ∠AY C − ∠ECY =
= ∠AY C − Но = 180
◦
− ∠ABC и ∠AY C = 180
◦
− ∠ADC. Значит. Из
Заключительный этап, 2022–2023 учебный год. Второй день
A
B
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
E
G
X
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Рис. полученного равенства следует, что точки A, C, E, G лежат на одной окружности.
Поскольку точка E лежит на серединном перпендикуляре к (те. на оси симметрии окружностей (ABC) иона является серединой дуги AGC окружности (ACEG). Значит, лежит на внешней биссектрисе угла Аналогично показывается, что F также лежит на внешней биссектрисе угла Замечание. У задачи есть следующее обобщение. Пусть — четырехугольника вторая точка пересечения окружностей (ADG) и (BCG) (иначе говоря, точка
Микеля этого четырехугольника. Пусть E — центр гомотетии с положительным коэффициентом, переводящей (ABC) в (Тогда точки A, C, M , E лежат на одной окружности, причем — середина дуги AC те биссектриса угла между и CM Доказать это можно аналогично решению решении задачи:
имеем (в направленных углах = ∠ABC + ∠ADC =
= ∠GBC + ∠AM G = ∠GM C + ∠AM G = ∠AM C.
9.8. У Пети есть 10 000 гирь, среди них нет двух гирь равного веса
XLIX Всероссийская математическая олимпиада школьников
Также у него есть чудо-прибор: если положить в него 10 гирь,
он сообщит сумму весов каких-то двух из них (при этом неизвестно, каких именно. Докажите, что Петя может использовать чудо-прибор так, чтобы через некоторое время указать на одну из гирь и точно назвать ее вес. (В чудо-прибор нельзя класть другое количество гирь.)
(С. Берлов, Т. Коротченко)
Решение. Покажем, что Петя сможет определить вес одной гири, даже если у него 8 000 гирь. Положим n = 4 Лемма. Для любых n гирь Петя может найти две гири,
для которых он знает их суммарный вес.
Доказательство. Пусть Петя положит в прибор по очереди всевозможные наборы из 10 гирь из наших n. Заметим, что каждое показание прибора — это вес какой-то из C
2
n пар гирь
(будем говорить, что это показание использует эту пару. В тоже время, Петя получит C
10
n показаний. Значит, одна из пар будет использована хотя бы =
C
10
n
C
2
n
=
(n − 2)(n − 3) . . . (n − 9)
3 · 4 · . . . · 10
раз.
Иначе говоря, найдутся D измерений таких, что (1) в них прибор показывает один и тот же веси) во всех десятках,
использованных в этих испытаниях, есть две общих гири a и Мы покажем, что при выполнении условий (1) и (2) суммарный веси обязательно равен S, то есть вес этой пары Петя и сможет определить по показаниям прибора. Назовем десятки гирь, участвовавшие в этих D измерениях, нужными.
Предположим противное сумма весов a и b неравна. Рассмотрим все пары из n гирь, суммарные веса в которых равны (назовем эти пары хорошими. Поскольку веса всех гирь различны, хорошие пары не пересекаются в частности, их не больше, чем n/2. При этом в каждой нужной десятке есть не только гири a и b, но и хотя бы одна хорошая пара. Оценим теперь общее количество нужных десяток.
Пусть в нужной десятке хорошая пара не содержит ни ни b. Любую такую десятку можно получить, добавив к гирями хорошую пару (не более чем (n − 2)/2 способами, а затем
XLIX Всероссийская математическая олимпиада школьников класс. Найдите наибольшее натуральное число n, для которого произведение чисел n, n + 1, n + 2, . . . , n + 20 делится на квадрат какого-то одного из них.
(А. Храбров)
Ответ. Решение. При n = 20! имеем n(n + 1)(n + 2) . . . (n + 20)
n
2
=
=
(n + 1)(n + 2) . . . (n + 20)
20!
= C
20
n+20
— целое число.
Пусть теперь n > 20! и пусть P = n(n + 1)(n + 2) . . . (n + делится на k
2
, где k = n + i, i ∈ {0, 1, 2, . . . , 20}. Имеем P/k =
= (k − i)(k − i + 1) . . . (k − 1)(k + 1)(k + 2) . . . (k + j), где j = 20 − Заметим, что число P/k ≡ (−1)
i i!j!
(mod k) должно делиться на k. Но 0 < i!j!
6 i!·(i+1)(i+2) . . . (i+j) = 20! < n 6 k, значит не делится на k. Противоречие. Квадрат 100 × 100 разбит на квадраты 2 × 2. Потом его разбивают на доминошки (прямоугольники 1 × 2 и 2 × 1). Какое наименьшее количество доминошек могло оказаться внутри квадратов разбиения?
(С. Берлов)
Ответ. 100.
Решение.
Пример. Верхнюю и нижнюю горизонтали разобьем на горизонтальные доминошки — они окажутся в квадратах. Остальной прямоугольник 98 × 100 разобьем на вертикальные доминошки — они не окажутся в квадратах 2 × Оценка. Рассмотрим квадраты A
1
, A
3
, . . . , размеров × 1, 3 × 3, . . . , 99 × 99, у которых левый нижний угол совпадает с левым нижним углом исходного квадрата 100 × 100. Для каждого из квадратов A
i
(i = 1, 3, 5, . . . , 99) найдется доминош- ка X
i
, пересекающая его сторону (поскольку квадраты нечетной площади не разбиваются на доминошки). Легко видеть, что X
i лежит внутри квадратика 2 × 2 из разбиения.
Аналогично, рассматривая квадраты B
1
, B
3
, . . . , размеров, у которых правый верхний угол совпадает с правым верхним углом исходного квадрата 100 × находим еще 50 нужных нам доминошек Y
j
(j = 1, 3, 5, . . . , Это завершает решение (очевидно, что все доминошки X
1
,
X
3
, . . . , X
99
, Y
1
, Y
3
, . . . , различны
A
B
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
E
G
X
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Рис. полученного равенства следует, что точки A, C, E, G лежат на одной окружности.
Поскольку точка E лежит на серединном перпендикуляре к (те. на оси симметрии окружностей (ABC) иона является серединой дуги AGC окружности (ACEG). Значит, лежит на внешней биссектрисе угла Аналогично показывается, что F также лежит на внешней биссектрисе угла Замечание. У задачи есть следующее обобщение. Пусть — четырехугольника вторая точка пересечения окружностей (ADG) и (BCG) (иначе говоря, точка
Микеля этого четырехугольника. Пусть E — центр гомотетии с положительным коэффициентом, переводящей (ABC) в (Тогда точки A, C, M , E лежат на одной окружности, причем — середина дуги AC те биссектриса угла между и CM Доказать это можно аналогично решению решении задачи:
имеем (в направленных углах = ∠ABC + ∠ADC =
= ∠GBC + ∠AM G = ∠GM C + ∠AM G = ∠AM C.
9.8. У Пети есть 10 000 гирь, среди них нет двух гирь равного веса
XLIX Всероссийская математическая олимпиада школьников
Также у него есть чудо-прибор: если положить в него 10 гирь,
он сообщит сумму весов каких-то двух из них (при этом неизвестно, каких именно. Докажите, что Петя может использовать чудо-прибор так, чтобы через некоторое время указать на одну из гирь и точно назвать ее вес. (В чудо-прибор нельзя класть другое количество гирь.)
(С. Берлов, Т. Коротченко)
Решение. Покажем, что Петя сможет определить вес одной гири, даже если у него 8 000 гирь. Положим n = 4 Лемма. Для любых n гирь Петя может найти две гири,
для которых он знает их суммарный вес.
Доказательство. Пусть Петя положит в прибор по очереди всевозможные наборы из 10 гирь из наших n. Заметим, что каждое показание прибора — это вес какой-то из C
2
n пар гирь
(будем говорить, что это показание использует эту пару. В тоже время, Петя получит C
10
n показаний. Значит, одна из пар будет использована хотя бы =
C
10
n
C
2
n
=
(n − 2)(n − 3) . . . (n − 9)
3 · 4 · . . . · 10
раз.
Иначе говоря, найдутся D измерений таких, что (1) в них прибор показывает один и тот же веси) во всех десятках,
использованных в этих испытаниях, есть две общих гири a и Мы покажем, что при выполнении условий (1) и (2) суммарный веси обязательно равен S, то есть вес этой пары Петя и сможет определить по показаниям прибора. Назовем десятки гирь, участвовавшие в этих D измерениях, нужными.
Предположим противное сумма весов a и b неравна. Рассмотрим все пары из n гирь, суммарные веса в которых равны (назовем эти пары хорошими. Поскольку веса всех гирь различны, хорошие пары не пересекаются в частности, их не больше, чем n/2. При этом в каждой нужной десятке есть не только гири a и b, но и хотя бы одна хорошая пара. Оценим теперь общее количество нужных десяток.
Пусть в нужной десятке хорошая пара не содержит ни ни b. Любую такую десятку можно получить, добавив к гирями хорошую пару (не более чем (n − 2)/2 способами, а затем
Заключительный этап, 2022–2023 учебный год. Второй день дополнив шестью из оставшихся n − 4 гирь. Итого, количество таких десяток не больше, чем n − 2 Во всех остальных нужных десятках хорошая пара содержит либо a, либо b. Если есть хорошая пара, содержащая a, то такая пара единственна. Для получения нужной десятки, содержащей эту пару, ее надо дополнить гирей b и еще семью гирями из оставшихся n − 3; итого, таких нужных десяток не больше. Аналогично, нужных десяток, содержащих хорошую парус гирей b, тоже не больше Итого, получаем 6
n − 2 2
C
6
n−4
+ 2C
7
n−3
=
= D ·
7 · 8 · 9 · 10 4(n − 3)
+
8 · 9 · 10
n − 2
< D ·
1 2
+
1 2
= D.
Противоречие.
Завершим решение задачи. Построим следующий граф. Сопоставим каждой гире вершину, Среди каждых n гирь найдем одну парус известной суммой две соответствующих вершины соединим ребром. Если в этом графе нет нечетных циклов, то,
как известно, его вершины можно раскрасить в два цвета так,
чтобы каждое ребро соединяло вершины разных цветов. Но тогда вершин одного цвета не меньше n, и потому среди них мы провели ребро противоречие.
Значит, в полученном графе есть цикл w
1
, w
2
, . . . , w
2k+1
, и
Петя знает суммарные веса всех пар соседних гирь в этом цикле.
Взяв полусумму всех этих весов, Петя узнает суммарный вес всех гирь цикла. Вычтя из него (w
2
+ w
3
) + (w
4
+ w
5
) + . . . +
+ (w
2k
+ w
2k+1
), он узнает вес гири Замечание. Оценивая чуть точнее, можно доказать лемму даже при n = 2 000.
7
n − 2 2
C
6
n−4
+ 2C
7
n−3
=
= D ·
7 · 8 · 9 · 10 4(n − 3)
+
8 · 9 · 10
n − 2
< D ·
1 2
+
1 2
= D.
Противоречие.
Завершим решение задачи. Построим следующий граф. Сопоставим каждой гире вершину, Среди каждых n гирь найдем одну парус известной суммой две соответствующих вершины соединим ребром. Если в этом графе нет нечетных циклов, то,
как известно, его вершины можно раскрасить в два цвета так,
чтобы каждое ребро соединяло вершины разных цветов. Но тогда вершин одного цвета не меньше n, и потому среди них мы провели ребро противоречие.
Значит, в полученном графе есть цикл w
1
, w
2
, . . . , w
2k+1
, и
Петя знает суммарные веса всех пар соседних гирь в этом цикле.
Взяв полусумму всех этих весов, Петя узнает суммарный вес всех гирь цикла. Вычтя из него (w
2
+ w
3
) + (w
4
+ w
5
) + . . . +
+ (w
2k
+ w
2k+1
), он узнает вес гири Замечание. Оценивая чуть точнее, можно доказать лемму даже при n = 2 000.
7
XLIX Всероссийская математическая олимпиада школьников класс. Найдите наибольшее натуральное число n, для которого произведение чисел n, n + 1, n + 2, . . . , n + 20 делится на квадрат какого-то одного из них.
(А. Храбров)
Ответ. Решение. При n = 20! имеем n(n + 1)(n + 2) . . . (n + 20)
n
2
=
=
(n + 1)(n + 2) . . . (n + 20)
20!
= C
20
n+20
— целое число.
Пусть теперь n > 20! и пусть P = n(n + 1)(n + 2) . . . (n + делится на k
2
, где k = n + i, i ∈ {0, 1, 2, . . . , 20}. Имеем P/k =
= (k − i)(k − i + 1) . . . (k − 1)(k + 1)(k + 2) . . . (k + j), где j = 20 − Заметим, что число P/k ≡ (−1)
i i!j!
(mod k) должно делиться на k. Но 0 < i!j!
6 i!·(i+1)(i+2) . . . (i+j) = 20! < n 6 k, значит не делится на k. Противоречие. Квадрат 100 × 100 разбит на квадраты 2 × 2. Потом его разбивают на доминошки (прямоугольники 1 × 2 и 2 × 1). Какое наименьшее количество доминошек могло оказаться внутри квадратов разбиения?
(С. Берлов)
Ответ. 100.
Решение.
Пример. Верхнюю и нижнюю горизонтали разобьем на горизонтальные доминошки — они окажутся в квадратах. Остальной прямоугольник 98 × 100 разобьем на вертикальные доминошки — они не окажутся в квадратах 2 × Оценка. Рассмотрим квадраты A
1
, A
3
, . . . , размеров × 1, 3 × 3, . . . , 99 × 99, у которых левый нижний угол совпадает с левым нижним углом исходного квадрата 100 × 100. Для каждого из квадратов A
i
(i = 1, 3, 5, . . . , 99) найдется доминош- ка X
i
, пересекающая его сторону (поскольку квадраты нечетной площади не разбиваются на доминошки). Легко видеть, что X
i лежит внутри квадратика 2 × 2 из разбиения.
Аналогично, рассматривая квадраты B
1
, B
3
, . . . , размеров, у которых правый верхний угол совпадает с правым верхним углом исходного квадрата 100 × находим еще 50 нужных нам доминошек Y
j
(j = 1, 3, 5, . . . , Это завершает решение (очевидно, что все доминошки X
1
,
X
3
, . . . , X
99
, Y
1
, Y
3
, . . . , различны
Заключительный этап, 2022–2023 учебный год. Второй день
Замечание. Приведем схему несколько другого доказательства оценки.
Пусть внутри квадратов 2 × 2 оказалось не более 99 доми- ношек.
Провед¨
ем 50 вертикальных линий сетки v
1
, v
3
, v
5
, . . . , так, что v отделяет i столбцов слева. Легко видеть, что любая доминошка, пересекаемая одной из линий v
1
, v
3
, v
5
, . . . , v
99
, нам подходит. Каждая вертикальная линия пересекает четное количество доминошек, так как слева от этой линии четное количество клеток. Значит, среди линий v
1
, v
3
, v
5
, . . . , есть линия v
i
, не пересекающая доминошек, иначе мы уже нашли хотя бы · 50 = 100 нужных нам доминошек. Проведем аналогичное рассуждение для 50 горизонтальных линий сетки h
1
, h
3
, h
5
, . . . , и найдем среди них линию h j
, не пересекающую доминошек. Но v
i и h делят доску на области с нечетным количеством клеток,
поэтому хотя бы одна из этих двух линий обязана пересекать доминошку. Противоречие. Дана трапеция ABCD, в которой AD k BC, а лучи AB и пересекаются в точке G. Общие внешние касательные к окружностям, описанным около треугольников ABC и ACD, пересекаются в точке E. Общие внешние касательные к окружностям,
описанным около треугольников ABD и BCD, пересекаются в точке F . Докажите, что точки E, F и G лежат на одной пря- мой.
(А. Кузнецов)
Решение. Пусть прямая EC повторно пересекает окружность) в точке X, а прямая EA повторно пересекает окружность (ACD) в точке Y (мы разберем расположение точек, указанное на рис. 2; другие случаи рассматриваются ана- логично).
Рассмотрим гомотетию с центром E, переводящую (в (ACD). При такой гомотетии точка X переходит ваточка в Y . Отсюда AX k Y C и = ∠AY C − ∠ECY =
= ∠AY C − Но = 180
◦
− ∠ABC и ∠AY C = 180
◦
− ∠ADC. Значит. Из полученного равенства следует, что точки A, C, E, G лежат на одной окружности
XLIX Всероссийская математическая олимпиада школьников
A
B
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
E
G
X
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Рис. Поскольку точка E лежит на серединном перпендикуляре к (те. на оси симметрии окружностей (ABC) иона является серединой дуги AGC окружности (ACEG). Значит, лежит на внешней биссектрисе угла Аналогично показывается, что F также лежит на внешней биссектрисе угла Замечание. У задачи есть следующее обобщение. Пусть — четырехугольника вторая точка пересечения окружностей (ADG) и (BCG) (иначе говоря, точка
Микеля этого четырехугольника. Пусть E — центр гомотетии с положительным коэффициентом, переводящей (ABC) в (Тогда точки A, C, M , E лежат на одной окружности, причем — середина дуги AC те биссектриса угла между и CM Доказать это можно аналогично решению решении задачи:
имеем (в направленных углах = ∠ABC + ∠ADC =
= ∠GBC + ∠AM G = ∠GM C + ∠AM G = ∠AM C.
10.8. Дано число a ∈ (0, 1). Положительные числа x
0
, x
1
, . . ., x удовлетворяют условиями Заключительный этап, 2022–2023 учебный год. Второй день+ . . . +
1
x n
= n +
1
a
. Найдите наименьшее значение выражения x
2 0
+ x
2 1
+ . . . + А. Храбров)
Ответ. n + Решение. Заметим, что равенство достигается при x
0
= a и x
1
= . . . = x n
= Запишем x
2
k
=
P(1−x k
)
2
+2
P x k
−(n+1) =
P(1−x k
)
2
+
+ n − 1 + 2a. Достаточно доказать, что − x k
)
2
> (1 − Пусть x
0
— наименьшее из чисел.
При x
0 6 a имеем − x k
)
2
> (1 − x
0
)
2
> (1 − Если же x
0
> a, то − x k
)
2
=
P x k
1
x k
− 2 + x что, поскольку выражения в скобках неотрицательны, не меньше, чем a
P
1
x k
− 2 + x k
= a
n +
1
a
− 2(n + 1) + n + a
=
= a
1
a
− 2 + a
= (a − 1)
2 11
XLIX Всероссийская математическая олимпиада школьников класс. Изначально на доске написано 10 единиц. Гриша и Глеб играют в игру, делая ходы по очереди. Своим ходом Гриша возводит некоторые 5 чисел на доске в квадрат. Глеб своим ходом выбирает несколько (возможно, ни одного) чисел на доске и увеличивает каждое из них на 1. Если в течение 10 000 ходов на доске появится число, делящееся на 2023, то побеждает Глеб, иначе побеждает Гриша. Кто из игроков имеет выигрышную стратегию, если первым ходит Гриша?
(Г. Никитин)
Ответ. Побеждает Гриша.
Решение. Заметим, что 2023 = 7 · 17 2
. Гриша разобьет числа на доске на две группы пои будет возводить в квадрат числа из первой группы и из второй группы по очереди. Легко видеть, что квадраты целых чисел, не кратных 7, при делении на 7 могут давать лишь остатки 1, 2 и 4. Следовательно, после увеличения максимум на 2 числа на доске будут давать при делении на 7 только остатки 1, 2, 3, 4, 5 и 6. Значит, ни одно из чисел не будет делиться 7, а поэтому не будет делиться и на
2023.
Замечание. Существуют и другие решения. Плоскость α пересекает ребра AB, BC, CD и DA тетраэдра в точках X, Y , Z и T соответственно. Оказалось, что точки Y и T лежат на окружности ω, построенной на отрезке как на диаметре. Точка P отмечена в плоскости α так, что прямые P Y и P T касаются окружности ω. Докажите, что середины ребер AB, BC, CD, DA и точка P лежат водной плоско- сти.
(А. Кузнецов)
Решение. Из условия задачи мы сразу получаем, что Z = 90
◦
= ∠XT Z. Обозначим через Q точку пересечения прямых XY и ZT , через R — точку пересечения прямых ZY и (см. рис. 3). Без ограничения общности можно считать, что точка Z лежит на отрезках RY и QT . Поскольку точка R лежит ив плоскости ABD, ив плоскости BCD, то она лежит на прямой BD. Аналогично, точка Q лежит на прямой Заметим, что RY и QT — высоты треугольника XQR. Тогда точка пересечения высот этого треугольника, и по
Замечание. Приведем схему несколько другого доказательства оценки.
Пусть внутри квадратов 2 × 2 оказалось не более 99 доми- ношек.
Провед¨
ем 50 вертикальных линий сетки v
1
, v
3
, v
5
, . . . , так, что v отделяет i столбцов слева. Легко видеть, что любая доминошка, пересекаемая одной из линий v
1
, v
3
, v
5
, . . . , v
99
, нам подходит. Каждая вертикальная линия пересекает четное количество доминошек, так как слева от этой линии четное количество клеток. Значит, среди линий v
1
, v
3
, v
5
, . . . , есть линия v
i
, не пересекающая доминошек, иначе мы уже нашли хотя бы · 50 = 100 нужных нам доминошек. Проведем аналогичное рассуждение для 50 горизонтальных линий сетки h
1
, h
3
, h
5
, . . . , и найдем среди них линию h j
, не пересекающую доминошек. Но v
i и h делят доску на области с нечетным количеством клеток,
поэтому хотя бы одна из этих двух линий обязана пересекать доминошку. Противоречие. Дана трапеция ABCD, в которой AD k BC, а лучи AB и пересекаются в точке G. Общие внешние касательные к окружностям, описанным около треугольников ABC и ACD, пересекаются в точке E. Общие внешние касательные к окружностям,
описанным около треугольников ABD и BCD, пересекаются в точке F . Докажите, что точки E, F и G лежат на одной пря- мой.
(А. Кузнецов)
Решение. Пусть прямая EC повторно пересекает окружность) в точке X, а прямая EA повторно пересекает окружность (ACD) в точке Y (мы разберем расположение точек, указанное на рис. 2; другие случаи рассматриваются ана- логично).
Рассмотрим гомотетию с центром E, переводящую (в (ACD). При такой гомотетии точка X переходит ваточка в Y . Отсюда AX k Y C и = ∠AY C − ∠ECY =
= ∠AY C − Но = 180
◦
− ∠ABC и ∠AY C = 180
◦
− ∠ADC. Значит. Из полученного равенства следует, что точки A, C, E, G лежат на одной окружности
XLIX Всероссийская математическая олимпиада школьников
A
B
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
D
E
G
X
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Рис. Поскольку точка E лежит на серединном перпендикуляре к (те. на оси симметрии окружностей (ABC) иона является серединой дуги AGC окружности (ACEG). Значит, лежит на внешней биссектрисе угла Аналогично показывается, что F также лежит на внешней биссектрисе угла Замечание. У задачи есть следующее обобщение. Пусть — четырехугольника вторая точка пересечения окружностей (ADG) и (BCG) (иначе говоря, точка
Микеля этого четырехугольника. Пусть E — центр гомотетии с положительным коэффициентом, переводящей (ABC) в (Тогда точки A, C, M , E лежат на одной окружности, причем — середина дуги AC те биссектриса угла между и CM Доказать это можно аналогично решению решении задачи:
имеем (в направленных углах = ∠ABC + ∠ADC =
= ∠GBC + ∠AM G = ∠GM C + ∠AM G = ∠AM C.
10.8. Дано число a ∈ (0, 1). Положительные числа x
0
, x
1
, . . ., x удовлетворяют условиями Заключительный этап, 2022–2023 учебный год. Второй день+ . . . +
1
x n
= n +
1
a
. Найдите наименьшее значение выражения x
2 0
+ x
2 1
+ . . . + А. Храбров)
Ответ. n + Решение. Заметим, что равенство достигается при x
0
= a и x
1
= . . . = x n
= Запишем x
2
k
=
P(1−x k
)
2
+2
P x k
−(n+1) =
P(1−x k
)
2
+
+ n − 1 + 2a. Достаточно доказать, что − x k
)
2
> (1 − Пусть x
0
— наименьшее из чисел.
При x
0 6 a имеем − x k
)
2
> (1 − x
0
)
2
> (1 − Если же x
0
> a, то − x k
)
2
=
P x k
1
x k
− 2 + x что, поскольку выражения в скобках неотрицательны, не меньше, чем a
P
1
x k
− 2 + x k
= a
n +
1
a
− 2(n + 1) + n + a
=
= a
1
a
− 2 + a
= (a − 1)
2 11
XLIX Всероссийская математическая олимпиада школьников класс. Изначально на доске написано 10 единиц. Гриша и Глеб играют в игру, делая ходы по очереди. Своим ходом Гриша возводит некоторые 5 чисел на доске в квадрат. Глеб своим ходом выбирает несколько (возможно, ни одного) чисел на доске и увеличивает каждое из них на 1. Если в течение 10 000 ходов на доске появится число, делящееся на 2023, то побеждает Глеб, иначе побеждает Гриша. Кто из игроков имеет выигрышную стратегию, если первым ходит Гриша?
(Г. Никитин)
Ответ. Побеждает Гриша.
Решение. Заметим, что 2023 = 7 · 17 2
. Гриша разобьет числа на доске на две группы пои будет возводить в квадрат числа из первой группы и из второй группы по очереди. Легко видеть, что квадраты целых чисел, не кратных 7, при делении на 7 могут давать лишь остатки 1, 2 и 4. Следовательно, после увеличения максимум на 2 числа на доске будут давать при делении на 7 только остатки 1, 2, 3, 4, 5 и 6. Значит, ни одно из чисел не будет делиться 7, а поэтому не будет делиться и на
2023.
Замечание. Существуют и другие решения. Плоскость α пересекает ребра AB, BC, CD и DA тетраэдра в точках X, Y , Z и T соответственно. Оказалось, что точки Y и T лежат на окружности ω, построенной на отрезке как на диаметре. Точка P отмечена в плоскости α так, что прямые P Y и P T касаются окружности ω. Докажите, что середины ребер AB, BC, CD, DA и точка P лежат водной плоско- сти.
(А. Кузнецов)
Решение. Из условия задачи мы сразу получаем, что Z = 90
◦
= ∠XT Z. Обозначим через Q точку пересечения прямых XY и ZT , через R — точку пересечения прямых ZY и (см. рис. 3). Без ограничения общности можно считать, что точка Z лежит на отрезках RY и QT . Поскольку точка R лежит ив плоскости ABD, ив плоскости BCD, то она лежит на прямой BD. Аналогично, точка Q лежит на прямой Заметим, что RY и QT — высоты треугольника XQR. Тогда точка пересечения высот этого треугольника, и по
Заключительный этап, 2022–2023 учебный год. Второй день = Рис. Рис. этому XZ ⊥ QR. Пусть M — середина отрезка QR. Поскольку, то Y M = M R = RQ по свойству медианы прямоугольного треугольника. Значит Y R = ∠Y RQ =
= 90
◦
− ∠XQR = ∠ZXQ. Следовательно, прямая Y M касается окружности ω. Аналогично, прямая T M тоже касается окружности, поэтому точки M и P совпадают.
Рассмотрим две параллельные плоскости β и γ, одна из которых содержит отрезок AC, а другая — отрезок BD. Заметим,
что середины всех отрезков, соединяющих точку из плоскости и точку из плоскости γ, лежат водной плоскости, параллельной и γ. Действительно, если ввести декартовы координаты так,
что одна из плоскостей задается уравнением z = 0, а другая уравнением z = h (где h есть расстояние между плоскостями и γ), то середины всех рассматриваемых отрезков лежат в плоскости z = h/2. Применяя это наблюдение для отрезков AB,
BC, CD, DA, QR, мы получаем, что их середины лежат водной плоскости, что и требовалось. Назовем многочлен P (x) бицелозначным, если числа P (k) и) целые при любом целом k. Пусть P (x) — бицелозначный многочлен степени d, и пусть N
d
— произведение всех составных чисел, не превосходящих d (произведение пустого множества сомножителей считаем равным 1). Докажите, что старший коэффициент многочлена N
d
· P (x) — целый.
(И. Богданов, Г. Челноков)
Решение. Многочлен P (x) называется целозначным, если
XLIX Всероссийская математическая олимпиада школьников (k) — целое число при любом целом k. Нам надо доказать, что,
если многочлены P (x) и P
0
(x) целозначны, причем степень P (равна d, то старший коэффициент многочлена N
d
·P (x) — целый.
Лемма. Пусть P (x) — целозначный многочлен степени Тогда все коэффициенты многочлена d! · P (x) целые.
Доказательство. Рассмотрим многочлен) =
n
X
i=0
P (i)·
(x − 0)(x − 1) . . . (x − (i − 1))(x − (i + 1)) . . . (x − d)
(i − 0)(i − 1) . . . (i − (i − 1))(i − (i + 1)) . . . (i − Его степень не больше d, и его значения совпадают с соответствующими значениями P (x) в точках x = 0, 1, 2, . . . , d. Это означает, что многочлен P (x) − Q(x) имеет степень не выше а также обнуляется в d + 1 точке. Поэтому он нулевой, то есть (x) = Q(x). (Формула выше — это частный случай интерполяционной формулы Лагранжа.)
Осталось заметить, что в формуле выше в м слагаемом знаменатель равен (−1)
d−i i!(d − i)!; это число делит d!, поскольку. Значит, приумножении каждого слагаемого на d! получается многочлен с целыми коэффициентами.
Перейд¨
ем к решению задачи. Индукция по d. База при d = тривиальна. Для перехода индукции рассмотрим бицелознач- ный многочлен P (x) степени d; пусть его старший коэффициент равен Если d не является простым числом, то N
d
= dN
d−1
. Заметим, что многочлен ∆P (x) = P (x + 1) − P (x) также бицелознач- ный, имеет степень d − 1 и старший коэффициент ad. По предположению индукции, число N
d−1
· ad = N
d a является целым,
что и требовалось доказать.
Пусть теперь d — простое число тогда N
d
= N
d−1
, и тоже рассуждение дает, что число dN
d a является целым. Предположим, что N
d a — нецелое число тогда знаменатель числа a (в несократимой записи) делится на простое число d.
Заметим,
что сумма всех коэффициентов многочлена (x) — это целое число P (1). Поскольку знаменатель числа a делится на d, среди коэффициентов многочлена P (x) найдется еще один, у которого знаменатель делится на d; пусть это коэф-
14
= 90
◦
− ∠XQR = ∠ZXQ. Следовательно, прямая Y M касается окружности ω. Аналогично, прямая T M тоже касается окружности, поэтому точки M и P совпадают.
Рассмотрим две параллельные плоскости β и γ, одна из которых содержит отрезок AC, а другая — отрезок BD. Заметим,
что середины всех отрезков, соединяющих точку из плоскости и точку из плоскости γ, лежат водной плоскости, параллельной и γ. Действительно, если ввести декартовы координаты так,
что одна из плоскостей задается уравнением z = 0, а другая уравнением z = h (где h есть расстояние между плоскостями и γ), то середины всех рассматриваемых отрезков лежат в плоскости z = h/2. Применяя это наблюдение для отрезков AB,
BC, CD, DA, QR, мы получаем, что их середины лежат водной плоскости, что и требовалось. Назовем многочлен P (x) бицелозначным, если числа P (k) и) целые при любом целом k. Пусть P (x) — бицелозначный многочлен степени d, и пусть N
d
— произведение всех составных чисел, не превосходящих d (произведение пустого множества сомножителей считаем равным 1). Докажите, что старший коэффициент многочлена N
d
· P (x) — целый.
(И. Богданов, Г. Челноков)
Решение. Многочлен P (x) называется целозначным, если
XLIX Всероссийская математическая олимпиада школьников (k) — целое число при любом целом k. Нам надо доказать, что,
если многочлены P (x) и P
0
(x) целозначны, причем степень P (равна d, то старший коэффициент многочлена N
d
·P (x) — целый.
Лемма. Пусть P (x) — целозначный многочлен степени Тогда все коэффициенты многочлена d! · P (x) целые.
Доказательство. Рассмотрим многочлен) =
n
X
i=0
P (i)·
(x − 0)(x − 1) . . . (x − (i − 1))(x − (i + 1)) . . . (x − d)
(i − 0)(i − 1) . . . (i − (i − 1))(i − (i + 1)) . . . (i − Его степень не больше d, и его значения совпадают с соответствующими значениями P (x) в точках x = 0, 1, 2, . . . , d. Это означает, что многочлен P (x) − Q(x) имеет степень не выше а также обнуляется в d + 1 точке. Поэтому он нулевой, то есть (x) = Q(x). (Формула выше — это частный случай интерполяционной формулы Лагранжа.)
Осталось заметить, что в формуле выше в м слагаемом знаменатель равен (−1)
d−i i!(d − i)!; это число делит d!, поскольку. Значит, приумножении каждого слагаемого на d! получается многочлен с целыми коэффициентами.
Перейд¨
ем к решению задачи. Индукция по d. База при d = тривиальна. Для перехода индукции рассмотрим бицелознач- ный многочлен P (x) степени d; пусть его старший коэффициент равен Если d не является простым числом, то N
d
= dN
d−1
. Заметим, что многочлен ∆P (x) = P (x + 1) − P (x) также бицелознач- ный, имеет степень d − 1 и старший коэффициент ad. По предположению индукции, число N
d−1
· ad = N
d a является целым,
что и требовалось доказать.
Пусть теперь d — простое число тогда N
d
= N
d−1
, и тоже рассуждение дает, что число dN
d a является целым. Предположим, что N
d a — нецелое число тогда знаменатель числа a (в несократимой записи) делится на простое число d.
Заметим,
что сумма всех коэффициентов многочлена (x) — это целое число P (1). Поскольку знаменатель числа a делится на d, среди коэффициентов многочлена P (x) найдется еще один, у которого знаменатель делится на d; пусть это коэф-
14
Заключительный этап, 2022–2023 учебный год. Второй день фициент b при x i
, i < d. Заметим, что i > 0, так как число P (0)
целое.
Но тогда у целозначного многочлена P
0
(x) коэффициент при x равен ib и также имеет знаменатель, кратный d. Поскольку простое число, отсюда вытекает, что коэффициент при x у многочлена (d − 1)!P
0
(x) нецелый, что противоречит лемме.
Замечание 1. Случай простого d можно разобрать и другими способами. Приведем один из них.
Предположим, что число dN
d a целое, а N
d a — нет, так что a = t/d для некоторого целого t, не кратного d. Рассмотрим многочлен) = N
d
P (x) − N
d a · (x − 1)(x − 2) . . . (x − Он целозначен, поскольку при любом целом k число (k − 1)(k −
−2) . . . (k−d) делится на d!. Кроме того, его степень меньше d. Из леммы вытекает, что знаменатели коэффициентов многочлена) не делятся на Рассмотрим теперь целое число c = N
d
P
0
(d). Из формулы) нетрудно получить, что c = Q
0
(d) +
t d
· (d − 1)(d − 2) . . . (d − (d − При этом первое слагаемое — это несократимая дробь со знаменателем, не делящимся на d, а второе — с делящимся. Это невозможно для целого Замечание Как доказали D. Brizolis и E. G. наименьшее N , для которого старший коэффициент многочлена) обязательно целый, равно d!
Q
p p
−k(p,d)
, где произведение берется по всем простым p, а k(p, d) — это наибольшее целое неотрицательное число k, для которого верно неравенство kp k
− (k − 1)p k−1 6 d.
11.8. В стране N городов. В ней действует N (N − 1) дорог с односторонним движением по одной дороге изв для каждой упорядоченной пары городов X 6= Y . У каждой дороги есть цена ее обслуживания. Для данного k = 1, . . . , N рассмотрим все способы выделить k городов и N − k дорог так, чтобы из каждого города можно было попасть в какой-то выделенный город
XLIX Всероссийская математическая олимпиада школьников пользуясь только выделенными дорогами. Такую систему городов и дорог с наименьшей суммарной стоимостью обслуживания назовем оптимальной. Докажите, что города можно пронумеровать от 1 до N так, что при каждом k = 1, 2, . . . , N существует оптимальная система дорог с выделенными городами, 2, . . . , В. Буслов)
Решение. Рассматриваемые сети из N − k дорог называем далее сетями. Рассмотрим неориентированный граф, образованный дорогами сети. В нем не более чем k компонент связности, поскольку в каждой есть выделенный город. С другой стороны, компонент не менее k, поскольку ребер всего не более чем N − k. Поэтому компонент ровно k, каждая из них есть дерево, содержит единственный выделенный городи вспоминая про ориентацию — ребра каждого дерева направлены по направлению к выделенному городу. В частности, из каждого не выделенного города должна выходить ровно одна дорога, а из выделенного 0 дорог.
Рассмотрим (k + оптимальную сеть A с выделенными городами и оптимальную сеть B с выделенными городами x
1
, . . . , x k
. Не умаляя общности, ни из одного x нельзя добраться в сети A до города y
0
. Пусть U — множество городов, из которых в A можно добраться до y
0
, а α, β — множества дорог, выходящих изв сетях A, B соответственно. Имеем = |U | − 1, |β| = |U Рассмотрим сеть D := (A \ α) ∪ β. Утверждается, что это сеть для выделенных городов y
1
, . . . , y k
. В самом деле, число дорог в ней равно |D| = N − k − 1 − (|U | − 1) + |U | = N − Из каждого города, кроме y
1
, . . . , y выходит ровно одна дорога. Выезжая из любого города вне U и используя дороги сети,
мы по-прежнему можем попасть в один из городов y
1
, . . . , y Выезжая из города в U , мы либо попадаем вне U — и далее в один из городов y
1
, . . . , y k
, — либо зацикливаемся в U . Но тогда содержит цикл, что невозможно.
Рассмотрим сеть C := (B \ β) ∪ α. Утверждается, что это
(k+1)-сеть для выделенных городов x
1
, . . . , x k
, y
0
. В самом деле = n − k − 1, и выезжая из любого города по дорогам сети, мы либо попадаем в U — и тогда по α доезжаем до y
0
, — либо
, i < d. Заметим, что i > 0, так как число P (0)
целое.
Но тогда у целозначного многочлена P
0
(x) коэффициент при x равен ib и также имеет знаменатель, кратный d. Поскольку простое число, отсюда вытекает, что коэффициент при x у многочлена (d − 1)!P
0
(x) нецелый, что противоречит лемме.
Замечание 1. Случай простого d можно разобрать и другими способами. Приведем один из них.
Предположим, что число dN
d a целое, а N
d a — нет, так что a = t/d для некоторого целого t, не кратного d. Рассмотрим многочлен) = N
d
P (x) − N
d a · (x − 1)(x − 2) . . . (x − Он целозначен, поскольку при любом целом k число (k − 1)(k −
−2) . . . (k−d) делится на d!. Кроме того, его степень меньше d. Из леммы вытекает, что знаменатели коэффициентов многочлена) не делятся на Рассмотрим теперь целое число c = N
d
P
0
(d). Из формулы) нетрудно получить, что c = Q
0
(d) +
t d
· (d − 1)(d − 2) . . . (d − (d − При этом первое слагаемое — это несократимая дробь со знаменателем, не делящимся на d, а второе — с делящимся. Это невозможно для целого Замечание Как доказали D. Brizolis и E. G. наименьшее N , для которого старший коэффициент многочлена) обязательно целый, равно d!
Q
p p
−k(p,d)
, где произведение берется по всем простым p, а k(p, d) — это наибольшее целое неотрицательное число k, для которого верно неравенство kp k
− (k − 1)p k−1 6 d.
11.8. В стране N городов. В ней действует N (N − 1) дорог с односторонним движением по одной дороге изв для каждой упорядоченной пары городов X 6= Y . У каждой дороги есть цена ее обслуживания. Для данного k = 1, . . . , N рассмотрим все способы выделить k городов и N − k дорог так, чтобы из каждого города можно было попасть в какой-то выделенный город
XLIX Всероссийская математическая олимпиада школьников пользуясь только выделенными дорогами. Такую систему городов и дорог с наименьшей суммарной стоимостью обслуживания назовем оптимальной. Докажите, что города можно пронумеровать от 1 до N так, что при каждом k = 1, 2, . . . , N существует оптимальная система дорог с выделенными городами, 2, . . . , В. Буслов)
Решение. Рассматриваемые сети из N − k дорог называем далее сетями. Рассмотрим неориентированный граф, образованный дорогами сети. В нем не более чем k компонент связности, поскольку в каждой есть выделенный город. С другой стороны, компонент не менее k, поскольку ребер всего не более чем N − k. Поэтому компонент ровно k, каждая из них есть дерево, содержит единственный выделенный городи вспоминая про ориентацию — ребра каждого дерева направлены по направлению к выделенному городу. В частности, из каждого не выделенного города должна выходить ровно одна дорога, а из выделенного 0 дорог.
Рассмотрим (k + оптимальную сеть A с выделенными городами и оптимальную сеть B с выделенными городами x
1
, . . . , x k
. Не умаляя общности, ни из одного x нельзя добраться в сети A до города y
0
. Пусть U — множество городов, из которых в A можно добраться до y
0
, а α, β — множества дорог, выходящих изв сетях A, B соответственно. Имеем = |U | − 1, |β| = |U Рассмотрим сеть D := (A \ α) ∪ β. Утверждается, что это сеть для выделенных городов y
1
, . . . , y k
. В самом деле, число дорог в ней равно |D| = N − k − 1 − (|U | − 1) + |U | = N − Из каждого города, кроме y
1
, . . . , y выходит ровно одна дорога. Выезжая из любого города вне U и используя дороги сети,
мы по-прежнему можем попасть в один из городов y
1
, . . . , y Выезжая из города в U , мы либо попадаем вне U — и далее в один из городов y
1
, . . . , y k
, — либо зацикливаемся в U . Но тогда содержит цикл, что невозможно.
Рассмотрим сеть C := (B \ β) ∪ α. Утверждается, что это
(k+1)-сеть для выделенных городов x
1
, . . . , x k
, y
0
. В самом деле = n − k − 1, и выезжая из любого города по дорогам сети, мы либо попадаем в U — и тогда по α доезжаем до y
0
, — либо
Заключительный этап, 2022–2023 учебный год. Второй день ни разу не попадаем в U и тогда доезжаем до одного из городов x
1
, . . . , x Итак, C, D — сеть и (k + сеть. Сумма их стоимостей такая же, как у A и B. Значит, они обе оптимальны. Таким образом, для сети A удалось выкинуть выделенный городи найти оптимальную сеть с оставшимися выделенными городами.
Теперь можно построить требуемую нумерацию в обратном порядке (начиная с пустой N -сети
1
, . . . , x Итак, C, D — сеть и (k + сеть. Сумма их стоимостей такая же, как у A и B. Значит, они обе оптимальны. Таким образом, для сети A удалось выкинуть выделенный городи найти оптимальную сеть с оставшимися выделенными городами.
Теперь можно построить требуемую нумерацию в обратном порядке (начиная с пустой N -сети