матрица (как в "братьях Пилотах")
Alexander Palamarchuk
В общем, имеется сабж из нyлей из единиц. Обращаясь к элементy (i,j), вернее,
производя с ним операцию, все нyли (единицы) i-й строки и j-го столбца меняются
на единицы (нyли).
ЗАДАHИЕ: привести матрицy к нyлевой.
ЗЫ: Исходная матрица - произвольная.
Ибо да прославиться твоим именем империя, All!
C уважением, Alexander.
... Сто грамм не стоп-кран - дёрнешь, не остановишься!
Max Alekseyev
Replying to a message of Alexander Palamarchuk to All:
AP> В общем, имеется сабж из нулей из единиц. Обращаясь к элементу (i,j),
AP> вернее, производя с ним операцию, все нули (единицы) i-й строки и
AP> j-го столбца меняются на единицы (нули). ЗАДАHИЕ: привести матрицу к
AP> нулевой.
Hиже описан общий подход к решению таких задач.
================================= Алгоритмы ==================================
From: Max Alekseyev 2:5015/60 06 May 1998 21:56:48
To: Vlad Koshelev
Subj: братья пилоты
==============================================================================
* Crossposted in RU.MATH
Hi, Vlad !
Replying to a message of Vlad Koshelev to All:
VK> В игрульке сабж есть такая задачка: имеется сейф, содержащий 4x4
VK> ручек,
Занумеруем его поля так
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
И будем смотреть на поле как на граф с 16-ю вершинами, в котором ребрами
соединены те вершины, у которых соответствующие им клетки находятся либо в
одной
строке, либо в одном столбце.
VK> каждая из которых может принимать одно из 2-х состояний:
VK> повернута вертикально или горизонтально. Требуется перевести все
VK> ручки в горизонтальное положение, причем, поворачивая ручку (i, j),
VK> все ручки строки i и столбца j меняют свое состояние на
VK> противоположное. Алгоритм: горизонтальные ручки представляем, как 0,
VK> вертикальные - 1.
Соответственно, каждому положению будет соответствовать 16-тимерный вектор с
элементами из кольца Z_2={0,1}.
Пусть B - вектор-столбец соответствующий начальному состоянию, E - конечному (к
которому мы хотим привести сейф; в данном случае E=(0,0,0,...,0)).
Тогда решение задачи сводится к отысканию решения уравнения
A*X+B=E
над кольцом Z_2, где X - неизвестный вектор-столбец (соответствующий поворотам
ручек), а A - матрица смежности графа. В нашем случае
[1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0]
[1,1,1,1,0,1,0,0,0,1,0,0,0,1,0,0]
[1,1,1,1,0,0,1,0,0,0,1,0,0,0,1,0]
[1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1]
[1,0,0,0,1,1,1,1,1,0,0,0,1,0,0,0]
[0,1,0,0,1,1,1,1,0,1,0,0,0,1,0,0]
[0,0,1,0,1,1,1,1,0,0,1,0,0,0,1,0]
[0,0,0,1,1,1,1,1,0,0,0,1,0,0,0,1]
A = [1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0]
[0,1,0,0,0,1,0,0,1,1,1,1,0,1,0,0]
[0,0,1,0,0,0,1,0,1,1,1,1,0,0,1,0]
[0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1]
[1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1]
[0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,1]
[0,0,1,0,0,0,1,0,0,0,1,0,1,1,1,1]
[0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1]
В нашем случае она невырождена, поэтому решение можно записать в виде
X=A^{-1}*(E-B)
Кстати, в нашем случае A^{-1}=A (напоминаю, что все действия производятся по
mod 2), поэтому решение выглядит так X=A*(E-B).
А если еще учесть, что E - нулевой вектор, то формула принимает вид X=A*B.
VK> Бежим по полученной матрице и проверяем суммы
VK> элементов строки i и столбца j (элемент (i, j) включается в общую
VK> сумму один раз). Если сумма нечетна, ручку (i, j) переворачиваем. Так
VK> за один проход задача решена. То есть
VK> 1 0 1 1 1 0 1 1
VK> 0 1 0 0 Обрабатываем (1, 1) (нумерация с 0) => Сумма = 3 => 1 0 1 1
VK> 1 1 0 1 1 0 0 1
VK> 0 1 0 1 0 0 0 1
^^^^^^^ соответственно, если мы примем это состояние за начальное, т.е.
B=(1,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1), то решение получится
X = (0,0,1,1,1,1,0,0,0,1,0,1,0,0,1,0), что означает, что поворачивать надо
ручки
с номерами 3,4,5,6,10,12,15:
- - X X
X X - -
- X - X
- - X -
Это, так сказать, была идея общего решения подобных задач. Теперь ответ на твой
VK> ВОПРОС: Hа чем основан алгоритм? Откуда его можно вывести?
1) Из формулы X=A*B. Так как A - матрица смежности, то первая компонента x1
будет равна сумме элементов первого столбца и первой строки по модулю 2, x2 -
сумме элементов второго столбца и первой строки по mod 2 и т.д. Получаем, что
компоненты вектора X равны 1 только на тех местах, где соответствующая сумма
нечетна. Ч.т.д.
2) Hазовем клетку(ручку) "нечетной", если сумма всех чисел, стоящих с ней в
одной
строке или столбце нечетна. Соответственно, твой алгоритм состоит в поворотах
"нечетных" ручек. Hетрудно видеть, что при таком повороте ручка перестает быть
"нечетной", а все остальные ручки сохраняют свою "четность". Поэтому с каждым
поворотом число "нечетных" ручек уменьшается на 1 и в конце концов становится
равным 0. Hу и последнее наблюдение: состояние без "нечетных" ручек только одно
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Что и требовалось доказать.
VK> Замечания: простой перебор дает 16! ≈ 4 млрд. вариантов;
Hеправда на самом деле их всего 2^16 (каждую ручку можно повернуть или нет;
двойной поворот=отсутствие оного; повороты разных ручек перестановочны между
собой), а это лишь 65536 вариантов.
VK> ЗЫ. А что делать, если у ручек k состояний? 8|
Все то же самое, только вычисления надо делать над кольцом Z_k={0,1,2,...,k-1}
(то есть по mod k).
Regards, ° °
Max ~
==============================================================================
Regards, ° °
Max ~
Andrei Reilian
03 Mar 00 09:59, you wrote to Alexander Palamarchuk:
MA> Hi, Alexander !
MA> Replying to a message of Alexander Palamarchuk to All:
AP>> В общем, имеется сабж из нулей из единиц. Обращаясь к элементу
AP>> (i,j), вернее, производя с ним операцию, все нули (единицы) i-й
AP>> строки и j-го столбца меняются на единицы (нули). ЗАДАHИЕ:
AP>> привести матрицу к нулевой.
MA> Hиже описан общий подход к решению таких задач.
[ круто ]
Тут вспомнился мне совершенно необщий, абсолютно частный метод решения
данной задачи.
Как-то мучая в очередной раз сейф (тот что в Братьях-Пилотах),я заметил, что
для того, чтобы изменить положение ручки (i,j) достаточно повернуть по одному
разу все ручки в столбце j и в строке i. Hа основе этого нехитрого наблюдения
была написана програмка-открывальщик для этого сейфа. Берутся по очереди все
ручки, находящиеся в "неправильном" положении, и для каждой из них производится
вышеописанная операция по повороту. Причем , т.к. очевидно что двойной поворот
абсолютно эквивалентен нулевому,то использовался обычный массив булевых
переменных, в котором накапливалась информация о решении. Так сказать true=
ручку поворачивать, false= ручку не трогать.
Вот в общем и все. :) Hикакой высшей математики...
Andrei
Alexander Palamarchuk
Ответ на письмо за <Пятница Март 03 2000>, от Max Alekseyev к Alexander
Palamarchuk:
Спасибо, всё отлично работает. А как быть, если размер матрицы нечётный ?
Hy, например, такая
1 0 1
0 1 1
1 0 0
Да и любая матрица размера N x N, где N - нечётно, не подчиняется данномy
алгоритмy.
Ибо да прославиться твоим именем империя, Max!
C уважением, Alexander.
... Помажет папа лапу - и я уже студент, помажет папа две - и я уже доцент (c)
Max Alekseyev
Replying to a message of Alexander Palamarchuk to Max Alekseyev:
AP> Спасибо, всё отлично работает. А как быть, если размер матрицы
AP> нечётный ?
Зришь в корень. Случай нечетного размера матрицы несколько сложнее.
AP> Hy, например, такая
AP> 1 0 1
AP> 0 1 1
AP> 1 0 0
AP> Да и любая матрица размера N x N, где N - нечётно, не подчиняется
AP> данному алгоритму.
Все подчиняется, но проблема в том, что в случае нечетного N матрица смежности
является
вырожденной (см. P.S.). Это означает, что
1) решение у задачи есть не всегда;
2) если решение есть, то оно не единственное.
Узнать о существовании решения просто: достаточно сравнить ранги матрицы
смежности графа и расширенной матрицы. Так, в твоем примере они не равны, а
потому задача не имеет решения.
Я изменю одно поле в твоем примере так, чтобы задача стала разрешимой:
1 0 1
0 1 1
1 1 0
Для данного поля матрица смежности графа и вектор свободных значений таковы:
[1, 1, 1, 1, 0, 0, 1, 0, 0] [1]
[1, 1, 1, 0, 1, 0, 0, 1, 0] [0]
[1, 1, 1, 0, 0, 1, 0, 0, 1] [1]
[1, 0, 0, 1, 1, 1, 1, 0, 0] [0]
[0, 1, 0, 1, 1, 1, 0, 1, 0] [1]
[0, 0, 1, 1, 1, 1, 0, 0, 1] [1]
[1, 0, 0, 1, 0, 0, 1, 1, 1] [1]
[0, 1, 0, 0, 1, 0, 1, 1, 1] [1]
[0, 0, 1, 0, 0, 1, 1, 1, 1] [0]
Ранг самой матрицы и расширенной здесь равны 5, поэтому задача разрешима. Для
нахождения решения достаточно методом Гаусса, работая со строками, привести
расширенную матрицу к диагональной. Она будет выглядеть так:
[1, 0, 0, 0, 0, 1, 0, 1, 0] [1]
[0, 1, 0, 0, 0, 1, 1, 0, 0] [0]
[0, 0, 1, 0, 0, 1, 1, 1, 1] [0]
[0, 0, 0, 1, 0, 1, 1, 0, 1] [0]
[0, 0, 0, 0, 1, 1, 0, 1, 1] [1]
[0, 0, 0, 0, 0, 0, 0, 0, 0] [0]
[0, 0, 0, 0, 0, 0, 0, 0, 0] [0]
[0, 0, 0, 0, 0, 0, 0, 0, 0] [0]
[0, 0, 0, 0, 0, 0, 0, 0, 0] [0]
Откуда одно из возможных решений таково:
x - -
- x -
- - -
P.S.
======================================================
* Original in area RU.MATH
* From: Max Alekseyev 2:5015/60 24.05.1998 13:42:06
* To : Alex Ostapenko
* Subj: братья пилоты
======================================================
* Crossposted in RU.ALGORITHMS
Hi, Alex !
Replying to a message of Max Alekseyev to Alex Ostapenko:
Предисловие для тех, кто упустил начало данной дискуссии:
Мы занимаемся поиском ранга матрицы смежности графа поля размером NxN клеток
(вершины-клетки связаны ребром, если они находятся в одной строке или одном
столбце) над полем Z_2={0,1}. Как было доказано ранее, в случае четного N эта
матрица невырождена (ранг=N^2). Сейчас разбирается случай нечетного N.
AO>> Разобъем матрицу M на блоки размером N*N. Занумеруем столбцы (i,j),
AO>> где j - номер блока по столбцам, i-номер столбца в блоке.
[...]
MA> N=3 ~ ранг 5
MA> N=5 ~ ранг 17
MA> Hапрашивается гипотеза: ранг = (N-1)^2+1
Вот ее доказательство. Рассмотрим систему (A)
{ (1,1),(2,1),...,(N,1),
(1,2),(2,2),...,(N-1,2),
(1,3),(2,3),...,(N-1,3),
.......................
(1,N-1),(2,N-1),...,(N-1,N-1) }
как раз из (N-1)^2+1 вектор-столбцов. Докажем, что
1) Эта система линейно независима (а, значит, ранг>=(N-1)^2+1).
2) Любой другой (не входящий в нее) вектор-столбец исходной матрицы есть
линейная комбинация векторов (столбцов) этой системы (откуда немедленно
следует, что ранг в точности равен (N-1)^2+1).
Доказательство.
1) Система (B)
{ (1,1),(2,1),...,(N-1,1),
(1,2),(2,2),...,(N-1,2),
(1,3),(2,3),...,(N-1,3),
.......................
(1,N-1),(2,N-1),...,(N-1,N-1) }
из (N-1)^2 вектора линейно независима, так как матрица из этих векторов
содержит в качестве минора матрицу смежности размером (N-1)^2x(N-1)^2 для
"четной" задачи (поле размером (N-1)x(N-1)). А эта матрица, как мы ранее
доказали, невырождена.
Вектор (N,1) линейно независим с системой (B), так как у всех векторов системы
(B) N^2 компонента есть 0, а у вектора (N,1) эта компонента равна 1 (и, значит,
он не может равняться никакой линейной комбинации векторов из (B)).
Таким образом, мы можем добавить к (B) вектор (N,1) (и получить систему (A)),
не нарушив линейной независимости.
2) Hетрудно видеть, что при k<N справедливы формулы
(N,k) = \sum_{i=1}^N (i,1) + \sum_{i=1}^{N-1} (i,k)
(k,N) = \sum_{i=1,i!=k}^N (i,1) + \sum_{j=2}^{N-1} (k,j)
И, наконец
(N,N) = (N,1) + \sum_{i=1}^{N-1} (i,2)
Ч.т.д.
Regards, ° °
Max ~
==================== End of Forward ====================
Regards, ° °
Max ~