Я сам решу.
А застряну — спрошу.

Решение.
Лемма. 𝑎 = 𝑎 𝑎 + 𝑠𝑎 𝑎 при натуральных 𝑛 и 𝑘.
𝑛+𝑘 𝑛+1 𝑘 𝑛 𝑘−1
Доказательство: Будем действовать индукцией по 𝑘 при фиксированном 𝑛.
База: 𝑘 = 1,𝑎 = 𝑎 𝑎 + 𝑠𝑎 𝑎 , что верно при 𝑎 = 0 и 𝑎 = 1.
𝑛+1 𝑛+1 1 𝑛 0 0 1
𝑘 = 2,𝑎 = 𝑎 𝑎 + 𝑠𝑎 𝑎 , что напрямую следует из условия рекурренты и 𝑎 = 𝑟,
𝑛+2 𝑛+1 2 𝑛 1 2
𝑎 = 1.
1
Переход: сделаем переход от чисел 𝑘 и 𝑘 + 1 к числу 𝑘 + 2. Из предположения индукции
имеем:𝑎 = 𝑎 𝑎 +𝑠𝑎 𝑎 ,𝑎 = 𝑎 𝑎 +𝑠𝑎 𝑎 .Домноживпервоетождество
𝑛+𝑘 𝑛+1 𝑘 𝑛 𝑘−1 𝑛+𝑘+1 𝑛+1 𝑘+1 𝑛 𝑘
на 𝑠, а второе на 𝑟, сложим их: 𝑠𝑎 +𝑟𝑎 = 𝑠𝑎 𝑎 +𝑠2𝑎 𝑎 +𝑟𝑎 𝑎 +𝑟𝑠𝑎 𝑎 .
𝑛+𝑘 𝑛+𝑘+1 𝑛+1 𝑘 𝑛 𝑘−1 𝑛+1 𝑘+1 𝑛 𝑘
Тогда левая часть из условия равна 𝑎 , а правая после перегруппировки слагаемых
𝑛+𝑘+2
𝑎 (𝑟𝑎 + 𝑠𝑎 ) + 𝑠𝑎 (𝑟𝑎 + 𝑠𝑎 ) = 𝑎 𝑎 + 𝑠𝑎 𝑎 .
𝑛+1 𝑘+1 𝑘 𝑛 𝑘 𝑘−1 𝑛+1 𝑘+2 𝑛 𝑘+1
Заметим, что
𝑓𝑚+𝑛
= 𝑎 ⋅ 𝑎 ⋯𝑎 . Тогда нужно доказать, что 𝑎 ⋅ 𝑎 ⋯𝑎 ∣ 𝑎 ⋅
𝑛+1 𝑛+2 𝑚+𝑛 1 2 𝑚 𝑛+1
𝑓𝑛
𝑎 ⋯𝑎 . Докажем это утверждение индукцией по m+n.
𝑛+2 𝑚+𝑛
База:
• 𝑚 = 1 – очевидно, 𝑛 = 1 – очевидно.
Переход : сделаем переход к паре (𝑛,𝑚). Важно, что 𝑛,𝑚 ≠ 1. Из леммы мы знаем, что
𝑎 = 𝑎 𝑎 + 𝑠𝑎 𝑎 . Тогда 𝑎 ⋅ 𝑎 ⋯𝑎 = 𝑎 ⋅ 𝑎 ⋯𝑎 ⋅ (𝑎 𝑎 +
𝑛+𝑚 𝑛+1 𝑚 𝑛 𝑚−1 𝑛+1 𝑛+2 𝑚+𝑛 𝑛+1 𝑛+2 𝑚+𝑛−1 𝑛+1 𝑚
𝑠𝑎 𝑎 ) = 𝑎 𝑎 ⋅𝑎 ⋯𝑎 𝑠𝑎 +𝑎 ⋅𝑎 ⋯𝑎 𝑎 𝑎 . Заметим, что оба
𝑛 𝑚−1 𝑛 𝑛+1 𝑛+2 𝑚+𝑛−1 𝑚−1 𝑛+1 𝑛+2 𝑚+𝑛−1 𝑛+1 𝑚
слагаемых из последнего тождества кратны 𝑎 ⋅ 𝑎 ⋯𝑎 . Первое кратно из предположе-
1 2 𝑚
ния для пары (𝑛 − 1,𝑚), а второе из предположения для пары (𝑛,𝑚 − 1), в котором оба
числа из предположения о делимости домножили на 𝑎 ≠ 0. Доказательство окончено.
𝑚
3

Решение.
2𝑃𝐺 𝑃𝐹 + 𝑃𝐺 − 𝑃𝐹 + 𝑃𝐺 𝐵𝐹 + 𝐵𝐺 − 𝐴𝐹 + 𝐴𝐺
Докажем,что𝐺𝑃 = 𝐺𝑄 = 𝐺𝑌.Имеем𝑃𝐺 = = = =
2 2 2
𝐴𝐺 + 𝐵𝐺 + 𝐴𝐵 2𝐺𝑌
= = 𝐺𝑌. Аналогично проверяем, что 𝐹𝑃 = 𝐹𝑄 = 𝐹𝑍. Рассмотрим
2 2
соответствующие окружности с центрами в точках 𝐹 и 𝐺. Точки 𝑃 и 𝑄 лежат на их ради-
кальной оси. Касательные из точки 𝐼 к рассмотренным окружностям равны, поскольку
эторадиусывписаннойокружностичетырехугольника𝐴𝐵𝐶𝐷.Следовательно,точка𝐼 то-
же лежит на этой радикальной оси.

Ответ: Верно.
Решение.
2
Выберем три последовательные точки так, чтобы они укладывались на дуги окруж-
13
ности. Такие найдутся, поскольку если для каждой пары точек, взятой через одну, ду-
2
га будет больше , то обойдя дважды окружность мы получим больше, чем два обо-
13
рота. Для этих трех точек основание треугольника меньше 13, поскольку центральный
360∘
угол меньше 2 ⋅ < 60∘. При этом 2√48 > 13, а значит высота треугольника меньше
13
13 − √132 − (√48)2. Тогда площадь будет меньше 13.

Ответ: 36
Решение. Подсчитаемупорядоченныетройки(растопыркиитреугольники).Соднойсто-
роныможновыбратьпервого12𝑘способами,адобратькнемувтройкувторогоитретьего
– 3𝑘 + 6 и 3𝑘 + 5 способов соответственно. С другой стороны если обозначить за 𝑚 коли-
чество пожавших руку двум людям, то первых двух можно выбрать любыми (то есть 12𝑘
и12𝑘−1способами),атретьегоможнодобрать𝑚способами.Имеем12𝑘(3𝑘+6)(3𝑘+5) =
9𝑘2 + 33𝑘 + 30
12𝑘(12𝑘 − 1)𝑚, тогда 𝑚 = . Числитель на 3 делится, а знаменатель нет, по-
12𝑘 − 1
3𝑘2 + 11𝑘 + 10 12𝑘2 + 44𝑘 + 40 9𝑘 + 43
этомуцелымдолжнобытьчисло .Тогдаи = 𝑘+3+
12𝑘 − 1 12𝑘 − 1 12𝑘 − 1
тоже. Из последнего имеем 9𝑘 + 43 ⩾ 12𝑘 − 1 или 𝑘 ⩽ 14. Перебором находим, что 𝑘 = 3,
откуда ответ 36. В качестве примера такой конфигурации возьмем 36 человек, каждому
изкоторыхможноприсвоитьупорядоченнуюпаруостатковприделениина6.Рукопожа-
тия будут совершать люди у которых первый остаток пары совпал, второй остаток пары
совпал или суммы остатков в паре совпадают.

Решение.
1

Отразим точку 𝐴 относительно 𝑂𝐸 и 𝑂𝐹. Получим точки 𝐴′ и 𝐴″, которые лежат на опи-
санной окружности треугольника 𝐴𝐵𝐶. Треугольники 𝐴′𝑂𝐴″ и 𝐵𝑂𝐶 равны по первому
признаку (𝑂𝐵 = 𝑂𝐶 = 𝑂𝐴′ = 𝑂𝐴″, ∠𝐴′𝑂𝐴″ = 2∠𝐸𝑂𝐹 = 2∠𝐵𝐴𝐶 = ∠𝐵𝑂𝐶). Тогда 𝑃 =
𝛥𝐴𝐸𝐹
𝐴𝐸 + 𝐸𝐹 + 𝐹𝐴 = 𝐴′𝐸 + 𝐸𝐹 + 𝐹𝐴″ ⩾ 𝐴′𝐴″ ⩾ 𝐵𝐶.

Ответ: 𝑃(𝑥) = 2𝑡2, 𝑡 ∈ ℤ; 𝑃(𝑥) = 𝑎2𝑥, 𝑎 ∈ ℤ
Решение. Имеем 𝑃(𝑥) + 𝑃(−𝑥) = 𝑘2, причем из-за непрерывности многочлена 𝑘2 будет
0
фиксированнымдлялюбого 𝑥.Аналогично 𝑃(𝑥+1)+𝑃(−𝑥) = 𝑘2.Тогда 𝑃(𝑥+1)−𝑃(𝑥) =
1
𝑘2−𝑘2−−𝑐𝑜𝑛𝑠𝑡,азначитлибонашмногочленпостоянный(вэтомслучаеподойдутлишь
1 0
вынесенныевответконстанты),либоонведетсебякаклинейный,азначитискатьнужно
в виде 𝑃(𝑥) = 𝑎𝑥 + 𝑏. Подставим в исходное: 𝑎(𝑥 + 𝑦) + 2𝑏 – квадрат, если 𝑥 + 𝑦 – квад-
рат. Подставляя 𝑥 + 𝑦 = 0 и 𝑥 + 𝑦 = 1, получаем, что 𝑎 = 𝑚2 − 𝑚2 ∈ ℤ. К тому же из
1 0
подстановки следует, что 2𝑏 ∈ ℤ. Очевидно, что 𝑎 не может быть отрицательным, иначе
можносделатьотрицательноезначениедляквадрата,еслиподставить𝑥+𝑦 = (2𝑏)2.Нуа
еслиположительное,томожносделатьследующее:подставим𝑥+𝑦 = 𝑡2 идомножимвсе
на 𝑎. Имеем (𝑎𝑡)2 + 2𝑎𝑏 = 𝑎𝑘2. Разницы между соседними квадратами могут быть сколь
угодно большими, поэтому и разницы между соседними выражениями вида 𝑎𝑘2 тоже.
Тогда можно подобрать 𝑡 столь большим, что «довесок» 2𝑎𝑏 не дотянется до квадратов,
соседних с (𝑎𝑡)2, а значит 𝑏 = 0.

Решение. Будемназыватьмножествочиселприятным,еслионоудовлетворяетусловию.
Заметим, что множество 𝐴 нечетных чисел от −9 до 9 является приятным, поскольку в
таком множестве любая искомая сумма будет нечетной и не более 45 по модулю. Рас-
смотрим множества
𝐴 = {𝑥 ∈ 𝑋 | ∃𝑎 ∈ 𝐴 ∶ 𝑘𝑥 ≡ 𝑎 (mod 47)}.
𝑘
Легковидеть,чтопри𝑘 = 1,2,...,46такиемножествабудутприятными.Еслибывкаждом
из этих множеств было меньше искомого количества, то суммарно их будет не более 46⋅
2020 = 92920. В то же время каждый 𝑥 мы посчитали в 10 множествах, а значит должно
всего получиться 10 ⋅ 10000 = 100000.

Решение. Пусть𝑂𝐵 пересекает𝐴𝐶 вточке𝑌′,а𝑟–радиусокружности.Посчитаемуголоч-
ки в равнобедренных треугольниках 𝐴𝑂𝐵 и 𝐵𝑂𝐶: ∠𝐴𝐵𝑂 = ∠𝐵𝐴𝑂 = 72∘;∠𝑂𝐶𝐴 = ∠𝑂𝐴𝐶 =
36∘. Далее получаем, что ∠𝐶𝐴𝐵 = ∠𝑂𝐴𝐵 − ∠𝑂𝐴𝐶 = 72∘ − 36∘ = 36∘ и ∠𝐴𝑌′𝐵 = ∠𝑂𝑌′𝐶 =
180∘ − ∠𝐶𝑂𝑌′ − ∠𝑂𝐶𝑌′ = 72∘. Из полученных тождеств получаем, что треугольники
𝑂𝐶𝑌′,𝐵𝐴𝑌′,𝐴𝑌′𝑂 равнобедренные (𝑥 = 𝐴𝐵 = 𝐴𝑌′ = 𝑌′𝑂; 𝑟 = 𝑂𝐶 = 𝐶𝑌′). Т.к. 𝑟 = 𝐶𝑌′,
то осталось показать, что 𝑌 = 𝑌′ или 𝑂𝑋 = 𝐵𝑌′. Далее из подобия треугольников 𝑂𝐴𝑌′ и
𝐶𝐴𝑂;теоремыМенелаядлятреугольника𝑂𝑌′𝐴ипрямой𝑀𝐶исвойствабиссектрисы𝐴𝑌′
7

𝑂𝐴 𝑂𝑌′ 𝐴𝑀 𝑂𝑋 𝑌′𝐶
в треугольнике 𝐴𝑂𝐵 мы получаем следующие отношения: = ; ⋅ ⋅ =
𝐶𝐴 𝑂𝐴 𝑂𝑀 𝑋𝑌′ 𝐶𝐴
𝐴𝑂 𝑌′𝑂 𝑟 𝑥 𝑂𝑋 𝑟
1; = . В терминах 𝑟 и 𝑥 они переписываются так: = ; ⋅ =
𝐴𝐵 𝑌′𝐵 𝑟 + 𝑥 𝑟 𝑥 − 𝑂𝑋 𝑟 + 𝑥
𝑟 𝑥
1; = . Выражая из последнего 𝐵𝑌′, а из второго 𝑂𝑋, легко проверить их равенство,
𝑥 𝐵𝑌′
пользуясь первым тождеством.
8

Решение. Будем следить за суммой квадратов попарных расстояний.
Пусть текущая тройка точек — 𝐴,𝐵,𝐶, а точка 𝐷 ещё одна точка из множества. Поставим
𝐷 в начало координат. Сумма квадратов расстояний от 𝐷 до меняющихся изменится
𝑎 + 𝑏 2 𝑎 + 𝑐 2 𝑐 + 𝑏 2
с 𝑎2 + 𝑏2 + 𝑐2 на ( ) + ( ) + ( ) .
2 2 2
Нетрудно доказать, что сумма квадратов не увеличилась. А сумма квадратов, относяща-
яся к попарным расстояниям меняющихся точек, уменьшается в 4 раза.
Есликаждыйразтройка𝐴,𝐵,𝐶 несодержаласьвкругерадиуса1,тосуммаквадратовсто-
рон была уж точно больше 1, значит общая сумма квадратов на каждом из сколь угодно
3
большого числа шагов уменьшалась минимум на , что невозможно.
4

Решение. Докажем, что для каждого 𝑘 подойдут все 𝑛 = 𝑙 ⋅ 𝑘! − 1, где 𝑙 ⩾ 3.
Пусть 𝑚 = HOK((𝑛 + 1),…,(𝑛 + 𝑘)). Заметим, что при таком выборе 𝑛,
HOД(𝑛,𝑛 + 𝑗) = HOД(𝑛,𝑗) = 1
для всех 𝑗 от 1 до 𝑘, а значит
HOK(𝑛,(𝑛 + 1),…,(𝑛 + 𝑘)) = HOK(𝑛,𝑚) = 𝑛𝑚.
Теперь осталось заметить, что 𝑚 и 𝑛 + 𝑘 + 1 оба делятся на 𝑘 ⩾ 2, а значит
𝑚(𝑛 + 𝑘 + 1)
HOK((𝑛 + 1),(𝑛 + 2),…,(𝑛 + 𝑘 + 1)) ⩽ < 𝑚𝑛 = HOK(𝑛,(𝑛 + 1),…,(𝑛 + 𝑘)).
2

Докажите, что для любых положительных чисел 𝑎,𝑏,𝑐 справедливо неравен-
ство
(𝑎𝑏 + 𝑏𝑐 + 𝑐𝑎 + 1)(𝑎 + 𝑏)(𝑏 + 𝑐)(𝑐 + 𝑎) ⩾ 2𝑎𝑏𝑐(𝑎 + 𝑏 + 𝑐 + 1)2.
Первое решение. После раскрытия скобок и приведения подобных слагаемых получим
неравенство
∑ 𝑎2𝑏 + ∑ 𝑎3𝑏2 ⩾ 4 ∑ 𝑎2𝑏𝑐.
𝑠𝑦𝑚 𝑠𝑦𝑚 𝑠𝑦𝑚
Последнее верно, если сложить 6 неравенств типа
𝑎2𝑏 + 𝑏3𝑐2 ⩾ 2𝑎𝑏2𝑐.
Второе решение. По неравенству КБШ
𝑎 𝑏 𝑐
(𝑎 + 𝑏 + 𝑐 + 1)2 ⩽ (𝑎𝑏 + 𝑏𝑐 + 𝑐𝑎 + 1)( + + + 1)
𝑏 𝑐 𝑎
𝑏 𝑐 𝑎
(𝑎 + 𝑏 + 𝑐 + 1)2 ⩽ (𝑎𝑏 + 𝑏𝑐 + 𝑐𝑎 + 1)( + + + 1)
𝑎 𝑏 𝑐
Сложив эти два неравенства, получим
𝑎 𝑏 𝑐 𝑏 𝑐 𝑎 (𝑎 + 𝑏)(𝑏 + 𝑐)(𝑐 + 𝑎)
2(𝑎+𝑏+𝑐+1)2 ⩽ (𝑎𝑏+𝑏𝑐+𝑐𝑎+1)( + + + + + +2) = (𝑎𝑏+𝑏𝑐+𝑐𝑎+1) ,
𝑏 𝑐 𝑎 𝑎 𝑏 𝑐 𝑎𝑏𝑐
откуда и следует требуемое неравенство.

Ответ: при чётных 𝑘 можно за 𝑛 вопросов.
Решение. Давайте всем людям раздадим остатки по модулю 2. Рыцари получат 1, а лже-
цы0. Еслиспросить человека счислом 𝑝 промножество 𝐴,то вкачестве ответамы полу-
чим число
(𝑝 + 1) + ∑ 𝑎 (mod 2).
𝑎∈𝐴
Если 𝑝 лежит в множестве 𝐴, то мы узнаем сумму набора из 𝑘 − 1 числа, иначе из 𝑘 + 1
числа.Если𝑘нечетно,тозамениввсехрыцарейналжецов,алжецовнарыцарей,унасне
поменяютсясуммыпонаборам.Тогдамынесможемничегопонятьнипроодногочело-
века. Тогда 𝑘 должно быть четным. Понятно, что нужно минимум 𝑛 вопросов, т.к. всего
вариантовраспределениялжецовирыцарей2𝑛,анакаждыйвопроснамотвечаютодним
из двух вариантов. Спросим у всех про фиксированное множество 𝐵. Просуммировав по
5

суммам для людей из множества 𝐵 мы получим число
(𝑘 − 1)(∑ 𝑏) = ∑ 𝑏 (mod 2).
𝑏∈𝐵 𝑏∈𝐵
Последнееверно,т.к.𝑘−1нечетно.Тогда,принимаявовниманието,чтокаждыйдалпро
𝐵 ответ
(𝑝 + 1) + ∑ 𝑏 (mod 2).
𝑏∈𝐵
мы узнаем все про каждого человека.