Головоломка

[juna]

Не могу определиться - где открыть данную тему. Поэтому, оставляю на усмотрение модераторов.
Это отчасти, конечно, носит развлекательный характер. Но меня интересует и ряд вопросов.
http://slil.ru/23745685
По данной ссылке скачивается небольшая программка, вид которой представлен здесь:

Идея состоит в том, чтобы случайно разобрав, попытаться потом собрать.

Для ладьи так или иначе я обладаю общей концепцией, а для короля и других фигур нет.
Вопросы:
1. Можно ли с помощью ладьи (короля) добиться любого состояния полей
2. Всегда ли можно, разобрав одной фигурой, собрать другой
3. Какое минимальное число нажиманий достаточно, чтобы собрать из любого положения

[нг]

Скорее всего, олимпиадные задачи. Туда и перемещаю.

[незваный гость]

А что значит разобрать/собрать? Добиться одного цвета?

И что делает определенная фигура? Инвертирует поля, на которые она ходит? Включается ли поле, на котором она стоит?

[juna]

Да нужно добиться одного цвета, например, чтобы все стали зелеными.
Вы правильно поняли, цвет клеток инвертируется на полях, куда может попасть заданная шахматная фигура с того поля, на которое нажали, которое также инвертируется.

[незваный гость]

Предполагая инверсию, включающую поле фигуры, очевидно что

Артамонов Ю.Н. писал(а):

2. Всегда ли можно, разобрав одной фигурой, собрать другой

не всегда. Пример: 1 раз король в центре. Так как доска 8 х 8, то любое собираемое ладьей поле имеет четное число инвертированных полей. QED.

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

[Brukvalub]

незваный гость писал(а):

Пример: 1 раз король в центре. Так как доска 8 х 8, то любое собираемое ладьей поле имеет четное число инвертированных полей.

-Не понял. Например, первый ход ладьи инвертирует на однородном поле 15 клеток?

[juna]

На самом деле для ладьи есть инвариант, позволяющий инверсировать только одну клетку.

[Brukvalub]

Интересен и тот факт, что в самой игрушке ниже игрового поля есть движок, позволяющий менять число клеток, так что поле 8х8- далеко не единственно возможное.

[незваный гость]

Brukvalub писал(а):

-Не понял. Например, первый ход ладьи инвертирует на однородном поле 15 клеток?

Я почему-то решил, что ладья инвертирует горизонталь либо вертикаль. Mea maxima culpa

[maxal]

Для поля $n\times n$ надо составить матрицу размера $n^2\times n^2,$ где номера строк/столбцов соответствуют клеткам на исходном поле. Элемент $(x,y)$ в этой матрице равен 1, если нажатие на клетку номер $x$ инвертирует клетку $y$, и 0 в противном случае.
Если эта матрица имеет полный ранг над полем $\mathbb{Z}_2,$ то достичь любой конфигурации клеток из любой исходной - можно, иначе - нет.

Вот еще одна аналогичная головоломка, кстати: http://bz.var.ru/comp/web/js/floor.html

Добавлено спустя 9 минут 25 секунд:

В случае ладьи ответ на первый вопрос зависит от четности $n.$ Если $n$ четно, то ответ "можно", если нечетно - "нельзя".
Подробно мы эту задачу когда-то разбирали тут.

Добавлено спустя 3 минуты 23 секунды:

Простейший алгоритм для ладьи в случае четного $n$ такой (предполагая, что цвета - это числа 0 или 1, и что нам нужно привести поле к нулевому):

Hазовем клетку(ручку) "нечетной", если сумма всех чисел, стоящих с ней в одной строке или столбце нечетна. Алгоритм состоит в поворотах "нечетных" ручек. Hетрудно видеть, что при таком повороте ручка перестает быть "нечетной", а все остальные ручки сохраняют свою "четность". Поэтому с каждым поворотом число "нечетных" ручек уменьшается на 1 и в конце концов становится равным 0. Hу и последнее наблюдение: состояние без "нечетных" ручек только одно - нулевое.

Этот алгоритм дает ответ на третий вопрос в случае ладьи и четного $n$: минимальное число ходов равно числу "нечетных" клеток.

[juna]

Очень интересно. Спасибо!
Только стоит, наверное уточнить Ваше определение:

maxal писал(а):

Hазовем клетку(ручку) "нечетной", если сумма всех чисел, стоящих с ней в одной строке или столбце нечетна.

надо наверное указать, что сама клетка не считается или говорить: сумма всех чисел, стоящих с ней в одной строке или столбце или сумма этих сумм нечетна.
иначе можно найти противоречие этому наблюдению:

maxal писал(а):

Hу и последнее наблюдение: состояние без "нечетных" ручек только одно - нулевое.

Можно еще добавить для ладьи следующие очевидные факты:
если нажать на все клетки внутри квадрата, сторона которого степень двойки, то инверсируются сразу все клетки только внутри квадрата;
если пришли к симметричному положению, то запомнив клетки одного цвета и нажав на них всегда будем переходить к симметричному положению и т.д. Исходное положение (когда все клетки одного цвета) тоже симметричное.

[maxal]

Кстати, вариант этой головоломки известен под названием Lights Out.
Ей даже посвящен ряд научных и научно-популярных публикаций. Например, в статье Turning Lights Out with Linear Algebra головоломка анализируется с помощью линейной алгебры.
У Кнута в 4-м томе "Искусства программирования" также есть серия исследовательских задач № 190-194 (стр. 67-68), связанных с этой головоломкой.

[General]

О, я про эту игру на 1 курсе исследовательскую работу писал. Именно к таким выводам и приходил.
А файл не скачивается.

[juna]

General в сообщении #284799 писал(а):

А файл не скачивается.

Если есть желание поиграться, конечно, перезалью. Но хотелось бы, чтобы форум приобрел возможность прикрепления аттачментов.