|
|
 |
Условие
На окружности отмечены 2014 точек. В одной из них сидит кузнечик, который делает прыжки по часовой стрелке либо на 57 делений, либо на 10. Известно, что он посетил все отмеченные точки, сделав наименьшее количество прыжков длины 10. Какое?
Решение
1) Поймём, в какие точки кузнечик сможет попасть, если будет двигаться только прыжками длины 57. Пусть изначально он находится в некоторой точке A и прыгает по часовой стрелке. Поскольку 2014 = 35·57 + 19, то последней точкой, в которую он попадёт перед тем, как перепрыгнуть через A, будет точка B, отстоящая от A на 19 делений (см. рис.). Теперь мы можем считать, что кузнечик прыгает по часовой стрелке (прыжками длины 57), начиная с точки B, то есть последняя точка, в которую он попадёт перед тем, как перепрыгнуть через B, будет точка C, отстоящая от B на 19 делений. Рассуждая аналогично, получим, что кузнечик будет попадать во все точки, отстоящие от A на количество делений, кратное 19 (число 57 также делится на 19, поэтому в часть точек он попадёт раньше). Поскольку 2014 делится на 19, то в какой-то момент он попадёт в точку A, после чего процесс зациклится.
Пронумеруем все точки числами от 1 до 2014 по часовой стрелке. Тогда, если номер стартовой точки даёт остаток d от деления на 19, то прыжками длины 57 кузнечик сможет побывать во всех точках с номерами, дающими тот же остаток d (и только в них).
2) Чтобы попасть в точки с номерами, дающими иной остаток, надо сделать прыжок длины 10. Так как существует ровно 19 остатков от деления на 19, то необходимо сделать не менее восемнадцати прыжков длины 10.
3) Покажем, что восемнадцати прыжков длины 10 хватит. Обозначим через (N) группу чисел от 1 до 2014, дающих при делении на 19 остаток N. Кузнечик может обходить группы, перескакивая с одной на другую прыжками длины 10 следующим образом:
Ответ
18.
Замечания
Пусть на окружности отмечены x точек, а кузнечик прыгает прыжками длины y. Тогда он сможет побывать в тех и только в тех точках, которые отстоят от стартовой на число, кратное d = НОД(x, y). Доказать это можно следующим образом.Обозначим стартовую точку через A. Кроме того, окрасим все точки, которые отстоят от A на число, кратное d. Таких точек будет x/d = u.
Пусть кузнечик попал в клетку A вторично, сделав по пути из A в A ровно k прыжков. Тогда он преодолел путь yk, который кратен x. Значит, k делится на u. Ясно, что за это "время" кузнечик не мог дважды "посетить" одну точку. Следовательно, k = u, а кузнечик по пути из A в A побывал во всех окрашенных точках, отличных от A, по одному разу.
