Решение: Камни в трёх коробках
Есть три коробки: в первой коробке 97 камней, во второй — 104, а в третьей коробке камней нет. За один ход берут по одному камню из любых двух коробок и кладут в оставшуюся. Сделали некоторое количество таких ходов.
Решите три пункта задачи и приведите развернутое обоснование.
Решение по шагам
7 шаговОбозначим количества камней в коробках через $a$, $b$ и $c$. Всего камней всегда 201. При ходе из первой и второй коробок в третью изменения имеют вид $(-1,-1,+2)$; при ходе из первой и третьей во вторую — $(-1,+2,-1)$; при ходе из второй и третьей в первую — $(+2,-1,-1)$. В каждом случае разность любых двух количеств изменяется на число, кратное 3.
В начальном состоянии $a-b=97-104=-7\equiv2\pmod3$, а $a-c=97-0=97\equiv1\pmod3$.
Для пункта а) в состоянии $(97,89,15)$ имеем $a-b=8\equiv2\pmod3$ и $a-c=82\equiv1\pmod3$. Остатки совпадают с начальными, поэтому такое состояние не противоречит инвариантам и может быть достигнуто.
Например, обозначим через $x$, $y$, $z$ число ходов соответственно из первой и второй коробок в третью, из первой и третьей во вторую и из второй и третьей в первую. Для состояния $(97,89,15)$ можно взять $x=t+10$, $y=t$, $z=t+5$. При подходящем порядке этих ходов все количества остаются неотрицательными, поэтому состояние достижимо.
Для пункта б) состояние $(0,0,201)$ невозможно: здесь $a-b=0$, тогда как в начале $a-b\equiv2\pmod3$. Сохранение разности по модулю 3 запрещает такое состояние.
В пункте в) пусть в первой коробке остался 1 камень, а в третьей — $c$ камней. Тогда во второй коробке $200-c$ камней. Из сохранения разности первой и второй коробок получаем $1-(200-c)=c-199\equiv2\pmod3$, откуда $c\equiv0\pmod3$. Так как $c\leq200$, наибольшее возможное значение — $198$.
Число 198 действительно достигается. Последовательность ходов: 96 раз брать по камню из первой и второй коробок и класть в третью; 1 раз — из второй и третьей в первую; 3 раза — из первой и второй в третью; 1 раз — из второй и третьей в первую; 1 раз — из первой и второй в третью. Состояния последовательно имеют вид $(1,8,192)$, $(3,7,191)$, $(0,4,197)$, $(2,3,196)$, $(1,2,198)$.
а) Да, могло; б) Нет, не могло; в) наибольшее число камней в третьей коробке — 198.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Забывают, что общее число камней постоянно и равно 201.
Проверяют только делимость одного количества, не рассматривая инвариант разностей по модулю 3.
Для пункта в) получают ограничение $c\leq200$, но не учитывают, что $c$ должно быть кратно 3.
Указывают максимальное значение без последовательности ходов, показывающей его достижимость.