Есть четыре коробки: в первой коробке 101 камень, во второй — 102, в третьей — 103, а в четвёртой коробке камней нет. За один ход берут по одному камню из любых трёх коробок и кладут в оставшуюся. Сделали некоторое количество таких ходов.
а) Могло ли в первой коробке оказаться 97 камней, во второй — 102, в третьей — 103, а в четвёртой — 4?
б) Могло ли в четвёртой коробке оказаться 306 камней?
в) Какое наибольшее число камней могло оказаться в первой коробке?
а) Инвариант: сумма остатков количеств камней в коробках по модулю 3 постоянна. Начальные остатки: 101≡2, 102≡0, 103≡1, 0≡0, сумма 3≡0mod3.
Для конфигурации (97, 102, 103, 4) остатки: 97≡1, 102≡0, 103≡1, 4≡1, сумма 3≡0mod3, инвариант выполняется.
Также уравнения для числа ходов N и чисел добавлений xi разрешимы: например, при N=4 получаем x1=0, x2=1, x3=1, x4=2, все целые неотрицательные. Значит, конфигурация достижима.
б) Пусть в четвёртой коробке 306 камней, тогда остальные пусты. Из уравнений
xi=4конечное−начальное+Nполучаем для второй коробки:
x2=40−102+N,откуда N≡102≡2mod4, для третьей:
N≡103≡3mod4.Одновременно эти сравнения невыполнимы, значит, такая конфигурация невозможна.
в) Пусть N — число ходов, xi — сколько раз коробку i выбирали для добавления. Тогда
A=101+4x1−N,B=102+4x2−N,C=103+4x3−N,D=4x4−N.Максимизация A эквивалентна минимизации S=B+C+D. Исследуя остатки по модулю 4, находим, что минимальная S=3 достигается при N≡2mod4, B=0, C=1, D=2. Тогда
A=306−3=303.Пример реализации: сначала 26 ходов с добавлением в четвёртую коробку (изъятие из первых трёх), затем 76 ходов с добавлением в первую (изъятие из остальных). В процессе количества неотрицательны. Большее A невозможно, так как S≥3.
Ответ:
а) Да, могло.
б) Нет, не могло.
в) 303.
Проверить решение?
Покажи своё решение — проверю и покажу, где ошибка
Потренируйся на похожих — ИИ проверит твои решения
2
Задачи повышенной сложности
ФИПИ