Question

По кругу стоят 2019 камней, на одном из которых сидит лягушка. Лягушка умеет прыгать на 21 камня вперед по часовой стрелке и на 15 камней против часовой стрелке. Сколько камней может посетить лягушка с учетом того камня, на котором она изначально сидит?

Answer 1

Пусть прыжки по часовой стрелке обозначаются со знаком "плюс", а против часовой стрелке - со знаком "минус".

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

Изначально имеется два прыжка (+21) и (-15) Выполним их по очереди:

$+21-15=+6$

Итак, каким-то образом можно выполнить прыжок (+6).

Сгруппируем прыжки (+6) и (-15):

$+6-15=-9$

Таким образом, можно выполнить прыжок (-9).

Наконец, сгруппируем прыжки (+6) и (-9):

$+6-9=-3$

Также выполним прыжок (-3).

Получить прыжок с меньшим перемещением (кроме тривиально нулевого) невозможно.

Обратим внимание на то, что общее число каменей 2019, а также все рассмотренные прыжки кратны 3. Это означает, что при любом прыжке номер исходного и номер конечного камня дают одинаковые остатки при делении на 3.

Посетить все камни с номерами, дающими при делении на 3 один и тот же остаток, можно. У нас есть прыжок (-3).

Таким образом, мы посещаем либо все камни с номерами, кратными 3, либо все с номерами, дающими при делении на 3 остаток 1, либо все с номерами, дающими при делении на 3 остаток 2. И тех и других и третьих поровну в количестве $\dfrac{2019}{3}=673$ штуки.

Ответ: 673

Answer 2

При каждом прыжке лягушка изменяет свое положение на число камней, кратное НОД(21, 15) = 3. Это значит, что после каждого прыжка лягушка оказывается на камне, номер которого сравним по модулю 3 с номером камня, на котором она начинала прыгать.

Изначально лягушка сидит на камне с определенным номером, и она может посетить только те камни, номера которых сравнимы с этим номером по модулю 3. Для того чтобы найти количество камней, которые она может посетить, нужно найти количество камней, номера которых сравнимы с номером изначального камня по модулю 3, и которые находятся на расстоянии, кратном НОД(21, 15) = 3, от этого камня.

Чтобы это сделать, нужно разбить все 2019 камней на классы по модулю 3. Так как 2019 = 3*673, получаем, что в каждом классе будет 673 камня. Лягушка изначально сидит на камне, номер которого сравним с нулем по модулю 3, поэтому нужно найти количество камней, номера которых сравнимы с нулем по модулю 3, и которые находятся на расстоянии, кратном 3, от этого камня.

Из 673 камней, номера которых сравнимы с нулем по модулю 3, половина (337) находятся по часовой стрелке от начального камня, а другая половина находятся против часовой стрелки. Каждая половина состоит из камней, номера которых отличаются друг от друга на 3*k, где k - натуральное число. Чтобы найти количество камней в каждой половине, нужно разделить максимальный номер камня в этой половине на 3 и вычесть начальный номер камня, деленный на 3.

Максимальный номер камня в каждой половине определяется так:

• для половины по часовой стрелке: начальный номер камня + 21*337 = 7083;
• для половины против часовой стрелки: начальный номер камня - 15*337 = -5025.

Так как мы рассматриваем только камни с номерами, сравнимыми с нулем по модулю 3, нужно найти количество камней в интервале от -5019 до 7080, которые находятся на