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

Ответ: Можно.
Решение. Уложим монеты в квадрат 3×3. Первым взвешиванием сравним пер-
вые две строки квадрата на первых весах, а вторым – первые два столбца квад-
рата на вторых весах. Рассмотрим монеты, которые должны быть фальшивыми
при корректной работе в первых двух взвешиваниях. В первом случае это одна
из строк квадрата, а во втором – один из столбцов. Сравним третьим взвеши-
ванием эти монеты на третьих весах, выкинув лежавшую на пересечении этих
рядов. Пусть на третьем взвешивании в результате равенство. Заметим, что
откинутая монета и была фальшивой.
Действительно, если плохие весы были на одном из первых взвешиваний, то
один из первых двух результатов точно верный, а значит один ряд с фаль-
шивой монетой правильно выбран. При этом третье взвешивание тоже дает
верный результат, а значит соответствующие две монеты точно настоящие. В
соответствующем ряду остается только фальшивая. Если первые два взвеши-
вания давали верные результаты, то фальшивая уже автоматически найшлась.
Пусть на третьем взвешивании легче две монеты из строки. Тогда получается,
что первое и третье взвешивание на фальшивую монету указывают одинаково,
а второе взвешивание иначе. Следовательно, первые весы корректно работают.
Теперь с учетом первого взвешивания можно на них за одну операцию най-
ти фальшивую. Аналогично действуем в ситуации, когда легче две монеты из
столбца и вторыми весами.

Германия, 2014

Ответ: При n, дающих остаток 2 при делении на 4.
Решение. Пусть n – нечетно. Тогда второй каждым ходом уменьшает число
компонент связности, пока это возможно. Когда получается связный граф, он
двудольный, поскольку нечетных циклов нет. При этом в долях количества вер-
шин разной четности. Теперь любой ход может быть сделан только между до-
лями, иначе две вершины одной доли можно соединить как проведенным этим
ходом ребром, так и цепочкой других ребер в силу связности. А тогда нашелся
нечетный цикл. Следовательно, оставшаяся игра приведет к построению пол-

ного двудольного графа с четным числом ребер. В этой ситуации побеждает
второй игрок.
Пусть n – четно, но не делится на 4. В этом случае первый разбивает все вер-
шины на пары и соединяет две вершины одной пары. Если второй соединяет
вершины некоторой пары, то первый делает так же (их к моменту хода будет
доступно нечетное количество). Если второй соединяет две вершины из разных
пар, то первый соединяет парные к ним вершины. Если после этого получился
нечетный цикл, то он и до этого должен быть нечетный цикл.
Если n делится на 4, то второй после хода первого начинает действовать по
стратегии, аналогичной предыдущему случаю.
Канада, 2019

Ответ: n треугольников.
Решение. Пример: Разобьем каждую из n полос нашего треугольника на па-
раллелограммы со сторонами 1 и 2 и правильный треугольник. В каждом па-
раллелограмме проведем длинную диагональ.
Оценка: Рассмотрим разбиение на треугольники и выберем самую длинную сто-
рону треугольника разбиения. Понятно, что если она лежит на стороне исход-
ного правильного треугольника, то она равна 1, а все треугольники разбиения
√
правильные. Можно считать, что она не меньше 3. Тогда можно считать, что с
каждой из сторон к ней прилегает треугольник. Но в силу того, что мы выбрали
наибольшую сторону, положение точек в каждой из полуплоскостей однозначно
задано. Действительно, если мы нашли две точки в одной полуплоскости, то в
силу выбора исходной стороны на ней тоже должен найтись еще узел. А это про-
тиворечит теореме Пика для треугольной решетки. Рассмотрим теперь первую
сторону и две найденные вершины в каждой из полуплоскостей. Они образуют
параллелограмм. Заменим в нем диагональ на другую. Площади треугольни-
ков не изменились, а сумма периметров треугольников разбиения уменьшилась.
Количество правильных треугольников не изменилось. Понятно, что всего раз-
ных разбиений на треугольники конечное число, поэтому и возможных сумм
периметров тоже конечное число. Следовательно, рано или поздно от таких
√
преобразований мы придем к максимальной длине в разбиении 3. Теперь все
разбивается на параллелограммы со сторонами 1 и 2 а также правильные тре-
угольники. Раскрасим таблицу в шахматном порядке. Тогда каждый паралле-
лограмм дает равный вклад в цвета, а одного цвета на n треугольников больше.
Следовательно, хотя бы n правильных треугольников должно быть.
Тайвань, отбор на IMO, 2016, вариация

Решение. Отметим точку O – центр описанной окружности шестиугольника
ABCDEF. Условие, которое нужно доказать, эквивалентно тому, что OK ⊥
CF. Заметим, что точки B, K, O и D лежат на одной окружности, поскольку
1
∠BKD = ∠AFC = ACE = BCD = ∠BOD. Пусть прямые AB и CD пересе-
2
каются в точке S. Рассмотрим гомотетию с центром в S, переводящую точку
B в точку A. Тогда D переходит в C, точка K – в точку K′, лежащую на опи-
санной окружности исходного шестиугольника. Поскольку при этой гомотетии
треугольник BKD перешел в треугольник AK′E, то и описанная окружность
должна была перейти в описанную окружность. Тогда точка O, лежавшая на
первой описанной окружности, перейдет в точку C′, диаметрально противопо-
ложную C. Угол CK′C′ опирается на диаметр и потому прямой. При нашей
гомотетии OK перешло в C′K′, а значит тоже образовывало прямой угол с
CK′. Такое возможно только если K′ совпадает с точкой F, а значит остается
доказать этот факт. Заметим, что если рассмотреть ГМТ F, задаваемых ве-
личиной угла BKC, лежащих в соответствующей полуплоскости от AE. Это
ухо чебурашки, построенное на EK. Тогда на описанной окружности есть ров-
но одна точка, с заданным углом (вторая – точка E). Остается проверить, что
K′ является подходящей. А это так, поскольку ∠SK′E = ∠SKD по свойству
гомотетии.
Китай, отбор на IMO, 2016

Решение. Легко видеть, что треугольники ABC и IPQ подобны. При этом ко-
эффициент подобия можно выразить через отношение высоты и радиуса впи-
санной окружности исходного треугольника. Запишем площадь треугольника
ABC двумя способами: S = ah /2 = (a+b+c)r/2. Тогда h /r = a/(a+b+c). То-
a a
гда сторону PQ треугольника APQ можно выразить как a2/(a+b+c). Заметим,
ac
что по свойству биссектрисы BE/EA = b/a, а значит BE = . Аналогично
a + b
ab ac ab 2a2
CD = . Остается заметить, что + = . Действитель-
a + c a + b a + c a + b + c
c b 2a c(a + c) + b(a + b) 2a
но, + = равносильно = и с
a + b a + c a + b + c (b + c)(a + c) a + b + c

ac + ab + a2 2a
учетом того, что треугольник прямоугольный = . Отсю-
(b + c)(a + c) a + b + c
да получаем(a + b + c)2 = 2(a + b)(a + c) или a2 + b2 + c2 + 2ab + 2bc + 2ca =
2ab + 2bc + 2ac + 2a2, а это эквивалентно b2 + c2 = a2.
Решение. Отразим отрезки BE и CD относительно соответствующих биссек-
трис треугольника. Получим точки E′ и D′ на BC. Легко видеть после непосред-
ственного подсчета углов, что углы BID′ и CIE′ – прямые. В то же время из па-
раллельности IP = PB и IQ = QC. Тогда из свойств прямоугольного треуголь-
ника IP = PB = PD′ и IQ = QC = QE′. Тогда 2PQ = 2PD′ + 2QE′ − 2D′E′ =
(BD′ − D′E′) + (CE′ − D′E′) = BE′ + CD′ = BE + CD.
Журнал Crux, 2000, №1

Ответ: k = 1,2.
Решение. Легко видеть, что при раскраске чисел в три цвета: БСКБСКБСК...
не найдутся числа с разностью,равной степени двойки, так как любая разница
между одноцветными числами делится на 3. Для большего числа цветов доста-
точно просто перекрасить какие-то числа в новые цвета. Остается разобраться
со случаями k = 1,2. В первом случае очевидно, что такие числа найдутся. На-
пример, соответствующие степени двойки. Во втором случае возьмем 1 и будем
последовательно добавлять числа, отличающиеся от предыдущего на степень
двойки. Если мы не собрали нужный комплект чисел, то в какой-то момент для
текущего числа n всевозможные сдвиги на степени двойки дают числа другого
цвета. Тогда можем выкинуть все ранее выбранные числа и взять эти сдвиги в
нужном количестве. Разницы между соседями тоже будет степенями двойки.
Олимпиада BxMO, 2023

Ответ: Нет, не может.
Решение. Пусть d – длина периода в десятичной записи числа x. Запишем
d = 2kt, где t – нечетно. Выберем такое натуральное s, что 2s ≡ 1 (mod k).
Такое существует, можно взять s = φ(k). Тогда 2n+s ≡ 2n (mod k) при любом
натуральном n. При n > k 2n+s ≡ 2n ≡ 0 (mod 2k). Но тогда при достаточно

большом n 2n+k ≡ 2n (mod d), а значит (2n+k)-ая цифра в десятичной записи
числа будет находиться на том же месте цикла, что и (2n)-ая цифра. А это зна-
чит, что с некоторого момента произойдет зацикливание. Следовательно, новое
число тоже будет рациональным.
Шорт-лист международной олимпиады, 2006

Ответ: 35 решений.
1 (cid:16)
Решение. Исходное равенство переписывается в виде (m+n−33) (m−n)2 +
2
(cid:17)
(n + 33)2 + (m + 33)2 = 0. Если первая скобка равна нулю, то подходят пары
(33,0), (32,1), ..., (0,33). Для остальных пар значения m и n будут разных зна-
ков. Если вторая скобка равна нулю, то m = n = −33. Всего имеем 34 + 1 = 35
решений.
Из книги «101 Problem from the Training of the USA IMO team»

Ответ: 4k + 1, при n = 4k + 3 и 4k, при n = 4k, 4k + 1 или 4k + 2.
Решение. Пусть для каких-то элементов A,B,C ,...,C взяты тройки ABC ,
1 k 1
..., ABC . Будем называть такую конструкцию фонариком. Пусть для каких-то
k
элементов A,B,C,D взято некоторое подмножество троек ABC, BCD, ABD,
ACD – будем называть такую конструкцию (неполным) тетраэдром. Докажем
следующее утверждение: любое удовлетворяющее условию семейство троек раз-
бивается на фонарики и неполные тетраэдры, причем тройки из разных объек-
тов разбиения не пересекаются.
Доказательство. Пусть в семействе есть три разные тройки, содержащие одну и
ту же пару элементов A,B. Пусть все такие тройки – ABC , ..., ABC . Тогда
1 k
больше с ними никакая тройка не пересекается. В самом деле, если пересекается
с кем-то, то содержит одну из A,B, но не обе (иначе ее включили бы в список
ABC ,...,ABC ), но тогда с каждой тройкой из списка уже есть один элемент
1 k
пересечения, значит еще надо взять все элементы C ,...,C , что невозможно
1 k
при k ⩾ 3. Можем выделить фонарик A,B,C ,...,C – с ним никто больше
1 k
не пересекается. Рассмотрим случай, когда ни одна пара не принадлежит трем
тройкам. Если тройки вообще пересекаются (иначе все доказано) – тогда обо-
значим тройки ABC,ABD. Пусть с ними еще кто-то пересекается, тогда не по
AB (эта пара уже использована дважды), тогда без ограничения общности по
AC и AD, то есть имеем тройку ACD. По тем же соображениям, если с этими
тремя тройками еще кто-то пересекается, то только BCD, и с этой конструк-
цией уже никто больше не может пересекаться – выделили тетраэдр. Лемма
доказана.
Итак, семейство состоит из тетраэдров и фонариков, тетраэдр занимает 4 эле-
мента и дает 4 тройки, фонарик дает троек на две меньше, чем занимает эле-
ментов.
Предложил Г.Челноков

Ответ: Нет.
Решение. Заметим, что максимальное число в при заданных операциях не меня-
ется. Заметим также, что с точки зрения лексикографического порядка каждая
следующая строка будет больше предыдущего. Но у нас лишь конечное ко-
личество строк с заданным максимальным элементом. Поэтому процесс будет
конечным.

Ответ: Для полоски 1 × k или k × 1 – k, для доски m × n – 2m + 2n − 4.
Решение. В случае полоски можно закрасить все клетки. Пусть каждая сторона
доски не менее 2. В качестве примера можно закрасить два первых столбца, а
также первую и последнюю строки. При попытке построить цикл мы уйдем
вправо.
Обозначим ячейку в i-й строке и j-м столбце как (i,j). k-я положительная диа-
гональ – это множество ячеек (i,j), такое, что i + j − 1 = k. Аналогично, k-я
отрицательная диагональ – это множество ячеек (i,j), такое, что n + i − j =
k. Рассмотрим двудольный граф G с долями A = {a ,a ,...,a } и B =
1 2 m+n−1

{b ,b ,...,b }, где вершины a и b соединены ребром тогда и только тогда,
1 2 m+n−1 i j
когда клетка в пересечении i-й положительной диагонали и j-й отрицательной
диагонали красная. Заметим, что цикл слона соответствует циклу в G, и наобо-
рот. Граф G имеет как минимум две компоненты: если мы раскрасим клетки
таблицы попеременно в черный и белый цвета, как в шахматах, то рёбра графа
G, соответствующие черным клеткам, лежат в другой компоненте, чем рёбра
графа G, соответствующие белым клеткам – невозможно переместить слона
между черной и белой клетками. Кроме того, граф G имеет 2n+2m−2 верши-
ны. Если граф G ацикличен, то G – это лес, состоящий как минимум из двух
деревьев. Следовательно, граф G содержит не более 2n+2m−2−2 = 2n+2m−4
рёбер, а значит верна оценка и для красных клеток.

Ответ: S =
2
1
Решение. Пусть значение S > , тогда можно взять два равных квадрата пло-
2
1
щади более , каждый из них содержит центр.
4
Упорядочим квадраты по убыванию и будем последовательно их выкладывать
в ряд по нижней стороне, пока можем. Если очередной квадрат «выпирает», то
проведем линию по верхней стороне первого квадрата и продолжим уже по ней
аналогичный процесс. И так далее. Рассмотрим высоты самых левых квадратов.
Пусть их сумма равна h. Докажем, что h ⩽ 1. Площадь всех квадратов можно
оценить как x2 + (1 − x)(h − x) (первый квадрат x × x, а дальше мы можем
использовать то, что первый квадрат в каждом слое это тот, который не влез на
1
предыдущий). С другой стороны сумма площадей квадратов равна . Получим
2
1 − x2 1 − x2
оценку h ⩽ 2 + x. Но 2 + x ⩽ 1, значит все уместится.
1 − x 1 − x