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

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

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

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

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

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

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

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

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

  4. Ответ: да

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

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

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

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

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

  7. Ответ: нет

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

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

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

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

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

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

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

  11. Ответ

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

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

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

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

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

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

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

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

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

Шаг 1. За ход каждый ящик отдаёт один камень, кроме выбранного: он получает все остальные камни. Общее число камней сохраняется. Если ящиков nn и сделано tt ходов, содержимое i-го ящика равно его первоначальному содержимому минус tt плюс nn, умноженное на число выборов этого ящика. Следовательно, разности содержимого любых двух ящиков сохраняются по модулю nn.
n=3n=3
S=201S=201
Шаг 2. Проверяем сохранение общей суммы и сравнений разностей по модулю числа ящиков. Нарушение любого из них исключает состояние. Для положительного ответа приводим последовательность разрешённых ходов.
X=(97;89;15)X=\left(97;89;15\right)
T=(0;0)\mathcal T=\left(0;0\right)
Шаг 3. В таблице для каждого блока указаны номера выбираемых получателей, число повторений блока и состояние после него. У пар номер 1 означает увеличение первого числа на 2, номер 2 - второго; у коробок номер указывает получателя камней. Все промежуточные величины допустимы. В повторяемом блоке каждая промежуточная координата меняется линейно с номером повторения, поэтому её границы проверяются по первому и последнему повторению.
P=(((3;1;1);2;(103;98;0));((3);1;(102;97;2));((1);1;(104;96;1));((3);7;(97;89;15)))\mathcal P=\left(\left(\left(3;1;1\right);2;\left(103;98;0\right)\right);\left(\left(3\right);1;\left(102;97;2\right)\right);\left(\left(1\right);1;\left(104;96;1\right)\right);\left(\left(3\right);7;\left(97;89;15\right)\right)\right)
Шаг 4. Да. Необходимые условия выполнены и приведённая последовательность ходов достигает цели.
Шаг 1. За ход каждый ящик отдаёт один камень, кроме выбранного: он получает все остальные камни. Общее число камней сохраняется. Если ящиков nn и сделано tt ходов, содержимое i-го ящика равно его первоначальному содержимому минус tt плюс nn, умноженное на число выборов этого ящика. Следовательно, разности содержимого любых двух ящиков сохраняются по модулю nn.
n=3n=3
S=201S=201
Шаг 2. Проверяем сохранение общей суммы и сравнений разностей по модулю числа ящиков. Нарушение любого из них исключает состояние. Для положительного ответа приводим последовательность разрешённых ходов.
X=(0;0;201)X=\left(0;0;201\right)
T=(2;1)\mathcal T=\left(2;1\right)
Шаг 3. Нет. Сохранённые ограничения или полный конечный список обратных кандидатов исключают цель.
Шаг 1. За ход каждый ящик отдаёт один камень, кроме выбранного: он получает все остальные камни. Общее число камней сохраняется. Если ящиков nn и сделано tt ходов, содержимое i-го ящика равно его первоначальному содержимому минус tt плюс nn, умноженное на число выборов этого ящика. Следовательно, разности содержимого любых двух ящиков сохраняются по модулю nn.
n=3n=3
S=201S=201
Шаг 2. При фиксированном остатке tt по модулю nn содержимое каждого прочего ящика не меньше его наименьшего неотрицательного остатка после вычитания tt. Вычитаем эти минимумы из общей суммы. Проверка nn возможных остатков даёт верхнюю границу для нужного ящика; дополнительное фиксированное содержимое учитываем отдельно.
T=((0;(1;2;198)))\mathcal T=\left(\left(0;\left(1;2;198\right)\right)\right)
K=3K=3
Шаг 3. В таблице для каждого блока указаны номера выбираемых получателей, число повторений блока и состояние после него. У пар номер 1 означает увеличение первого числа на 2, номер 2 - второго; у коробок номер указывает получателя камней. Все промежуточные величины допустимы. В повторяемом блоке каждая промежуточная координата меняется линейно с номером повторения, поэтому её границы проверяются по первому и последнему повторению.
P=(((3);1;(96;103;2));((1);2;(100;101;0));((3);99;(1;2;198)))\mathcal P=\left(\left(\left(3\right);1;\left(96;103;2\right)\right);\left(\left(1\right);2;\left(100;101;0\right)\right);\left(\left(3\right);99;\left(1;2;198\right)\right)\right)
Шаг 4. Записываем вычисленное значение, достигаемое указанной конструкцией.
198198

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

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