He магические квадраты

vladb314 · Сообщение **vladb314** » 01 окт 2010, 10:11

Всем доброго дня! Предлагаю рассмотреть следующую задачу. Требуется найти квадрат, заполненный цифрами 0 и 1, у которого в каждой строке и в каждом столбце количество нулей было бы равно количеству единиц, причём в нём не должно быть ни одной одинаковой строки и ни одного одинакового столбца. Понятно, что эта задача не такая трудная, так как решения для порядка 2 и 4 легко находятся подбором:

$$
\left( {\begin{array}{cñ}
1 & 0 \\
0 & 1 \\
\end{array}} \right)
$$</span> <span class=

$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">
\left( {\begin{array}{cñññ}
0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 1 & 0 & 0 \\
\end{array}} \right)
$$

Однако требуется ещё, чтобы каждая строка не являлась противоположностью ни одной другой строки, также и чтобы столбец не являлся противоположностью ни одного другого столбца. Для 2-го порядка, очевидно, такого квадрата не существует. Существует ли квадрат какого-нибудь порядка c таким свойством? Рассматриваются, естественно, квадраты только чётных порядков.

Эта задача возникла из глубин теории псевдобулевой оптимизации. Надеюсь услышать хоть что-нибудь по решению этой задачи.

Nemiroff · Сообщение **Nemiroff** » 01 окт 2010, 10:30

$$\left( {\begin{array}{cñññ} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ \end{array}} \right)$$
Подойдет? Для n=4 вроде бы нет решения.

YURI · Сообщение **YURI** » 01 окт 2010, 10:38

vladb314 писал(а):Source of the post
$$
\left( {\begin{array}{cñññ}
0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 1 & 0 & 0 \\
\end{array}} \right)
$$

Тут же есть противоположные столбцы.

vladb314 · Сообщение **vladb314** » 01 окт 2010, 10:43

Nemiroff писал(а):Source of the post
Подойдет? Для n=4 вроде бы нет решения.

O! Спасибо! Вы подбором решили?

Буду теперь знать, что такие квадраты существуют. И это не может не радовать.
Есть ли общий метод решения этой задачи? У меня просто рассматривается более специальный случай, где порядок есть степень двойки, например, 1024.

YURI писал(а):Source of the post
Тут же есть противоположные столбцы.

Первые два квадрата - это просто иллюстрации к первому абзацу...

Nemiroff · Сообщение **Nemiroff** » 01 окт 2010, 10:48

O! Спасибо! Вы подбором решили?

Да.
Вообще, если на наличие одинаковых строк наплевать, то из решения 6*6 делается 12*12.
Квадрат 8*8 существует, так что степени двойки вроде бы получаются.

vladb314 · Сообщение **vladb314** » 02 окт 2010, 19:19

Я нашёл несколько квадратов 8 на 8:

$\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

Думаю, что существуют ещё. Существует ли общий способ построения таких квадратов? Может быть, можно привлечь что-нибудь из теории латинских квадратов?

vicvolf · Сообщение **vicvolf** » 02 окт 2010, 20:00

Nemiroff писал(а):Source of the post
Вообще, если на наличие одинаковых строк наплевать, то из решения 6*6 делается 12*12.

Строки и столбцы по условию не должны совпадать!

YURI · Сообщение **YURI** » 02 окт 2010, 20:32

vicvolf писал(а):Source of the post Строки и столбцы по условию не должны совпадать!

Они не будут совпадать.

vicvolf · Сообщение **vicvolf** » 02 окт 2010, 21:34

vladb314 писал(а):Source of the post
$\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$
Существует ли общий способ построения таких квадратов?

Мне кажется. что перестановкой столбцов можно привести любой такой квадрат к виду, что на диаганали у него будут все 0 или 1 и остальные 0 и 1 будут симметричны относительно этой диаганали. Для примера я оставил один квадрат, который уже приведен к данному виду.

vladb314 · Сообщение **vladb314** » 05 окт 2010, 06:01

vicvolf писал(а):Source of the post
Мне кажется. что перестановкой столбцов можно привести любой такой квадрат к виду, что на диаганали у него будут все 0 или 1 и остальные 0 и 1 будут симметричны относительно этой диаганали. Для примера я оставил один квадрат, который уже приведен к данному виду.

Интересная гипотеза! Правда, мне было удобнее работать c перестановкой строк. Оказывается, для каждого из 6-ти найденных квадратов существует 8 перестановок строк, приводящих их к симметричному виду. Причём во всех случаях из этих 8-ми перестановок была ровно 1, которая приводила к квадрату c нулевой главной диагональю!

$\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

$\begin{array}{cccccccc} 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \end{array}$

Первый квадрат уже является симметричным c нулевой главной диагональю, поэтому приведён без изменения. Второй квадрат получается из второго, приведённого выше, перестановкой строк (2, 3) и (4, 5), третий - перестановкой строк (1, 2) и (4, 5) и т.д.

Симметричных квадратов c единицами на главной диагонали не было найдено ни одного.

Для любых ли квадратов c заданным свойством справедливо, что они перестановками строк могут быть приведены к симметричному виду c нулевой главной диагональю?

yourdomain.com