Перекладывание камней в четырёх коробках

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

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

  1. Сумма и остатки
  2. Проверка заданного состояния

    Сначала: Сумма и остатки

  3. Законная последовательность ходов

    Сначала: Проверка заданного состояния

  4. Ответ: да

    Сначала: Законная последовательность ходов

  5. Сумма и остатки

    Сначала: Ответ: да

  6. Проверка заданного состояния

    Сначала: Сумма и остатки

  7. Ответ: нет

    Сначала: Проверка заданного состояния

  8. Сумма и остатки

    Сначала: Ответ: нет

  9. Верхняя граница содержимого

    Сначала: Сумма и остатки

  10. Законная последовательность ходов

    Сначала: Верхняя граница содержимого

  11. Ответ

    Сначала: Законная последовательность ходов

Разобранный пример

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

а) Может ли в первой коробке оказаться 121 камень, во второй — 122 камня, в третьей — 119 камней, а в четвёртой 4 камня?

б) Может ли в четвертой коробке быть 366 камней?

в) Какое максимальное число камней может быть в четвертой коробке?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. За ход каждый ящик отдаёт один камень, кроме выбранного: он получает все остальные камни. Общее число камней сохраняется. Если ящиков nn и сделано tt ходов, содержимое i-го ящика равно его первоначальному содержимому минус tt плюс nn, умноженное на число выборов этого ящика. Следовательно, разности содержимого любых двух ящиков сохраняются по модулю nn.
n=4n=4
S=366S=366
Шаг 2. Проверяем сохранение общей суммы и сравнений разностей по модулю числа ящиков. Нарушение любого из них исключает состояние. Для положительного ответа приводим последовательность разрешённых ходов.
X=(121;122;119;4)X=\left(121;122;119;4\right)
T=(0;0;0)\mathcal T=\left(0;0;0\right)
Шаг 3. В таблице для каждого блока указаны номера выбираемых получателей, число повторений блока и состояние после него. У пар номер 1 означает увеличение первого числа на 2, номер 2 - второго; у коробок номер указывает получателя камней. Все промежуточные величины допустимы. В повторяемом блоке каждая промежуточная координата меняется линейно с номером повторения, поэтому её границы проверяются по первому и последнему повторению.
P=(((4);1;(120;121;122;3));((1);1;(123;120;121;2));((2);1;(122;123;120;1));((4);1;(121;122;119;4)))\mathcal P=\left(\left(\left(4\right);1;\left(120;121;122;3\right)\right);\left(\left(1\right);1;\left(123;120;121;2\right)\right);\left(\left(2\right);1;\left(122;123;120;1\right)\right);\left(\left(4\right);1;\left(121;122;119;4\right)\right)\right)
Шаг 4. Да. Необходимые условия выполнены и приведённая последовательность ходов достигает цели.
Шаг 1. За ход каждый ящик отдаёт один камень, кроме выбранного: он получает все остальные камни. Общее число камней сохраняется. Если ящиков nn и сделано tt ходов, содержимое i-го ящика равно его первоначальному содержимому минус tt плюс nn, умноженное на число выборов этого ящика. Следовательно, разности содержимого любых двух ящиков сохраняются по модулю nn.
n=4n=4
S=366S=366
Шаг 2. Проверяем сохранение общей суммы и сравнений разностей по модулю числа ящиков. Нарушение любого из них исключает состояние. Для положительного ответа приводим последовательность разрешённых ходов.
X=(0;0;0;366)X=\left(0;0;0;366\right)
T=(3;2;3)\mathcal T=\left(3;2;3\right)
Шаг 3. Нет. Сохранённые ограничения или полный конечный список обратных кандидатов исключают цель.
Шаг 1. За ход каждый ящик отдаёт один камень, кроме выбранного: он получает все остальные камни. Общее число камней сохраняется. Если ящиков nn и сделано tt ходов, содержимое i-го ящика равно его первоначальному содержимому минус tt плюс nn, умноженное на число выборов этого ящика. Следовательно, разности содержимого любых двух ящиков сохраняются по модулю nn.
n=4n=4
S=366S=366
Шаг 2. При фиксированном остатке tt по модулю nn содержимое каждого прочего ящика не меньше его наименьшего неотрицательного остатка после вычитания tt. Вычитаем эти минимумы из общей суммы. Проверка nn возможных остатков даёт верхнюю границу для нужного ящика; дополнительное фиксированное содержимое учитываем отдельно.
T=((1;(0;1;2;363));(2;(3;0;1;362));(3;(2;3;0;361));(0;(1;2;3;360)))\mathcal T=\left(\left(1;\left(0;1;2;363\right)\right);\left(2;\left(3;0;1;362\right)\right);\left(3;\left(2;3;0;361\right)\right);\left(0;\left(1;2;3;360\right)\right)\right)
K=4K=4
Шаг 3. В таблице для каждого блока указаны номера выбираемых получателей, число повторений блока и состояние после него. У пар номер 1 означает увеличение первого числа на 2, номер 2 - второго; у коробок номер указывает получателя камней. Все промежуточные величины допустимы. В повторяемом блоке каждая промежуточная координата меняется линейно с номером повторения, поэтому её границы проверяются по первому и последнему повторению.
P=(((4);121;(0;1;2;363)))\mathcal P=\left(\left(\left(4\right);121;\left(0;1;2;363\right)\right)\right)
Шаг 4. Записываем вычисленное значение, достигаемое указанной конструкцией.
363363

Открыть задачу целиком

Попробовать самостоятельно