Задача о кнопочной матрице

Ian · Сообщение **Ian** » 30 ноя 2019, 14:35

Вот здесь http://www.mathhelpplanet.com/viewtopic.php?f=50&t=63903 например не решили. Я тоже не сразу.
Имеется "кнопочная матрица" 5 х 5. Каждая кнопка светится либо красным, либо зелёным цветом. При нажатии на кнопку эта кнопка и все соседние (по вертикали и горизонтали) меняют цвет. Верно ли, что из любого начального состояния можно получить полностью зелёную матрицу?

zykov · Сообщение **zykov** » 30 ноя 2019, 20:14

Ian писал(а):Source of the post Верно ли, что из любого начального состояния можно получить полностью зелёную матрицу?

Не верно.

Тут просто линейная алгебра над полем вычетов по модулю 2.

Пусть зелёный - это "0" и красный - это "1".
Состояние "матрицы" можно записать двоичным вектором длины 25.
Если мы нажимаем кнопку, то новое состояние - это сумма (по модулю 2) старого состояния и вектора в котором единицы для тех позиций, которые меняют цвет.
Если вектора-столбцы с позициями меняющими цвет объеденить в матрицу 25x25, заполнить вектор-столбец единицами для тех позиций в которых нажимаем кнопки, то произведение этой матрицы и этого вектора даст вектор позиций, которые меняют цвет в результате нажатия всех заданных кнопок.

Вобщем эта матрица имеет детерминант 0 (по модулю 2). Значит матрица не обратима. Значит есть комбинации, которые нельзя получить (или по условию задачи - занулить) никакими нажатиями.
Я просто посчитал детерминант на компьютере.
Но то что он нулевой можно понять просто из того, что некоторые нетривиальные комбинации столбцов дают нулевой результат.
Например если нажать кнопки так:

Код: Выбрать все

то ничего не изменится.

(Если бы детерминант был не нулевой, то была бы обратная матрица и умножение этой обратной матрицы на столбец начального состояния дало бы те кнопки, которые нужно нажать.)

zykov · Сообщение **zykov** » 30 ноя 2019, 20:16

Сама матрица:

Ian · Сообщение **Ian** » 30 ноя 2019, 21:19

Да, что-то общее у нас есть. У меня просто принцип Дирихле. Набор кнопок(неупорядоченный) превращающих исходную матрицу в зеленую -превращает и зеленую в исходную. Всего

2^{25} как наборов кнопок, так и возможных результатов - значит, все матрицы могут быть получены, только когда они при всех наборах кнопок различны. Но есть простой набор кнопок, не изменяющий матрицу -12 кнопок в шахматном порядке

Код: Выбрать все

Раз одну матрицу зеленую, можно получить из зеленой двумя способами, нажатием 0 кнопок либо 12, то есть матрица, которую получить нельзя. Интересно какая и сколько классов матриц, которые друг из друга нельзя получить.

zykov · Сообщение **zykov** » 30 ноя 2019, 22:38

Ian писал(а):Source of the post не изменяющий матрицу -12 кнопок в шахматном порядке

Он не работает.
Там где нажимаются (где "1"), то там изменится (т.к. все соседи нулевые, то он изменится только один раз при нажатии на центр).
Там где кнопки не нажимаются (где "0") - почти везде не меняется, кроме центров граней (где по 3 соседних единицы).

Работает тот набор, что я привел (тоже 12 кнопок). Там для нулей либо 0, либо 2 соседа с единицей. А для каждой единицы ровно 1 сосед с единицей.

Ian писал(а):Source of the post Интересно какая и сколько классов матриц, которые друг из друга нельзя получить.

Это просто. Нужно провести LU факторизацию этой матрицы 25x25 (в поле вычетов по подулю 2). Делается методом Гаусса.
Если не ошибаюсь, там пара нулевых строк получится в U. Они и дадут несовместные линейные системы (если ноль в матрице приравнять ненулевой правой части). Через L из этих столбцов можно получить несовместные состояния для исходной системы.

(Там не классы. Там линейное пространство.)

Ian · Сообщение **Ian** » 01 дек 2019, 07:03

zykov писал(а):
Ian писал(а):Source of the post не изменяющий матрицу -12 кнопок в шахматном порядке

Он не работает.

Почему же не работает. Возьмем одну клетку матрицы, она изменится столько раз сколько единиц в кресте с центром в ней.И так получилось, что у процитированной либо 4 либо 6
Опс, теперь я вижу расхождение, я решал для полного креста 9 клеток , вся вертикаль и вся горизонталь, т.е. не вчитался в условие сразу.

zykov · Сообщение **zykov** » 01 дек 2019, 08:08

Ian писал(а):Source of the post Опс, теперь я вижу расхождение, я решал для полного креста 9 клеток , вся вертикаль и вся горизонталь, т.е. не вчитался в условие сразу.

Да, я тоже сначала так сделал. Там тоже есть незануляемые комбинации.
Простой пример ничего не меняющей нетривиальной комбинации кнопок - нажать все кнопки в двух любых строках (всего 10 кнопок).

Потом перечитал условие "все соседние (по вертикали и горизонтали) меняют цвет" и поменял матрицу.

zykov · Сообщение **zykov** » 01 дек 2019, 08:17

Провел LU факторизацию.
Да, оказалось всего два линейно независимых варианта, которые нельзя занулить.
Например первый - когда горит только одна лампочка сверху слева (верхняя строка 10000), второй - горит только одна лампочка сверху вторая слева (верхняя строка 01000).
Третий вариант - это их единственная линейная комбинация, когда обе горят (верхняя строка 11000).

Таким образом из нулевой "матрицы" получаем все возможные зануляемые комбинации произвольным нажатием кнопок (25%).
А из каждой из этих трёх незануляемых комбинаций получаем так же ещё три класса незануляемых комбинаций (на каждый по 25%).
Никакое нажатие кнопок не переводит из одного из этих классов в другой.

Ian · Сообщение **Ian** » 01 дек 2019, 09:03

Вы обсуждали линейное пространство или группу образуют все преобразования кнопочных матриц. И ЛП, и группу. Либо 25-мерное линейное пространство над полем

Z_2, либо прямое произведение 25 групп

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

2^{25-k} различных, считая и ее саму.

zykov · Сообщение **zykov** » 01 дек 2019, 09:38

Ian писал(а):Source of the post полем

Вроде обозначают $F_2$

,

или

.
Или

- ещё одно обозначение?

zykov · Сообщение **zykov** » 01 дек 2019, 09:48

Ian писал(а):Source of the post Либо 25-мерное линейное пространство над полем , либо прямое произведение 25 групп по сложению, это одно и то же.

Не понял, что имеется ввиду...
В линейной алгебре есть формула детерминанта, формула обратной матрицы через детерминанты, алгоритм Гаусса (приведение матрицы к треугольному виду). Всё это работает для любого поля (не только для $R$

и

). В теории групп этого нет...

Ian · Сообщение **Ian** » 01 дек 2019, 20:55

zykov писал(а): В теории групп этого нет...

В теории групп есть получше вещи, которые я и хотел привлечь для нахождения числа классов("орбит группы преобразований") для всевозможных размеров кнопочных матриц (может, и размера n) без прямого перебора. Типа Леммы Бернсайда https://en.wikipedia.org/wiki/Burnside's_lemma

zykov · Сообщение **zykov** » 01 дек 2019, 21:49

Количество может и получится найти.
А вот определить, является ли зануляемым выбранное начальное состояние? И если оно зануляемое, то какие кнопки нажимать?
Это как раз дело для линейной алгебры.

zykov · Сообщение **zykov** » 04 дек 2019, 12:31

Например 10000, 01000, 11000 (в верхней строке, остальные строки нулевые) - базовые незануляемые.
Далее 10100 и 01100 тоже незануляемые.

А 11100 уже зануляемая. Матрица нажатий:
00010
11011
00010
11100
01000

Если везде (во всех строках) только единицы, то это тоже зануляемый вариант. Матрица нажатий:
01101
01110
00111
11011
11000

zykov · Сообщение **zykov** » 04 дек 2019, 13:43

Да, кстати.
Нуль-пространство матрицы тоже двумерно.
Два базисных элемента - тот что я приводил и он же повернутый на 90 градусов.
11011
00000
11011
00000
11011

10101
10101
00000
10101
10101

Плюс к ним еще их сумма
01110
10101
11011
10101
01110

Т.е., если есть какая-то комбинация кнопок, то ещё 3 комбинации дадут тот же эффект (сумма исходной и одной из этих трёх).
Это если надо найти для данного эффекта комбинацию с наименьшим количеством кнопок, то нужно эти 4 варианта перебрать.

Ian · Сообщение **Ian** » 04 дек 2019, 20:12

На мех-мате появилась новая версия этой задачи

: Безымянный1.png (110.63 KiB) 27377 просмотра

Изменился крест 3х3 на крест 5х5, а также мысль исследователя (не знаю, чья) устремилась на размерность дефектного подпространства, что и предсказывалось.

zykov · Сообщение **zykov** » 04 дек 2019, 22:17

Ian писал(а):Source of the post Изменился крест 3х3 на крест 5х5,

Здесь уже нуль-пространство и пространство незануляемых получается 6-мерным.
Вот базис "нулевых" нажатий (кооторые ничего не меняют):

Код: Выбрать все

00001  11101  11011  10111  01111  11111
11110  00010  00100  01000  10000  00000
11110  00010  00100  01000  10000  00000
11110  00010  00100  01000  10000  11111
00001  00010  00100  01000  10000  00000

Из них можно ещё 57 ( $2^6-6-1$

) нетривиальных "нулевых" комбинаций получить в виде линейных комбинаций этих шести.

Насчет количества нажатий, то поскольку матрица U имеет внизу 6 нулевых строк, то при условии что решение существует, система будет совместна и последние 6 элементов вектора нажатий можно положить равными нулю. Тогда оставшиеся первые 19 определяются единственным образом по начальной комбинации лампочек.
Т.е. если решение существует, то есть его вариант когда мы нажимаем какие-то кнопки из 19 выбранных кнопок (другие 6 не нажимаются независимо от начальной комбинации).
Например, достаточно нажать какие-то из отмеченный (цифрой "1") кнопок:
11111
11111
11111
11110
00000

zykov · Сообщение **zykov** » 04 дек 2019, 22:21

Откуда у него 24 - не знаю.
Может имелось ввиду, что полностью матрица не анализируется и если найти две разных нетривиальных "нулевых" комбинации, то это уже покажет, что можно занулить не более чем за 25-2=23 нажатий.

zykov · Сообщение **zykov** » 09 дек 2019, 13:41

zykov писал(а):Source of the post Здесь уже нуль-пространство и пространство незануляемых получается 6-мерным.

Несколько поторопился, пару нулей не заметил.
Там получается ранг 17, а не 19. Нуль-пространство будет 8-мерным, а не 6-мерным.
К базису нулевых нажатий ещё нужно два варианта добавить.

Код: Выбрать все

00001  11101  11011  10111  01111  11111  11111  11111
11110  00010  00100  01000  10000  00000  00000  11111
11110  00010  00100  01000  10000  00000  11111  00000
11110  00010  00100  01000  10000  11111  00000  00000
00001  00010  00100  01000  10000  00000  00000  00000

Соответственно, из них можно ещё 247 ( $2^8-8-1$

) нетривиальных "нулевых" комбинаций получить в виде линейных комбинаций этих восьми.

Так же, если решение существует, то есть его вариант когда мы нажимаем какие-то кнопки из 17 выбранных кнопок (другие 8 не нажимаются независимо от начальной комбинации).
Например, достаточно нажать какие-то из отмеченный (цифрой "1") кнопок:
11111
11110
11110
11110
00000

zykov · Сообщение **zykov** » 09 дек 2019, 14:09

zykov писал(а):Source of the post К базису нулевых нажатий ещё нужно два варианта добавить.

Код: Выбрать все
00001 11101 11011 10111 01111 11111 11111 11111 11110 00010 00100 01000 10000 00000 00000 11111 11110 00010 00100 01000 10000 00000 11111 00000 11110 00010 00100 01000 10000 11111 00000 00000 00001 00010 00100 01000 10000 00000 00000 00000

Кстати, первый вариант можно заменить на
11111
00000
00000
00000
11111
Тогда будет 4 однотипных + 4 однотипных.

Или на
11110
00001
00001
00001
00001
Тогда будет 5 однотипных + 3 однотипных.

(Все 9 вместе уже будут линейно зависимые. Сумма 5 такая же, как сумма у других 4.)

Портал Естественных Наук, версия 1.1