yourdomain.com

Всем доброго дня! Предлагаю рассмотреть следующую задачу. Требуется найти квадрат, заполненный цифрами 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 таким свойством? Рассматриваются, естественно, квадраты только чётных порядков.

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

$$\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 вроде бы нет решения.

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)
$$

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

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

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

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

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

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

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

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

Я нашёл несколько квадратов 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}$

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

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

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

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

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

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 будут симметричны относительно этой диаганали. Для примера я оставил один квадрат, который уже приведен к данному виду.

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

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

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

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

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

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

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

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

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

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

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

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