По кругу стоят 2019 камней, на одном из которых сидит лягушка. Лягушка умеет прыгать на 21 камня вперед по часовой стрелке и на 15 камней против часовой стрелке. Сколько камней может посетить лягушка с учетом того камня, на котором она изначально сидит?
Answers & Comments
Verified answer
Пусть прыжки по часовой стрелке обозначаются со знаком "плюс", а против часовой стрелке - со знаком "минус".
Найдем, какие более простые прыжки с точки зрения перемещения (то есть по модулю) можно совершить.
Изначально имеется два прыжка (+21) и (-15) Выполним их по очереди:
Итак, каким-то образом можно выполнить прыжок (+6).
Сгруппируем прыжки (+6) и (-15):
Таким образом, можно выполнить прыжок (-9).
Наконец, сгруппируем прыжки (+6) и (-9):
Также выполним прыжок (-3).
Получить прыжок с меньшим перемещением (кроме тривиально нулевого) невозможно.
Обратим внимание на то, что общее число каменей 2019, а также все рассмотренные прыжки кратны 3. Это означает, что при любом прыжке номер исходного и номер конечного камня дают одинаковые остатки при делении на 3.
Посетить все камни с номерами, дающими при делении на 3 один и тот же остаток, можно. У нас есть прыжок (-3).
Таким образом, мы посещаем либо все камни с номерами, кратными 3, либо все с номерами, дающими при делении на 3 остаток 1, либо все с номерами, дающими при делении на 3 остаток 2. И тех и других и третьих поровну в количестве
штуки.
Ответ: 673