Есть задача (на форуме нашёл) о том как из рандомно заполненого квадрата 3*3 сделать магический, пользуясь циклическими сдвигами строк или столбцов. Сама задача несложная (если только не требовать минимизации числа ходов).
Однако я не могу придумать как можно доказать (и вообще так ли это) что поменять местами два числа (оставив остальные на местах) такими манипуляциями нельзя. (для исходной задачи это в общем и не нужно — вроде можно обойтись меняя числа парами)
Наверняка в какой-нибудь книжке головоломок подобное обсуждалось, но что-то не могу подобрать подходящих ключевых слов для гугла.
напишите бфс и проверьте достижимы ли эти 2 состояния.
это будет работать как и для
так и для
ибо размер всего 3*3
напишите бфс и проверьте достижимы ли эти 2 состояния.
Как потом предлагается экстраполировать на случай квадрата 100500*100500 (и сохраняется ли это для него?)
P.S. А как теперь цитатки делать в сообщениях?
Если хоть один размер четный — поменять местами два элемента можно всегда. Вот задача, в разборе можно посмотреть, как делается обмен двух соседних элементов (он тривиальным образом расширяется на любой размер).
Вот так:
Вроде бы нечётный цикл — это чётная перестановка, а поменять местами два числа — нечётная. Поэтому понятно, что чётными перестановками нельзя получить нечётную.
А... если рассмотреть циклический обмен трёх произвольных чисел вообще, а квадрат как перестановку чисел от 1 до 9... да, круть — пожалуй, тогда ясно, спасибо. ;-)
Ага, то же самое, что в пятнашках соседние поменять нельзя. Правда, там букв в доказательстве больше.
Ну... Как сказать. Если в пятнашках считать пустое поле 16-й шашкой, то перемещение будет являться циклическим сдвигом (на произвольное число полей). При этом перемешение всего одной шашки будет "обменом" её с фиктивной 16-й...
В общем про пятнашки-то я в курсе, но там по-моему сложнее задача и потому я не понял как свести эту к пятнашечному варианту...
Хотя если рассмотреть пятнашки на поле 5*5 (24-ряшки, ну и сокращеньице) то пожалуй можно и свести (рассматривая нашу задачу как центральные 9 шашек и гоняя остальные вокруг них)...