Перекладывание камней

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

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

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

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

  1. Точное преобразование состояния
  2. Все достижимые состояния и путь

    Сначала: Точное преобразование состояния

  3. Точный результат и конструкция

    Сначала: Все достижимые состояния и путь

  4. Ответ: да

    Сначала: Точный результат и конструкция

  5. Точное преобразование состояния

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

  6. Все достижимые состояния и путь

    Сначала: Точное преобразование состояния

  7. Ответ: нет

    Сначала: Все достижимые состояния и путь

  8. Точное преобразование состояния

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

  9. Все достижимые состояния и путь

    Сначала: Точное преобразование состояния

  10. Точный результат и конструкция

    Сначала: Все достижимые состояния и путь

  11. Ответ

    Сначала: Точный результат и конструкция

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

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

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

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

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

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

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

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

Шаг 1. Камни из выбранных двух коробок перемещаются в третью, поэтому общее число камней сохраняется. За ход два количества уменьшаются на один, а третье увеличивается на два. Все попарные разности сохраняются по модулю три. Полное состояние - три неотрицательных количества с постоянной суммой.
Шаг 2. Исходя из начального состояния, добавляем каждое ещё не встречавшееся состояние после любого разрешённого хода. Коробки-доноры должны содержать хотя бы по камню. Состояний не больше (S+1)(S+2)2\frac{(S+1)(S+2)}{2}, поэтому процесс завершается и охватывает ровно достижимые состояния. Сохраняем предыдущий ход для конструкции. Для максимума при фиксированном количестве во второй коробке сравниваем все достигнутые состояния.
Шаг 3. Приводим вычисленные параметры, значения, перечень состояний или явную конструкцию.
T=((0;0;199);(3;1;1;3;1;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3))\mathcal T=\left(\left(0;0;199\right);\left(3;1;1;3;1;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3\right)\right)
Шаг 4. Да. Приведённый пример удовлетворяет условию.
Шаг 1. Камни из выбранных двух коробок перемещаются в третью, поэтому общее число камней сохраняется. За ход два количества уменьшаются на один, а третье увеличивается на два. Все попарные разности сохраняются по модулю три. Полное состояние - три неотрицательных количества с постоянной суммой.
Шаг 2. Исходя из начального состояния, добавляем каждое ещё не встречавшееся состояние после любого разрешённого хода. Коробки-доноры должны содержать хотя бы по камню. Состояний не больше (S+1)(S+2)2\frac{(S+1)(S+2)}{2}, поэтому процесс завершается и охватывает ровно достижимые состояния. Сохраняем предыдущий ход для конструкции. Для максимума при фиксированном количестве во второй коробке сравниваем все достигнутые состояния.
Шаг 3. Нет. Полная область возможностей или доказанное необходимое условие исключает это.
Шаг 1. Камни из выбранных двух коробок перемещаются в третью, поэтому общее число камней сохраняется. За ход два количества уменьшаются на один, а третье увеличивается на два. Все попарные разности сохраняются по модулю три. Полное состояние - три неотрицательных количества с постоянной суммой.
Шаг 2. Исходя из начального состояния, добавляем каждое ещё не встречавшееся состояние после любого разрешённого хода. Коробки-доноры должны содержать хотя бы по камню. Состояний не больше (S+1)(S+2)2\frac{(S+1)(S+2)}{2}, поэтому процесс завершается и охватывает ровно достижимые состояния. Сохраняем предыдущий ход для конструкции. Для максимума при фиксированном количестве во второй коробке сравниваем все достигнутые состояния.
Шаг 3. Приводим вычисленные параметры, значения, перечень состояний или явную конструкцию.
T=((2;2;195);(3;1;1;3;1;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3))\mathcal T=\left(\left(2;2;195\right);\left(3;1;1;3;1;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3;3\right)\right)
Шаг 4. Записываем полученный ответ.
195195

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

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