Есть четыре коробки: в первой коробке 101 камень, во второй $—$ 102, в третьей $—$ 103, а в четвёртой коробке камней нет. За один ход берут по одному камню из любых трёх коробок и кладут в оставшуюся. Сделали некоторое количество таких ходов.
а) Могло ли в первой коробке оказаться 97 камней, во второй $—$ 102, в третьей $—$ 103, а в четвёртой $—$ 4?
б) Могло ли в четвёртой коробке оказаться 306 камней?
в) Какое наибольшее число камней могло оказаться в первой коробке?
Задание с развёрнутым ответом. Запишите решение и сравните его с разбором.
Ответ: а) да; б) нет; в) $303$.
Решение
Порядок координат в записи $(a;b;c;d)$ соответствует четырём коробкам. При ходе получатель приобретает 3 камня, а три донора теряют по одному. Сумма сохраняется:
$$
101+102+103=306.
$$
Изменения $+3$ и $-1$ отличаются на 4. Значит, по остатку при делении на 4 количества во всех коробках изменяются одинаково. Остаток разности любых двух количеств сохраняется. Это поможет исключать невозможные результаты.
а) Направим камни последовательно в коробки 4, 2, 3, 4. Покажем каждый ход:
$$
(101;102;103;0)\to(100;101;102;3)
$$
$$
\to(99;104;101;2)\to(98;103;104;1)\to(97;102;103;4).
$$
В каждом переходе у всех трёх доноров есть камень. Нужный результат достигнут. Ответ: да.
б) Если в четвёртой коробке 306 камней, три остальные пусты. Разность первой и второй тогда равна нулю. Но первоначально она равна $101-102=-1$; разность 0 и $-1$ равна 1 и не делится на 4. Это противоречит сохранению остатка разности. Ответ: нет.
в) Первоначальные количества во второй, третьей и четвёртой коробках равны $102,103,0$. Их остатки при делении на 4 равны $2,3,0$, то есть различны. При ходах они все сдвигаются на один и тот же остаток, поэтому остаются различными. Следовательно, сами три количества тоже различны. Три различных неотрицательных целых числа имеют сумму хотя бы $0+1+2=3$. Значит, первой коробке может достаться не больше:
$$
306-3=303\text{ камней}.
$$
Чтобы доказать достижимость, найдём повторяемую последовательность ходов. Из состояния $(a;b;c;0)$ сначала направим камни в четвёртую коробку, затем три раза в первую:
$$
(a;b;c;0)\to(a-1;b-1;c-1;3)
$$
$$
\to(a+2;b-2;c-2;2)\to(a+5;b-3;c-3;1)\to(a+8;b-4;c-4;0).
$$
За четыре хода первая коробка получает 8, вторая и третья теряют по 4, четвёртая снова пуста. Повторим это 25 раз:
$$
(101+25\cdot8;102-25\cdot4;103-25\cdot4;0)
=(301;2;3;0).
$$
Все повторы разрешены: перед последним повтором во второй и третьей ещё $6$ и $7$ камней, а внутри повтора они отдают только по четыре; первая всё время положительна; четвёртая после получения трёх может трижды отдать по одному. Осталось два хода:
$$
(301;2;3;0)\to(300;1;2;3)\to(303;0;1;2).
$$
Сначала получатель четвёртая коробка, затем первая. Каждый донор содержит необходимый камень. Верхняя граница 303 достигнута.
Ответ: а) да; б) нет; в) 303 камня.