Popov AcademyУсловие
На трёх стержнях по три диска: на первом все красные, на втором жёлтые, на третьем зелёные. За ход можно перенести только верхний диск на другой стержень со свободным местом. Нужно на каждом собрать снизу вверх зелёный, жёлтый, красный. Возможно ли это, если каждый стержень вмещает диска? А ?
О задаче · 6 класс
Записать идеюЕсть запись
Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.
Черновик не сохраняется: текст только в этой вкладке.
Черновик изменён в другой вкладке. Твой текущий текст пока сохранён здесь, автоматическая запись остановлена.
Подсказка 1
Чтобы нижний красный или жёлтый диск сменился зелёным, какой-то стержень придётся освободить.
Подсказка 2
В момент первого освобождения остальные два стержня должны вместить все девять дисков.
Разобрать решение по шагам
Докажите невозможность для четырёх
Хотя бы один из красного и жёлтого стержней должен когда-нибудь полностью опустеть, иначе его нижний диск не сменится. При первом освобождении любого стержня все дисков оказались бы на двух остальных. Но там только мест.
Постройте решение для пяти
Нумеруем стержни слева направо. Выполните ходы: →, →, →, →, →, →, →, →, →, →, →, →, →, →, →.
Проверьте результат
На каждом стержне будет зелёный, жёлтый, красный снизу вверх; вместимость не превышена. Интерактив позволяет проиграть этот план по одному ходу.
Ответ
При вместимости невозможно; при вместимости приведённый план из ходов работает.
Главная идея
Ограничение временной памяти может сделать возможную перестановку недостижимой.
Как заметить эту идею в другой задаче
Перекладывание ограничено вместимостью. Рассмотрите момент первого полного освобождения стержня: остальные должны вместить всё.
Возможная ошибка
Доказывать невозможность только неудачными попытками. Нужен аргумент, покрывающий любой план.
Источник и примечания
Источник и редакция
По материалам «Юный мыслитель», Малый мехмат МГУ, 19.03.2006, 6 класс, № 2; автор А. Банникова. Условие пересказано, подсказки и объяснение подготовлены Popov Academy.
Проверь себя
Почему одной возможности вместить дисков на двух стержнях ещё недостаточно для доказательства разрешимости?
Ответ к дополнительной задаче
Это только необходимое условие. Достаточность показывает конкретная допустимая последовательность ходов.
Тема, знания и приёмы
Игры и стратегии · Начальный вход
- Верхний и нижний диск
- Подсчёт свободных мест
Приёмы решения: Оценка и достижимость · Разбор случаев