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

Решение. Еслисредичиселесть0,задачарешена.Рассмотримситуацию,когданулейнет.
Очевидно, что тогда среди 𝑎 есть числа разных знаков. Будем собирать поднабор 𝑏 с
𝑖 𝑘
прицелом на нулевую сумму. Для этого выберем какое-нибудь положительное 𝑎 за 𝑏 ,
𝑖 1
а дальше будем выбирать 𝑏 из числа невыбранных 𝑎 так, чтобы его знак отличался от
𝑛 𝑗
𝑛−1
знака 𝑠 = ∑ 𝑏 . Так как сумма всех чисел исходного набора равняется 1, либо такое
𝑖 𝑘
𝑘=1
𝑏 нужного знака найдется вплоть до 𝑏 , либо сумма уже набранных 𝑏 равна 0, либо
𝑛 2000 𝑘
сумма еще не выбранных 𝑎 равна 0.
𝑖
Осталосьзаметить,чтовсилувыбора𝑏 ,этичисланемогутбытьвнеинтервала[−999;1000],
𝑖
а значит, либо какое-то 𝑠 равняется 0 и образует искомый поднабор, либо, по принципу
𝑖
Дирихле (у нас 2000 сумм и 1999 вариантов значения), найдутся такие 𝑙 > 𝑚, что 𝑠 = 𝑠 .
𝑙 𝑚
В этом случае нам, очевидно, подойдет набор 𝑏 ,…,𝑏 .
𝑚+1 𝑙

Ответ: 10002 − 2 ⋅ 999.
Решение.
Утверждение.Есликдоске𝑚×𝑛применитьуказаннуюоперациюнесколькораз,тооста-
нутсянеодноклеточныепрямоугольникисуммарнойплощадьюхотябы2(min(𝑚,𝑛) − 1)
клеток.
Доказательство.
Заметим, что ни один прямоугольник, кроме, собственно, 1×1 нельзя с помощью разре-
шенных действий разрезать на 1 × 1 без остатка. Таким образом, для всех неодноклеточ-
ных прямоугльников будет потеряно хотя бы 2 клетки.
Теперьдокажемутверждениепоиндукции:Базаиндукции:прямоугольникисоднимиз
3

измерений равным 1. Заметим, что для 1 × 1 утверждение верно, а в остальных случаях
для прямоугольника 1 × 𝑎 мы теряем даже не 0, а 𝑘 площади.
Переход:пустьдлявсехпрямоугольников,строгоменьшихискомогоутверждениеверно,
докажем для искомого.
Разобьём доску на три меньших первым ходом, для каждой напишем эту оценку и про-
суммируем: пусть у нас доска 𝑚 × 𝑛 разбилась на три прямоугольника:
• 𝑚 × 𝑘,
• 𝑙 × (𝑛 − 𝑘),
• (𝑚 − 𝑙) × (𝑛 − 𝑘).
Случай 1. Пусть 𝑚 ⩾ 𝑛.
Тогдамыполучимнеодноклеточныхпрямоугольниковсуммарнойплощадьюнеменьше
2(min(𝑚,𝑘) − 1) + 2(min(𝑙,𝑛 − 𝑘) − 1) + 2(min(𝑚 − 𝑙,𝑛 − 𝑘) − 1) =
= (2𝑘 − 2) + 2(min(𝑙,𝑛 − 𝑘) − 1) + 2(min(𝑚 − 𝑙,𝑛 − 𝑘) − 1).
Заметим,чтоеслихотябыодинизоставшихсяминимумовравен𝑛−𝑘,исредиэтихдвух
прямоугольников нет 1 × 1, то вся сумма не меньше, чем
2𝑘 − 2 + 2(𝑛 − 𝑘) − 2 + 2 = 2𝑛 − 2.
Если же один из них это прямоугольник 1 × 1, то 𝑛 − 𝑘 = 1, то вся сумма не меньше, чем
2𝑘 − 2 + 𝑚 − 1 = 2(𝑛 − 1) − 2 + 𝑚 − 1 ⩾ 2𝑛 − 2.
А если оба не равны, то сумма равняется
(2𝑘 − 2) + (2𝑙 − 2) + (2(𝑚 − 𝑙) − 2) = 2𝑘 + 2𝑚 − 6.
Это меньше 2𝑛 − 2 только если 𝑚 = 𝑛 и 𝑘 = 1 — но вот только для 𝑘 = 1 прямоугольник
𝑚×𝑘 теряет не 0, а 𝑚 клеток, что дает нам 3𝑚−4 ⩾ 2𝑛−2 для всех 𝑚 ⩾ 2, а значит и для
всех 𝑚, рассматриваемых в переходе.
Случай 2. Пусть 𝑚 < 𝑛.
Если 𝑘 ⩽ 𝑚, то этот случай рассматривается аналогичным образом. Если же 𝑘 > 𝑚, то
мы получаем цепочку неравенств 𝑛 > 𝑘 > 𝑚 > 𝑙. Тогда мы получим неодноклеточных
прямоугольников суммарной площадью не меньше
2(min(𝑚,𝑘) − 1) + 2(min(𝑙,𝑛 − 𝑘) − 1) + 2(min(𝑚 − 𝑙,𝑛 − 𝑘) − 1) =
= 2𝑚 − 2 + 2(min(𝑙,𝑛 − 𝑘) − 1) + 2(min(𝑚 − 𝑙,𝑛 − 𝑘) − 1) ⩾ 2𝑚 − 2
Для четных 𝑚 и 𝑛 (в частности для 𝑚 = 𝑛 = 1000), оценка точная — для того, чтобы
потерять не более, чем 2 ⋅ (𝑚𝑖𝑛(𝑚,𝑛) − 1) площади, надо каждым ходом от оставшегося
4

«большого»(состоронами,большими2)прямоугольникаотрезатьпрямоугольник2×𝑛,а
отостатка—ещёодинсостороной2.Такмыпорежемвсёнапрямоугольникисостороной
2, а из каждого того куска отрезая по два одноклеточных,можно оставить лишь одну не
разрезанную доминошку.

В четырехугольнике 𝐴𝐵𝐶𝐷 ∠𝐴 = ∠𝐶 = 90∘. На диагонали 𝐵𝐷 выбраны точки
𝑀,𝑁 так, что 𝐴𝑁 ∥ 𝐵𝐶, 𝐶𝑀 ∥ 𝐴𝐵. На сторонах 𝐴𝐷 и 𝐶𝐷 соответственно выбраны точки
𝑋 и 𝑌 так, что ∠𝑋𝑁𝐵 = ∠𝑌𝑀𝐷 = 90∘. Докажите, что отрезок 𝐴𝐶 равен полупериметру
треугольника 𝐵𝑋𝑌.
Первое решение.
Пусть 𝐴𝐶 пересекает 𝐵𝑋 и 𝐵𝑌 в точках 𝐸 и 𝐹
соответственно. Докажем, что 𝐸 — середина
𝐵𝑋, а 𝐹 — середина 𝐵𝑌.
Из этого будет следовать, что
𝐴𝐶 = 𝐴𝐸 + 𝐸𝐹 + 𝐹𝐶 = 𝐵𝐸 + 𝐸𝐹 + 𝐹𝐵 =
𝐵𝑋 + 𝑋𝑌 + 𝐵𝑌 𝑃
= = 𝛥𝐵𝑋𝑌 .
2 2
Доказательство того, что 𝐵𝐹 = 𝐶𝐹 = 𝑌𝐹.
Воспользуемся параллельностью 𝐴𝐵 и 𝑀𝐶, а также вписанностью 𝐴𝐵𝐶𝐷 и 𝐵𝐶𝑌𝑀. Полу-
чается следующая цепочка равенств
∠𝐹𝑌𝐶 = ∠𝐵𝑀𝐶 = ∠𝐴𝐵𝑀 = ∠𝐴𝐶𝐷.
А из неё уже следует, что 𝐶𝐹 — медиана в прямоугольном треугольнике 𝐵𝐶𝑌.
Аналогичным образом доказывается, что 𝐵𝐸 = 𝐴𝐸 = 𝑋𝐸.
Второе решение. 1 Шаг. Пусть 𝐴𝐵𝐶𝐷 вписан в окружность 𝜔. Т.к. ∠𝐵𝑀𝑌 = 90∘ = ∠𝐵𝐶𝑌,
то 𝐵𝐶𝑌𝑀 вписан. Далее из вписанности 𝐵𝐶𝑌𝑀 и параллельности 𝐴𝐵 c 𝐶𝑀 имеем сле-
дующие тождества на уголки:∠𝐴𝐵𝑀 = ∠𝐵𝑀𝐶;∠𝐶𝐵𝑌 = ∠𝐶𝑀𝑌 = 90∘ − ∠𝐵𝑀𝐶 = 90∘ −
2

∠𝐴𝐵𝐷 = ∠𝐴𝐷𝐵. Тогда 𝐵𝑌 и 𝐴𝑁 пересекаются в точке 𝐴 на окружности 𝜔 (дополняя точ-
1
кой 𝐴 треугольник 𝐴𝐵𝐶 до равнобокой трапеции). Т.к. 𝐴𝐵𝐶𝐴 равнобокая трапеция, то
1 1
𝐴𝐶 = 𝐵𝐴 . Аналогично определяем 𝐶 и получаем, что 𝐵𝐶 = 𝐴𝐶. Тогда надо доказать,
1 1 1
что 𝐵𝑌 + 𝐵𝑋 + 𝑋𝑌 = 𝐵𝐴 + 𝐵𝐶 , а это равносильно 𝑋𝑌 = 𝑋𝐶 + 𝑌𝐴 .
1 1 1 1
2 Шаг. Сейчас мы докажем, что D – центр вневписанной окружности треугольника 𝐵𝑋𝑌
напротив вершины 𝐵. Т.к. ∠𝐷𝐴 𝐵 = ∠𝐷𝐶 𝐵 = 90∘, то из этого моментально следует, что
1 1
𝑋𝑌 = 𝑋𝐶 + 𝑌𝐴 .
1 1
1Способ.Извписанности𝐵𝐶𝑌𝑀ипараллельности𝐴𝐵c𝐶𝑀имеемследующиетождества
на уголки: ∠𝐵𝐴𝐶 = ∠𝐴𝐶𝑀;∠𝐷𝐵𝐴 = ∠𝑀𝐶𝑌 = ∠𝐵𝐶𝑌 − ∠𝐴𝐶𝑀 − ∠𝐵𝐶𝐴 = 90∘ − ∠𝐵𝐶𝐴 −
1
∠𝐵𝐴𝐶.Аналогичнополучаем,что∠𝐷𝐵𝐶 = 90∘−∠𝐵𝐶𝐴−∠𝐵𝐴𝐶 = ∠𝐷𝐵𝐴 .Тогда𝐷 лежит
1 1
набиссектрисеугла𝑋𝐵𝑌,приэтом∠𝑋𝐷𝑌 = 180∘−∠𝐴𝐵𝐶 = ∠𝐵𝐴𝐶+∠𝐵𝐶𝐴 = 90∘−∠𝐷𝐵𝐴 .
1
∠𝑋𝐵𝑌
Это значит, что ∠𝑋𝐷𝑌 = 90∘ − . Т.к. 𝐷 вне треугольника 𝐵𝑋𝑌, то из условия, что
2
𝐷 на биссектрисе, и последнего тождества на углы мы как раз получаем, что это центр
вневписанной окружности.
2Способ.ИзтеоремыПаскалядляшестивершинника𝐴𝐴 𝐵𝐶𝐶 𝐷 мыполучаем,чтопере-
1 1
сечение𝑍 прямых𝐴𝐴 и𝐶𝐶 лежитнапрямой𝑋𝑌.Заметим,что𝑍 –ортоцентртреуголь-
1 1
ника𝐴𝐶𝐷 (𝐴𝑍 ∥ 𝐵𝐶 ⟂ 𝐶𝐷).Тогдаточки𝑍 и𝐴 симметричныотносительно𝐶𝐷 (леммаоб
1
отражении ортоцентра). Тогда из симметрии 𝐴 𝑌 = 𝑍𝑌. Аналогично 𝐶 𝑋 = 𝑍𝑋, откуда
1 1
𝑋𝑌 = 𝑋𝑍+𝑍𝑌 = 𝑋𝐶 +𝑌𝐴 .Чтоитребовалось.(Вэтомрешениимынетолькополучили,
1 1
что 𝐷 - центр вневписанной, но и что 𝑍 – точка касания вневписанной.)

Ответ: 36
Решение. Подсчитаем упорядоченные тройки. С одной стороны можно выбрать первого
12𝑘 способами, а добрать к нему в тройку второго и третьего — 3𝑘 + 6 и 3𝑘 + 5 спосо-
бов соответственно. С другой стороны если обозначить за 𝑚 количество пожавших руку
двум людям, то первых двух можно выбрать любыми (то есть 12𝑘 и 12𝑘−1 способами), а
третьего можно добрать 𝑚 способами. Имеем 12𝑘(3𝑘 + 6)(3𝑘 + 5) = 12𝑘(12𝑘 − 1)𝑚, тогда
1

9𝑘2 + 33𝑘 + 30
𝑚 = . Числитель на 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. Рукопожатия будут
совершатьлюдиукоторыхпервыйостатокпарысовпал,второйостатокпарысовпалили
суммы остатков в паре совпадают.

Решение. Предположимпротивное.Закодируемклеткиквадратапокоординатнопарами
чисел (𝐴,𝐵). Будем говорить, что Леша бьет в клетку (𝐴,𝐵), если он ударил по квадрату с
угловыми клетками (𝐴,𝐵) и (𝐴 + 49,𝐵 + 49).
Будем действовать «заметанием полос». Ударим поочередно по клеткам
(1,1);(50,1);(99,1)…(1 + 49𝑘,1)…(1961,1);(1971,1).
Всего получилось 42 удара. Далее будем повторять такие серии ударов, увеличивая вто-
руюкоординатуна1припереходекследующейсерии(можноувеличиватьинабольшее
число ⩽ 7).
Посмотримнавозможныепозициитараканпослеударов.Таккакквадратсостороной50,
то между ударами в серии таракан не может забежать в предыдущий квадрат из следу-
ющего между ударами. Тогда легко установить, что возможные позиции таракана после
серии — это «лесенка» c шириной ступеньки в 49 и высотой каждой 1 (последняя будет
длины 11). С каждым ударом наша «лесенка» опускается на один уровень в глубь квад-
рата, а где-то поднимается на 50 позиций. За 42 хода первая опустилась на 42, но мы ее
подняли на 50 в первом ходу. Тогда после серии ее высота будет 8, второй ступеньки 9 и
т.д. до высоты в 50 у последней. Когда мы повторяем наше ”заметание полосы”, то высо-
ты поднимаются на 1. Таким образом мы плавно увеличиваем площадь без таракана от
одной стороны до другой.
В 1971 такой серии у нас лесенка не сможет увеличиваться, так как таракану неоткуда
взяться в нашем квадрате. Таким образом мы справимся за 1971 такую серию.

Ответ: 3.
Решение.
Покажем, что меньше 3 нельзя. Рассмотрим два единичных круга, которые
зацеплены на ϵ. Легко видеть, что выбрать из них можно лишь один круг, а
раздуть его придется в 3 − ϵ раз. Ясно, что какое бы меньшее 3 число мы не
взяли, то можно так подобрать ϵ, чтобы у нас не получилось.

Покажем, что для k = 3 это возможно. Выберем самый большой круг, затем са-
мый большой из тех, что не пересекается с предыдущим, потом самый большой,
который не пересекается с ранее выбранными и т.д. Посмотрим, что произой-
дет после раздувания выбранных кругов. Рассмотрим круг U, который мы не
выбрали, пересекается с кем-то из выбранных. Выберем самый большой круг
S из тех, с кем U пересекся. В силу выбора U не более, чем S, а значит при
увеличении радиуса S в 3 раза круг U будет накрыт.
Putnam, 1998, вариация

Ответ: 2.
Решение.
Равенство из условия можно переписать в виде CD = 2·BD. Очевидно, что точ-
ка K лежит на вписанной окружности. Пусть касательная к вписанной окруж-
ности ABC в точке K пересекает стороны AC,AB или их продолжения в точ-
ках X,Y соответственно. Тогда B и X – середины отрезков FY и EC соот-
ветственно. Действительно, в силу симметрии относительно биссектрисы угла
A FY = CE = CD = 2BD = 2BF и 2XE = 2KX = 2BD = CD = CE.
Пусть W – середина отрезка KY , тогда KWBF – равнобедренная трапеция,
так как треугольник KY F является равнобедренным. Пусть Z симметрична
точке K относительно точки X, тогда EKCZ прямоугольник. Два рассмот-
ренных четырехугольника вписаны в соответствующие окружности из условия.
Давайте воспользуемся этим. Имеем XL = XK = Y B = Y W, что означает что
L симметрична B относительно серединного перпендикуляра к WK (окруж-
ность FBWKL симметрична относительно этого серединного перпендикуляра
и точки Y и Z тоже, а от последних проведены отрезки равной длины к B и L).
FK DE DE
Получаем, что KL = BW = = . Отсюда = 2.
2 2 KL
Шорт-лист Балканской олимпиады, 2021

Ответ: Да, верно.
Решение.
Обозначим стороны треугольника BC = a, AC = b и AB = c. Имеем CE =
a + b − c
CD = . Запишем теоремы косинусов вокруг угла C для треугольников
2
a2 + b2 − c2
ABC, ADC и BEC. Из первого треугольника имеем cosC = . Из
2ab
(a + b − c)2
двух оставшихся AD2 = b2 + − b(a + b − c)cosC и BE2 = a2 +
4
(a + b − c)2
− a(a + b − c)cosC. Тогда имеем
4
a − b
BE2 − AD2 = (a2(−a + b + c) + b2(a − b + c) + c2(a + b − c)).
2ab
Пусть треугольник не является равнобедренным. Тогда можно считать, что
a > b. Так как стороны целые, то c > 1, чтобы выполнялось неравенство тре-
угольника. А значит c ⩾ 2. Обозначим k разницу a − b. Если k ⩾ 2, то выразим
a как b + k в исходном выражении разности BE2 − AD2 и получим оценку
k (cid:0) (b + k)2(c − k) + b2(c + k) + c2(2b + k − c) (cid:1) ⩾ 2((b + k)2 + b2) > 2.
2(b + k)b 2(b + k)b
При k = 1 нужно воспользоваться оценкой разность квадратов из условия пе-
реписывается в виде 1 (cid:0) (b + 1)2(c − 1) + b2(c + 1) + c2(2b + 1 − c) (cid:1) . Заме-
2(b + 1)b
тим, что 2 ⩽ c ⩽ a + b − 1 = 2b, а также что минимум f(c) = c2(2b + 1 − c) на
отрезке [2;2b] достигается в левом конце. Следовательно, он равен f(2) = 8b−4.
Получаем оценку 1 (cid:0) (b + 1)2 · 1 + b2 · 3 + 8b − 4 (cid:1) = 2 + 4b2 + 10b − 3 > 2.
2(b + 1)b 2b2 + 2b

Журнал Crux, 2007, №1

Решение. Предположим, что наше утверждение неверно. Тогда каждый про-
стой делитель b входит в разложение b b ...b . Заметим, что b = P(b ) >
n 1 2 n−1 n n−1
b2 > b b ...b . Это значит, что найдется простое p, которое входит в b в
n−1 n−1 n−2 1 n
большей степени, нежели в произведение в левой части. Выберем наименьшее
натуральное k, для которого b делится на p. Фундаментальный факт: если m
k
не делится на k, то b не делится на p, а если делится, то степень вхождения
m
p в b и b одинаковы. Давайте этот факт докажем. Пусть степень вхожде-
k m
ния p в b равна α. Тогда b = P(b ) дает такой же остаток при делении на
k k+1 k
p2α, что и a . b = P(P(b )) дает такой же остаток при делении на p2α, что
0 k+2 k
и P(a ) и т.д. Тогда до индекса 2k мы будем получать, что соответствующие
0
b , b , ..., b дают такие же остатки, как и b , b , ..., b , а значит не
k+1 k+2 2k−1 1 2 k−1
делятся на p. Для индекса 2k остаток при делении на p2α такой же, как у b ,
k
означает, что степень вхождения такая же. Для остальных индексов рассужде-
ние аналогично. Вернемся теперь к исходному рассуждению. Каждое простое

p из разложения b входит в какое-то b с меньшим номером, однако мы выяс-
n i
нили, что тогда их степени вхождения должны совпадать. А это противоречит
тому, что нашлось простое p, которое в b входит в большей степени, нежели в
n
произведение b b ...b .
1 2 n−1
Болгария, 2018

Решение. Докажем в 4 этапа: 1) 2 лежит в A, 2) 3 лежит в A, 3) все нечетные
в A, 4) все в A.
1). Есть a,b > 1, если среди них есть четное – 2 лежит как делитель, если нет –
тогда 1 + ab – четное.
2). Итак, есть 2 и a > 2. Если a делится на 3 – 3 лежит. Если a вида 3k + 1 –
2a+1 делится на 3. Иначе смотрим на числа 2a+1 = 2(a+1)−1, 2(2a+1)+1 =
22(a + 1) − 1, ...2m(a + 1) − 1. Если хоть одно из них не простое – то у него
есть собственный делитель вида 3k+2 – поделили на него, частное вида 3k+1.
А все эти числа не могут быть простыми, ибо первое делилось на a (было ему
равно), и остатки по модулю повторяются периодично.
3). Из 2 и 3 соорудили 2·3+1 = 7,2·7+1 = 15,...2k−1. Надо объяснять, почему
любое нечетное число – делитель одного из членов этой последовательности?
Например, по теореме Эйлера.
4). Тут уже как угодно. Если надо получить четное n, можно рассмотреть де-
литель (n + 1)(n − 1) + 1.
Предложил Г.Челноков

Решение. Легко убедиться, что при k = 1 можно выбрать какое-то ребро. Пусть
n
k = 2. Тогда в нашем графе на n вершинах есть больше ребер, а значит какие-
2
то два имеют общую вершину. В дальнейшем будем считать, что k ⩾ 3. Заметим
также, что в любой момент граф можно считать связным. В противном случае
можно выбрать компоненту, в которой неравенство на ребра будет выполнятся
в силу линейности, и свести все к меньшему числу вершин.
Зафиксируем k. Докажем утверждение задачи с помощью индукции по n. Ба-
за при n = 2 очевидна. Докажем индукционный переход. Пусть для n вершин
мы доказали утверждение для всех таких графов, удовлетворяющих условию.
Рассмотрим граф на n + 1 вершине. Если найдется вершина с маленьким ко-
k + 1
личеством ребер (а именно менее ), то можно ее отбросить и применить
2
предположение индукции. Тогда можно считать, что каждая вершина имеет
k + 1
степень хотя бы .
2
Выберем самый длинный путь v v ...v в этом графе. С учетом рассмотренного
0 1 t
ранее можно считать, что t ⩾ 2. Первая ситуация: v и v соединены ребром.
0 t

Вспомним про связность и заметим, что если есть еще вершины, то от нашего
цикла v v ...v должно быть ребро к ним, а тогда можно построить более длин-
0 1 t
ный путь. Тогда t = n. Но тогда естественная оценка на суммарное число ребер
t(t + 1) (t + 1)(k − 1)
> эквивалентно t ⩾ k, а это значит, что есть путь длины
2 2
k.
Вторая ситуация: между v и v нет ребра. Рассмотрим вершину v . В силу
0 t 0
выбора максимального пути ее соседи могут быть только среди v , ..., v . С
1 t−1
k + 1
другой стороны у каждой вершины степень хотя бы . Тогда среди внутрен-
2
k − 1
них вершин пути v , ..., v у нее не менее соседей. Рассмотрим какую-то
2 t−1 2
из этих вершин v . Если она соседствует с v , то v не будет соседствовать с
r 0 r−1
v , поскольку в этом случае можно построить цикл v v v v ...v v v ...v и
t r 0 1 2 r−1 t t−1 r+1
свести все к первому случаю. Следовательно, у вершины v в этом пути соседей
t
k − 1 k + 1 k − 1
не более (t−2− )+1. Получаем оценку ⩽ d(v ) ⩽ (t−2− )+1,
2 2 t 2
а значит t ⩾ k, поэтому нужный путь найдется.
Форум Art of solving problems

Ответ: Второй.
Решение.
Заметим, что если закодировать красный цвет 1, а синий – 0, то получается,
что мы каждым ходом должны уменьшать число на доске, а такое не может
продолжаться бесконечно, поэтому игра закончится.
Выделим 40 карточек, которые лежали на позициях с номерами, кратными 50.
Каждым ходом меняется состояние ровно одной из этих карточек, а значит
перед ходом второго всегда нечетное количество таких красных карт. Следова-
тельно, второй всегда сможет сделать ход. Тогда он победит.
Шорт-лист международной олимпиады, 2009
n(k − 1)