Задание №176704: Турнир городов

1. В ряд слева направо стоят коробки с номерами 1, 2, 3, ...В них по очереди кладут

числа 1, 2, ..., 2025. В каждой коробке каждые два числа должны быть взаимно просты.
Очередное число кладётся в самую левую из разрешённых коробок. Все числа разложили.
а) (2 балла) Сколько чисел попало во вторую коробку?
б) (2 балла) Сколько чисел попало в третью коробку?
(Александр Шаповалов)
Ответы: а) 14 чисел; б) 7 чисел.
В первую коробку, очевидно, попадёт единица и все простые числа, меньшие 2025, а
составные числа туда попасть не могут.

Во вторую коробку не может попасть число, делящееся на два различных простых, так
как квадрат меньшего из этих простых попал бы сюда раньше. Поэтому в эту коробку
попадут в точности квадраты простых чисел, не превышающие 2025 = 452. Это числа
22, 32, 52, ..., 432. Их 14.
В третью коробку попадут следующие попарные произведения последовательных про-
стых чисел: 2 · 3, 5 · 7, 11 · 13, 17 · 19, 23 · 29, 31 · 37, 41 · 43. Докажем это. Число 6 туда
попадает, пусть там уже лежат числа p p , p p , ..., p p , и следующим туда попадает
1 2 3 4 2k−1 2k
число A.
В разложении A участвуют простые числа, не меньшие p . Число p2 попадёт во
2k+1 2k+1
вторую коробку, так что A равно либо p3 , либо p p . Заметим, что для простых
2k+1 2k+1 2k+2
чисел, меньших 50, p3 > p p . Действительно, это неравенство равносильно нера-
2k+1 2k+1 2k+2
венству p2 > p , но 52 > 7, а 72 уже больше даже 47. Поэтому A = p p .
2k+1 2k+2 2k+1 2k+2
Замечание. На самом деле неравенство p2 > p верно всегда, что следует из известного
n n+1
постулата Бертрана: 2p > p .
n n+1
2 (4 балла). В выпуклом пятиугольнике ABCDE равны стороны AE, BC и DE, а так-
же равны углы A, B, C и D. Докажите, что точки A, B, C, D и E лежат на одной
окружности.
(Михаил Евдокимов)
Из равенств ∠A = ∠B и AE = BC следует, что EABC — равнобедренная трапеция.
Значит, точки E, A, B и C лежат на одной окружности. Аналогично точки E, D, C и B
лежат на одной окружности. Так как эти две окружности имеют три общие точки E, B
и C, это одна и та же окружность.
3

3 (5 баллов). По кругу стоят 30 мальчиков и 30 девочек. Докажите, что можно
выбрать 10 мальчиков и 10 девочек так, чтобы никакие двое из выбранных не стояли
рядом.
(Александр Грибалко)
Решение 1. Выберем произвольно первого ребенка. Двигаясь от него по часовой стрелке,
будем выбирать каждого второго и объявлять негодными пропущенных, пока не наберётся

10 детей одного пола. Пусть в этот момент выбрано, например, 10 мальчиков и k < 10
девочек. Объявим негодным следующего по кругу. Остались не рассмотренными не менее
30 − k − (10 + k) = 20 − 2k девочек. Выберем 10 − k (не более половины) из следующих
девочек, начиная с первой из них и беря их через одну, не обращая внимания на мальчиков.
Решение 2. Будем доказывать индукцией по n, что среди 3n мальчиков и 3n девочек,
стоящих по кругу, можно выбрать n мальчиков и n девочек, среди которых никто не стоит
рядом друг с другом. База n = 1 очевидна.

Пусть утверждение доказано для n−1, докажем его для n. Рассмотрим все возможные
шестёрки подряд стоящих детей. Заметим, что не может во всех шестёрках быть больше
мальчиков (так как, просуммировав по всем шестёркам, получили бы, что и всего маль-
чиков больше). Аналогично не может во всех шестёрках быть больше девочек. Поэтому
найдётся шестёрка, где девочек не меньше половины, и аналогично найдётся шестёрка, где
мальчиков не меньше половины. Двигаясь от первой из них ко второй по кругу, мы найдём
шестёрку, где ровно 3 мальчика и 3 девочки. Заметим, что среди оставшихся детей (вне
выбранной шестёрки) можно найти n−1 мальчиков и n−1 девочек, не стоящих рядом (по
предположению индукции), выберем их.

Теперь рассмотрим в выделенной шестёрке четверых детей, не стоящих с краю. Среди
них найдутся два ребёнка разного пола, не стоящие рядом (возьмём двух крайних детей, а
если они одного пола, то среди двух детей, стоящих посередине, возьмём ребёнка другого
пола и добавим к нему крайнего ребёнка, не стоящего рядом). Добавим этих двоих детей
к уже выбранным, получим искомое.
Решение 3. Занумеруем детей по часовой стрелке числами 1, 2, 3, ..., 60 и разделим
на три группы: первая — номера которых имеют остаток 1 от деления на 3, вторая —

номера которых имеют остаток 2 от деления на 3, третья — номера которых делятся на 3.
В каждой группе 20 человек, и если хотя бы в одной группе мальчиков и девочек поровну, то
задача решена — надо просто выбрать эту группу. Иначе найдутся две «соседние» группы,
в одной из которых больше мальчиков, а в другой — больше девочек. Пусть это первая
и вторая группы. Будем постепенно заменять в первой группе людей одного за другим
на людей из второй группы: №1 на №2, потом №4 на №5, потом №7 на №8, и т. д. При
каждой замене число мальчиков в изменяемой первой группе меняется не более чем на 1.
Так как изначально их было больше половины, а после полной замены исходной первой
группы на вторую мальчиков станет меньше половины, в какой-то промежуточный момент

мы получим искомую группу, в которой мальчиков и девочек поровну.
Решение 4. Докажем, что можно выбрать даже 14 девочек и 14 мальчиков. Шаблоном
назовем 28 мест «через 1», то есть набор мест вида m, m + 2, m + 4, ..., m + 54. Шаблон
назовём «Д», если в нём больше девочек, и «М» — если в нём больше мальчиков.
Если нет шаблона, в котором мальчиков и девочек поровну, то должны существовать и
«М»-шаблон, и «Д»-шаблон (иначе, суммируя (усредняя) по всем шаблонам, получили бы,


4

что всего в круге больше мальчиков или больше девочек). Тогда найдутся два «соседних»
шаблона разного типа — скажем, «М»-шаблон n, n + 2, n + 4, ..., n + 54 и «Д»-шаблон
n+1, n+3, n+5, ..., n+55. Далее двигаемся от одного шаблона к другому, каждым ходом
заменяя одного человека среди текущих 28: а именно, сначала сдвинем n + 54 в n + 55,
затем n+52 в n+53 и т. д. В промежутках у нас будут получаться уже не шаблоны, но по-
прежнему 28 человек, не стоящие рядом. После каждого хода число девочек в выбранных
28 ребятах изменяется не более чем на 1. Значит, в какой-то момент мы получим набор
из 28 человек, в котором мальчиков и девочек поровну (так как изначально было больше

мальчиков, а в конце больше девочек).
4 (5 баллов). Петя и Вася подошли к доске, и Петя нарисовал на ней несколько окруж-
ностей с различными центрами, покрасив каждый центр красным или синим цветом.
Оказалось, что если какие-то две окружности касаются друг друга, то обязательно
внешним образом, причём их центры — разного цвета. Всегда ли Вася может заменить

каждую окружность на новую с тем же центром так, чтобы выполнялось условие: ес-
ли касались друг друга две старые окружности, то соответствующие им новые тоже
касаются, но уже внутренним образом?
(Михаил Святловский)
Ответ: всегда. Пусть R , ..., R — радиусы «красных» окружностей, а r , ..., r —
1 m 1 n
радиусы «синих». Возьмём R > max(r ,...,r ) и заменим окружности с радиусами R на
1 n i
окружности с радиусами R +R , а окружности с радиусами r на окружности с радиусами
i j
R − r . Если старые окружности с радиусами R и r касались, то R + r = d (где d
j i j i j ij ij
— расстояние между их центрами). Для соответствующих новых окружностей получим
(R + R ) − (R − r ) = d , то есть они касаются внутренним образом.
i i ij
Наглядно это можно представить себе так: мы равномерно раздуваем все красные окруж-
ности и одновременно сдуваем синие (с той же скоростью), причём когда какая-то синяя
окружность «схлопывается» в точку, далее она снова начинает расти (с той же скоростью).
При этом все касания всё время сохраняются, а в моменты схлопываний внешние касания
заменяются на внутренние.
Замечание. Хотя этого и не требовалось, можно добиться того, чтобы ещё и никаких
новых касаний не появилось (между красными и синими окружностями новые касания не
возникнут, а если вдруг коснутся между собой синие окружности (или же красные), то это
будут внешние касания, и их можно избежать, ещё увеличив R).