Модульная арифметика (задача про обезьяну)

[xyzman]

Задача:
Пять путешественников остановились на ночлег. Они везли с собой мешок орехов и обезьяну. Ночью один из них проснулся, подошел к мешку и разделил орехи на 5 равных частей, причем один орех остался лишним. Он отдал обезьяне лишний орех, съел свою долю и снова лег спать. Потом проснулся второй путешественник и, не зная о поступке первого, проделал то же самое. Потом это же сделали по очереди остальные три путешественника. Когда утром оставшиеся орехи разделили на 5 равных частей, снова остался один орех для обезьяны. Сколько было орехов?

Решение:
Число орехов, если бы оно не менялось после описанных операций: $\frac 4 5(x-1)=x$ => $x=-4$
Число орехов, если бы не было лишних для обезьяны: любое число кратное $5^6$

Ответ: $-4+5^6k$, где $k$ - любое натуральное число.

Вопрос: не очень понятна логика решения, особенно эти "если", вроде как уходим от условия задачи. Растолкуйте, пожалуйста.

[gris]

А Вы представьте, что все орехи, мы разделили на две кучки. И делили бы на пять частей каждую кучку.
Но при этом чтобы первая кучка после делёжки и отдания ореха обезьяне не менялась.
А вторая всё время делилась на 5 частей поровну. То есть содержала $5^6 k$ орехов.
Вот в первой кучке и получается -4 ореха. Если я отдам один орех обезьяне, то станет -5 орехов. Я заберу -1 и станет снова -4

[мат-ламер]

С трудом представляется процесс поедания своей доли, т.е. минус одного ореха. Интересно, каким местом организма оно (поедание) происходит?

[gris]

Отрицательное поедание? Хм... Да...
Впрочем, можете представить, что это не реальные орехи, а просто ореховые счета в ореховом банке.

[xyzman]

gris писал(а):

Но при этом чтобы первая кучка после делёжки и отдания ореха обезьяне не менялась.

В каком смысле "не менялась"? Сколько было- столько и осталось? Т.е. было 7 орехов, 3 скормили обезьяне и 7 осталось?

Правильно ли я понимаю, что обезьяна, в общей сложности, съела 6 орехов?

[gris]

Было -1 и останется -4. Потому что Вы берёте из кучки -1 орех, что означает, что Вы кладёте туда один орех и его же отдаёте обезьянке. Остаётся столько же орехов.

Добавлено спустя 2 минуты 43 секунды:

Обезьяна каждый раз ест по одному ореху. Всего она съест 6 штук.

Добавлено спустя 3 минуты 28 секунд:

Это не единственный метод решения. Просто Вы просили растолковать его логику. Это решение хорошо тем, что распространяется на любое количество путешественников.

[xyzman]

Откуда получилось, что было -1?

[gris]

Если какое-то количество орехов не делится на 5, то мы убираем из него орехи по одному, пока оно не станет делиться на 5.
-4 не делится на 5. Уберём 1 орех. Станет -5. разделим на 5. Получим -1. Вычтем -1 из -5, получим -4. Наша кучка не изменилась и ждёт следующего путешественника.

Но это решение, оно немного шутливое. Если написать всё формально, через модули, то никаких отрицательных орехов там, разумеется не будет.

[xyzman]

gris писал(а):

-4 не делится на 5. Уберём 1 орех. Станет -5. разделим на 5. Получим -1. Вычтем -1 из -5, получим -4. Наша кучка не изменилась и ждёт следующего путешественника.

Это я понял. Было -4 ореха. Один отдаем обезьяне, получаем -5 орехов. Делим на пять и съедаем свою долю: $-5-(-1)=-4$

Не понял другое. Введя условие, что кол-во орехов остается постоянным, мы тем самым, изменили условие задачи. Разве не так?

Если Вас не затруднит, привидите, пожалуйста, дополнительно другое решение, с модулями. Может быть оно прояснит ситуацию.

[gris]

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

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

С модулями (т.е. сравнениями по модулю) я боюсь написать неточно.

Но тем не менее, попробую.
Итак, пусть у нас имеется натуральное число $N_1\equiv_5 1$
Определим рекурсивную функцию
$N_{i+1}= \frac{4(N_i -1)}{5}$.

Определить вид $N_1$, если $N_i>5$ и $N_i\equiv_5 1$ для $i=2;3;4;5;6;$

Решение.
По условию задачи после последней делёжки остался ровно один орех. Это равносильно утверждению, что $N_7$, если его рассчитать, будет натуральным числом, хотя и не обязательно $N_7\equiv_5 1$
Определим $M_i = N_i+4$, то есть $N_i = M_i-4$.
Подставив в уравнение, получим $M_{i+1} -4=\frac{4(M_i -4 -1)}{5} = \frac45 M_i-4$, откуда $M_i=\frac54 M_{i+1}$, а
$M_1=5^6\cdot\frac {M_7}{4^6}$

Поскольку $N_7$, а значит и $M_7$ натуральное число, то имеем
$M_1=5^6k$, а
$N_1=5^6k - 4, \quad k\in\mathbb N$.

Но с отрицательными орехами веселее.

[xyzman]

Если я правильно понял, то $N_i$ физически - это количество орехов после $i$-ой операции с ними. А что такое $M_i$ физически? И почему оно равно $N_i-4$, а, скажем, не $N_i-11$?

По формуле вроде так получается: $M_1=\frac54 M_2=(\frac54)^2 M_3=(\frac54)^3 M_4=(\frac54)^4 M_5=(\frac54)^5 M_6$
Поправте меня, если я ошибаюсь.

[gris]

Вы правы насчёт $M_6$. Я поправил решение.
Нам же необходимо, чтобы $N_6$, то есть число орехов перед последней делёжкой, было не просто целое, а еще и давало в остатке 1 при делении на 5. То есть просто целым должно быть число орехов, доставшихся каждому путешественнику, а значит и четырём из них, то есть как бы $N_7$.
При таком подходе физический смысл несущественен, ведь мы от орехов перешли к отвлечённым реккурентным соотношениям.
Идея решения в разложении начального числа на два слагаемых, одно из которых не меняется при последовательном применении реккурентной формулы, а второе генерирует геометрическую прогрессию.

Попробуйте получить ещё более понятное решение, если взять за неизвестное $k$ число орехов, полученных каждым путешественником на последней делёжке. И продвигаться назад к исходному числу орехов.

Вообще осторожно предложу познакомиться с разностными уравнениями.
Либо почитать книгу Маркушевича "Возвратные последовательности".