Задача №15484

Есть три коробки: в первой коробке 97 камней, во второй — 104, а в третьей коробке камней нет. За один ход берут по одному камню из любых двух коробок и кладут в оставшуюся. Сделали некоторое количество таких ходов.

а) Могло ли в первой коробке оказаться 97 камней, во второй — 89, а в третьей — 15?

б) Мог ли в третьей коробке оказаться 201 камень?

в) В первой коробке оказался 1 камень. Какое наибольшее число камней могло оказаться в третьей коробке?

Общее число камней постоянно: $97+104+0=201\text{.}$ За один ход из двух коробок берут по 1 камню, в третью добавляют 2. Инвариант: разность чисел камней в любых двух коробках сравнима по модулю 3 с начальной разностью. Начальные разности: $97-104\equiv -7\equiv 2(\mathrm{mod}3)\text{,}$ $97-0\equiv 1(\mathrm{mod}3)\text{,}$ $104-0\equiv 2(\mathrm{mod}3)\text{.}$

а) Проверим состояние (97,89,15): сумма 201, разности: $97-89=8\equiv 2(\mathrm{mod}3)\text{,}$ $97-15=82\equiv 1(\mathrm{mod}3)\text{,}$ $89-15=74\equiv 2(\mathrm{mod}3)$ — инварианты соблюдаются.

Покажем явную последовательность ходов: сделаем 10 ходов типа «из первой и второй кладём в третью»: (97,104,0) → после 10 ходов: (87,94,20). Затем 5 ходов типа «из второй и третьей кладём в первую»: (87,94,20) → после 5 ходов: (97,89,15). Все ходы возможны, так как количества неотрицательны.

б) Состояние (0,0,201): разность первой и второй $0-0=0\equiv 0(\mathrm{mod}3)\text{,}$ но начальная разность $97-104\equiv 2(\mathrm{mod}3)\text{,}$ противоречие.

в) Пусть в конце в первой коробке 1 камень, во второй $b\text{,}$ в третьей $c\text{.}$ Тогда $1+b+c=201\text{,}$ откуда $c=200-b\text{.}$ Инвариант: $1-b\equiv 97-104\equiv 2(\mathrm{mod}3)\text{,}$ поэтому $b\equiv 2(\mathrm{mod}3)\text{.}$ Максимизируем $c$ - минимизируем $b\text{.}$ Наименьшее возможное $b=2\text{,}$ тогда $c=198\text{.}$

Покажем достижимость: можно подобрать количества ходов. Пусть $x$ — число ходов типа «из второй и третьей в первую», $y$ — «из первой и третьей во вторую», $z$ — «из первой и второй в третью». Решая систему, получаем

$$b=8-3(x-y),c=192+3(x-y).$$

При $x-y=2$ имеем $b=2\text{,}$ $c=198\text{.}$ Пример последовательности: 96 ходов $z\text{,}$ затем 1 ход $x\text{,}$ затем 3 хода $z\text{,}$ затем 1 ход $x\text{,}$ затем 1 ход $z\text{.}$ Все промежуточные количества неотрицательны.

Ответ:

а) да

б) нет

в) 198