Таблицы Брадиса

Заметим, что при этом понятия

Заметим, что при этом понятия

Элементы математики в задачах - Г. А. Мерзон

Задача 21*. Дан правильный 50-угольник. В одной из его вершин стоит доктор Фауст. У него есть три возможности: 1) бесплатно перей­ти в диаметрально противоположную точку; 2) заплатив Мефистофе­лю 1 рубль 05 копеек, перейти на соседнюю вершину против часовой стрелки; 3) получив от Мефистофеля 1 рубль 05 копеек перейти на соседнюю вершину по часовой стрелке. Известно, что доктор Фауст везде побывал (хотя бы один раз). Докажите, что на каком-то отрезке пути кто-то кому-то заплатил не меньше 25 рублей.

Указание. «Склейте» пары противоположных вершин.

144                                    Теория графов 1

Набросок решения. Склеим пары противоположных вершин (то есть рассмотрим 25-угольник, вершины которого соответствуют парам противоположных вершин исходного 50-угольника). Заметим, что при этом понятия «по часовой» и «против часовой» стрелки сохра­няют смысл. Учитывая, что 1,05 ■ 24 = 25,20, задача сводится к следу­ющей:

Гуляя по сторонам правильного 25-угольника, доктор Фауст побывал во всех вершинах. Докажите, что на каком-то участке времени модуль разности числа ходов доктора по и против часовой стрелки не меньше 24.

Занумеруем вершины 25-угольника числами от 0 до 24 по часовой стрелке и рассмотрим отображение из множества целых чисел в 25- угольник, сопоставляющее числу а вершину с номером «остаток от деления а на 25». Сопоставим пути доктора Фауста на 25-угольнике путь на целочисленной прямой, начинающийся в точке 0, в котором движению против часовой стрелки по 25-угольнику соответствует движению влево на прямой, а движение по часовой стрелке соответ­ствует движению вправо.

Все прообразы точки с номером к, лежащей на 25-угольнике, име­ют вид к + 25п, п є Ж. Рассмотрим самую левую и самую правую точки на прямой, в которых побывал доктор Фауст. Тогда расстояние между ними не меньше 24, так как доктор Фауст побывал во всех точках 25- угольника, а следовательно, во время прогулки по прямой встретил все остатки от деления на 25. Это завершает решение задачи.