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

5. На каждой из сторон правильного N-угольника живёт робот. Каждый робот едет по своей
стороне со своей постоянной скоростью, в вершине мгновенно разворачивается и продолжает
ехать с той же скоростью в противоположном направлении, и так далее. Когда два робота
встречаются в какой-то вершине, там вспыхивает искра. Могло ли оказаться, что в каждой

вершине искры вспыхивают с одной и той же ненулевой частотой, если
а) (6 баллов) N = 3;
б) (3 балла) N = 5?
(Александр Юран)
а) Решение 1.
Докажем, что искры не могут вспыхивать с равной частотой. Предположим, искры вспыхивают
каждые t секунд, и за время t роботы проезжают свои стороны m, n и k раз. Домножим их скорости

на mnk. Сократим скорости на их наибольший общий делитель и получим ситуацию, в которой
t
скорости целые и их наибольший общий делитель равен 1. Пусть в ней первый, второй и третий
роботы проезжают стороны за a, b и c секунд соответственно.
Тогда промежуток между вспышками — это
НОК(2a,2b) = НОК(2b,2c) = НОК(2a,2c).

Значит,
НОК(a,b) = НОК(b,c) = НОК(a,c).

Рассмотрим три последовательные искры: между первым и третьим роботом, между первым и
вторым и между вторым и третьим. Пусть между соответствующими им искрам первый, второй
и третий роботы прошли по своим сторонам l, m и n раз соответственно. Тогда l, m и n нечётны и

la + mb = nc ⇒ a + b ≡ c (mod 2).

Значит, либо a, b и c чётны, либо два из них нечётны, а третье чётно. Если все они чётны,
то a, b и c имеют общий делитель 2, что противоречит нашему предположению. А если два из
них нечётны, а третье чётно, то их попарные наименьшие кратные не все одной чётности, что
невозможно, так как они должны быть равны.
Таким образом, мы пришли к противоречию, то есть искры не могут вспыхивать через равные

промежутки времени.
б) Решение 1. Да, такое возможно. Обозначим пятиугольник через ABCDE и будем считать,
что его сторона равна 1. Все роботы начинают одновременно. Два робота начинают в A. Один из
них едет в сторону E со скоростью 2, второй — в сторону B со скоростью 1. Третий робот начинает
в B и едет к C со скоростью 2. Четвёртый начинает в середине CD едет к C со скоростью 1. Пятый
начинает в середине ED и едет к E со скоростью 1.
В каждой вершине искры будут вспыхивать через промежуток времени, равный 2: вспышки в

вершине A — в моменты времени 2k, в вершине B — в моменты 2k + 1, в вершине C — в моменты
2k+ 1, в вершине D — в моменты 2k+ 3, в вершине E — в моменты 2k+ 1, где k — неотрицательное
2 2 2
целое.
Решение 2. На рисунке внутри пятиугольника указано время в минутах, которое требуется
роботу, чтобы проехать соответствующую сторону, а у вершин — моменты времени, когда роботы
в них попадают (из этих данных можно восстановить, где роботы начинают движение в момент
времени 0: например, два «верхних» робота начинают движение по своим сторонам из верхней
вершины, а робот на нижней стороне начинает движение влево из её середины). Как видно, в
каждой вершине искрит раз в 4 минуты.


11

6 (10 баллов). Улитка проползла по плоскости по контуру замкнутой несамопересекающейся
n-звенной ломаной. Известно, что она двигалась только в трех направлениях: вверх, вправо и
вниз-влево (под углом 45◦ к горизонтали). Докажите, что n нечётно.
(Павел Кожевников)
Решение 1. Будем использовать только, что улитка может двигаться в трёх направлениях,
сонаправленных с одним из трёх векторов (cid:126)e ,(cid:126)e ,(cid:126)e , где (cid:126)e +(cid:126)e +(cid:126)e = (cid:126)0. Не умаляя общности, будем
1 2 3 1 2 3
считать, что эти векторы (cid:126)e идут в порядке (cid:126)e , (cid:126)e , (cid:126)e , считая от (cid:126)e против часовой стрелки.
i 1 2 3 1
При повороте улитки (в вершине многоугольника) текущий вектор направления (cid:126)e меняется на
i
вектор (cid:126)e (здесь и далее нижние индексы у векторов берём по модулю 3). Поэтому каждый раз
i±1
улитка поворачивается на угол между каким-то двумя соседними векторами из наших трёх по или
против часовой стрелки.
Пусть улитка проползла контур многоугольника против часовой стрелки (то есть так, что
внутренность ломаной оставалась всё время слева от улитки) и снова находится в исходной точке и
повёрнута в исходном направлении. Тогда она сделала суммарно 1 оборот против часовой стрелки
(сумма внешних углов многоугольника, взятых со знаками (в зависимости от того, поворот по
часовой стрелке или против), равна 360◦). Это значит, что количество изменений индекса на +1
было ровно на 3 больше, чем изменений на −1. Тогда общее количество изменений на ±1 нечётно,
но оно равно количеству вершин n. Этим завершается решение.
Замечание 1. На самом деле, исходную задачу (да и общий случай) можно свести к другому,
менее сложному частному случаю. А именно, рассмотрим в плоскости движения улитки треуголь-
ник с углами 45◦, 45◦, 90◦ и сторонами, параллельными направлениям движения улитки, и сделаем
аффинное преобразование плоскости, переводящее этот треугольник в равносторонний. При аф-
финном преобразовании параллельные прямые переходят в параллельные, поэтому весть путь
улитки перейдёт в новую ломаную, по которой улитка движется в трёх равноправных направле-
ниях (cid:126)e ,(cid:126)e ,(cid:126)e , образующих друг с другом равные углы (по 120◦).
1 2 3
В этом частном случае решение можно изложить более элементарно, используя лишь формулу
суммы углов n-угольника. Действительно, теперь наша ломаная ограничивает n-угольник с углами
180◦ ± 120◦; количество тех и других углов обозначим k и k соответственно. Тогда сумма углов
+ −
нашего n-угольника с одной стороны равна S = (n − 2) · 180◦ = n · 180◦ − 360◦, а с другой стороны,
S = k ·(180◦+120◦)+k ·(180◦−120◦) = (k +k )·180◦+(k −k )·120◦ = n·180◦+(k −k )·120◦.
+ − + − + − + −
Отсюда (k − k ) · 120◦ = −360◦, значит, k − k = −3. Следовательно, n = k + k = 2k − 3,
+ − + − + − −
Видим, что n нечётно, и задача решена.
12

Замечание 2. Соображения, приведённые в решении 1, показывают, что для произвольной (воз-
можно самопересекающейся) замкнутой n-звенной траектории нашей улитки (которой разрешено
двигаться в трёх направлениях) чётность числа n совпадает с чётностью количества полных обо-
ротов (вектора скорости улитки).

Можно показать, что для произвольной замкнутой ломаной четность количества оборотов сов-
падает с четностью количества ее точек самопересечения (здесь считаем, что разрешены только
самопересечения пар звеньев во внутренних точках).
Решение 2. Поставим в соответствие пути улитки (многоугольнику) кольцевое слово из букв
П (ход вправо), В (ход вверх) и Д (ход по диагонали); в этом слове нет соседних одинаковых
букв. Каждой паре соседних букв в этом слове соответствует ориентированный угол, на который
поворачивается улитка при переходе с первой стороны на вторую. Этот угол с точностью до знака

равен внешнему углу нашего многоугольника. Например, паре ПВ соответствует угол 90◦, а паре
ДВ — угол −135◦. Из теоремы о сумме внешних углов многоугольника следует, что сумма всех
этих углов равна 360◦, если улитка обходит многоугольник против часовой стрелке, и −360◦ — в
противном случае.
Будем сокращать полученное слово, а именно, тройку букв вида XY X будем заменять на
букву X. При этом чётность количества букв сохранится, а соседних одинаковых букв, очевидно,
не появится. Кроме того, сумма соответствующих углов не изменится, поскольку парам XY и
Y X соответствуют противоположные углы. Когда процесс закончится, останется слово, в котором
не только соседние, но и буквы через одну не повторяются. Таких слов есть всего два вида (с

точностью до кругового сдвига): ПВДПВД... и ПДВПДВ... Соответствующие суммы углов — это
(90◦ + 135◦ + 135◦) + (90◦ + 135◦ + 135◦) + ... и (−135◦ − 135◦ − 90◦) + (−135◦ − 135◦ − 90◦) + ...
Допустимые суммы 360◦ или −360◦ будут только в словах из трёх букв. Значит, получено одно из
таких слов, а в исходном слове число букв было нечётно, что и требовалось.
7 (14 баллов). Дано натуральное k. На столе по кругу лежат n внешне одинаковых монет

массами 1, 2, ..., n г. Вам известно, что эти массы идут по порядку, но неизвестно, по часовой
стрелке или против, и с какого места начинаются. Барон Мюнхгаузен утверждает, что вы
можете сделать k взвешиваний на чашечных весах без гирь так, чтобы по их результатам
гарантированно определить массу хотя бы одной монеты. При каком наибольшем n слова барона
будут правдой? (На каждую чашу помещается сколько угодно монет.)
(Александр Шаповалов)
Ответ: n = 2 при k = 1 и n = 3k при k > 1.

Оценка. За k взвешиваний результаты разобьют все 2n вариантов расположения монет не более
чем на 3k частей. При n > 3k в какую то часть попадут не менее 3 вариантов, среди них будут два
одинакового направления (оба по часовой стрелке или оба против часовой). Веса любой монеты
в этих двух вариантах различаются, поэтому никакой из весов нельзя определить однозначно.
Значит, n (cid:54) 3k.

Осталось разобрать ещё случай k = 1 — проверить, что n = 3 не подходит. Будем называть
монету числом, равным её весу в граммах. Заметим, что одним взвешиванием мы либо сравним
друг с другом какие-то две монеты и ни одну из трёх имеющихся не определим (мы могли сравнить
монеты 1 и 2, отложив монету 3, или сравнить монеты 2 и 3, отложив монету 1 — ни одна монета «не
осталась на месте»), либо сравним одну монету и пару оставшихся монет и в случае неравенства
снова ни одну не определим (могли взять монету 1 против монет 2 и 3, а могли взять монету 2
против 1 и 3, причём в паре монеты могут идти по кругу в любом порядке).

Алгоритм. Ясно, что при k = 1 и n = 2 достаточно сравнить две имеющиеся монеты друг с
другом, и мы узнаем их обе. Далее везде считаем, что k > 1.


13

Способ 1. Пусть n = 3k. Пусть монеты выкладываются в вершины правильного n-угольника с
вертикальной осью симметрии, проходящей через нижнюю вершину. Их веса определяются одно-
значно, если мы знаем, на какой стороне лежат веса 1 и n (скажем, что это разрыв) и направление
(по или против часовой; разрыв по часовой обозначим n1, против часовой — 1n). Пусть мы поло-

жили несколько монет на левую чашу и столько же на правую. Пометим буквой Л вершины, из
которой монеты взяты на левую чашу, и буквой П — на правую. Будем класть на каждую чашу
монеты парами из симметричных вершин, по 2 или по 4 на каждую чашу. Результат взвешивания
определяет набор подозрительных на разрыв сторон (набор зависит от направления). Будем брать
монеты из вершин как на рисунках













Эти вершины разбивают круг монет на участки. Нетрудно убедиться, что при данном направ-
лении (на рисунках — по часовой стрелке) результаты взвешивания зависят только от участка, на

который попал разрыв и не зависят от места разрыва на участке (при сдвиге разрыва по участ-
ку все веса увеличиваются или уменьшаются на одно и то же число, поэтому разность чаш не
меняется). При расположении разрыва на оси симметрии суммы в каждой симметричной паре
одинаковы, а при переходе разрыва по часовой стрелке через монету сумма на соответствующей
чаше уменьшается на n. Это позволяет узнать результаты взвешивания на участках, приведённые
на рисунке. При смене направления на противоположное и результат меняется на противополож-
ный (знак > меняется на < и наоборот.) Число сторон на участке от места A до места B по часовой
стрелке обозначим AB.
Проведём первое взвешивание по 2 монеты ЛЛ ? ПП так, чтобы было |ЛЛ| = 1, |ПП| = n/3−1

(тогда |ЛП| = |ПЛ| = n/3). При равенстве подозрительные стороны на ЛЛ + ПП, при неравенстве
на ЛП + ПЛ, при < подозрительны n1 на ЛП и 1n на ПЛ, при > наоборот.
Изначально было по n подозрительных сторон для каждого направления, теперь их осталось
по n/3. Сохранилась симметрия подозрительных сторон относительно вертикальной оси.
Случай 1: при неравенстве у нас есть два участка, симметричных друг другу, на одном подо-
зрительны только стороны вида 1n, на другом — только n1.
Случай 2: При равенстве у нас есть два участка (один длины 1), каждый участок симметричен
и подозрительная сторона может быть как вида 1n, так и вида n1. Будем проводить взвешивания
так, чтобы сохранять все перечисленные свойства.

Случай 1. У нас есть два подозрительных участка длин 3m, где один симметричен другому.
В первый раз такие участки возникли при неравенстве > или <, запомним, при каком именно.
Обозначаем их концы ЛЛ(cid:48) и Л(cid:48)Л и разбиваем каждый на три равные части монетами П и П(cid:48).
Монеты лежат по кругу так ЛПП(cid:48)Л(cid:48)Л(cid:48)П(cid:48)ПЛ. Сравниваем ЛЛЛ(cid:48)Л(cid:48) ? ППП(cid:48)П(cid:48). При равенстве подо-
зрительны монеты на П(cid:48)П и ПП(cid:48), при неравенстве того же знака как запомненное – подозрительны
участки ЛП + ПЛ, при противоположном – участки П(cid:48)Л(cid:48) + Л(cid:48)П(cid:48). Во всех случаях остаются по m
подозрительных симметричных пар.


14

Случай 2. Есть два подозрительных участка: EF длины 1 и AB длины 3m−1, где m > 1. Пусть
B(cid:48)A(cid:48) – участок длины 3m − 1 соседний по часовой с AB, который не включает EF (при этом A(cid:48)
может совпасть с E, см. рисунок).



















Выберем вспомогательную ось симметрии, чтобы AB и B(cid:48)A(cid:48) были симметричны относительно
неё. Добавим на участки две симметричные пары монет C, C(cid:48), D, D(cid:48) так чтобы |BC| = |AD| = m,
|DC| = m − 1. Взвесим ABB(cid:48)A(cid:48) ? DCC(cid:48)D(cid:48). При равенстве подозрительны участки EF + DC, при
неравенстве < подозрительны n1 на CB и 1n на AD, при неравенстве > наоборот.

Осталось заметить, что при неравенстве мы получили ситуацию случая 1, при равенстве –
случай 2, все со втрое меньшим m.
Случай 2’. Есть два подозрительных участка, EF длины 1 и AB длины 2. Взвесим FF(cid:48) ? A(cid:48)B(cid:48),
где F(cid:48), A(cid:48), B(cid:48) – соседи монет F, A, B по часовой. При равенстве подозрительная пара A(cid:48)B, при
неравенстве < имеем EF = 1n либо A(cid:48)B = n1, при неравенстве > имеем EF = n1 либо AA(cid:48) = 1n. Во
всех случаях после k испытаний остаются подозрительными два расположения противоположного
направления, ввиду нечётности общего числа монет у них есть общая монета.
Способ 2. Мы будем задавать расположение монет границей между монетами 1 и n — назовём

её началом — и направлением, в котором монеты возрастают (по или против часовой стрелки).
Для различных монет A и B назовём дугой AB множество границ между монетами от A до B
против часовой стрелки, а размером дуги — количество границ в ней.
Как и выше, считаем, что k > 1. Объясним, как при n = 3k найти вес одной монеты.
Докажем, что при нечётном количестве монет у двух разных расположений монет есть общая
монета тогда и только тогда, когда у них разное направление. Очевидно, что если направление
одинаковое, то общих монет нет. Если направления разные, то начала этих расположений разбива-
ют монеты на две группы (одна из групп может быть пустой, если начала совпадают), в одной из
этих групп будет нечётное количество монет, и средняя монеты этой группы является общей для

двух расположений. (Приведём также более концептуальное доказательство этого факта, которое
вы можете пропустить без ущерба для понимания дальнейшего решения. Рассмотрим движение,
которое переводит одно расположение монет в другое. Поскольку это меняющее ориентацию дви-
жение плоскости с неподвижной точкой, это симметрия. Но любая ось симметрии правильного
n-угольника для нечётного n проходит через вершину).
Таким образом, достаточно показать, как при n = 3k за k взвешиваний установить, что распо-
ложение — одно из двух с различными направлениями.


15

Лемма 1. Пусть дуги AB и CD не пересекаются и имеют размеры 3l. Пусть про расположение
монет известно, что либо его начало на дуге AB, а направление — против часовой стрелки, либо
начало на дуге CD, а направление — по часовой стрелке. Тогда за l взвешиваний можно найти вес
одной монеты.

Доказательство. Докажем лемму по индукции. База индукции для l = 0 очевидна, перейдём
к шагу. Пусть лемма доказана для l − 1, докажем для l. Разделим дугу AB на равные дуги
(размерами 3l−1) монетами K и L, а дугу CD — монетами M и N. Положим на левую чашу весов
монеты A, B, C и D, а на правую — монеты K, L, M и N. Заметим, что, если начало лежит вне
дуги AB или на дуге KL, то сумма масс монет A и B равна сумме масс монет K и L, аналогично
для другой четвёрки монет. Теперь разберём исходы взвешиваний:

• Если чаши уравновесились, то либо начало на дуге KL, а направление — против часовой
стрелке, либо начало на дуге MN, а направление — по часовой стрелке.

• Если левая чаша легче правой, то либо начало на LB, а направление — против часовой
стрелки, либо начало на CM, а направление — по часовой стрелке.

• Третий случай разбирается аналогично второму.

Таким образом, все случаи сводятся к предположению индукции и лемма доказана.
Лемма 2. Пусть начало лежит на дуге AB размера 3l, а направление неизвестно. Тогда найти
вес одной монеты можно за l взвешиваний.
Доказательство. Докажем лемму по индукции, база для l = 0 очевидна, перейдём к шагу.
Разделим дугу AB на три равные дуги монетами M и N. Положим монеты A и B на левую чашу,
а M и N — на правую. Разберём случаи:

• Если чаши уравновесились, начало лежит на дуге MN и направление неизвестно, так что
утверждение сводится к предположению индукции.

• Если левая чаша легче правой, то либо начало на NB и направление — против часовой
стрелки, либо начало на AM, а направление — по часовой стрелке. Таким образом, ситуация
сводится к лемме 1 для l − 1.

• Оставшийся случай разбирается аналогично предыдущему.

Перейдём к доказательству основного утверждения для круга из 3k монет. Выберем монеты A,
B, C и D так,что дуга BC имеет размер 3k−2, дуги AB и CD — 3k−1, а DA — 2·3k−2 (напомним, что
у нас k ≥ 2). Положим на левую чашу монеты A и D, а на правую — B и C. Разберём возможные

результаты взвешиваний:
• Неравенство сводится к лемме 1 для дуг AB и CD.

• Равенство разбирается несколько сложнее. Выберем монету E, которая делит дугу DA по-
полам. Положим на одну чашу монеты C и D, а на другую — E и B. Равенство сведётся к

лемме 2, а неравенство — к лемме 1.
Более подробный разбор завершения решения оставим читателю.







16

Рис. 1. Синими углами со стрелочками между монетами обозначены начало и направление ситуа-
ции, которая будет, если левая чаша легче, красными — если правая легче, зелеными — если они
равны. Соответственно, все стрелочки обозначают ситуации, возможные до очередного взвешива-

ния. «П» и «Л» указывают на монеты, которые надо положить на правую и левую чашу весов
соответственно.








17