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

Аватар пользователя
vladb314
Сообщений: 111
Зарегистрирован: 17 июл 2007, 21:00

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

Сообщение 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 таким свойством? Рассматриваются, естественно, квадраты только чётных порядков.

Эта задача возникла из глубин теории псевдобулевой оптимизации. Надеюсь услышать хоть что-нибудь по решению этой задачи.
Последний раз редактировалось vladb314 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Nemiroff
Сообщений: 180
Зарегистрирован: 26 июл 2010, 23:55

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

Сообщение 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 вроде бы нет решения.
Последний раз редактировалось Nemiroff 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
YURI
Сообщений: 5373
Зарегистрирован: 12 дек 2007, 21:00

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

Сообщение 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)
$$


Тут же есть противоположные столбцы.
Последний раз редактировалось YURI 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
vladb314
Сообщений: 111
Зарегистрирован: 17 июл 2007, 21:00

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

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

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

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

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

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

Первые два квадрата - это просто иллюстрации к первому абзацу...
Последний раз редактировалось vladb314 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
Nemiroff
Сообщений: 180
Зарегистрирован: 26 июл 2010, 23:55

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

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

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

Да.
Вообще, если на наличие одинаковых строк наплевать, то из решения 6*6 делается 12*12.
Квадрат 8*8 существует, так что степени двойки вроде бы получаются.
Последний раз редактировалось Nemiroff 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
vladb314
Сообщений: 111
Зарегистрирован: 17 июл 2007, 21:00

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

Сообщение 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} $$

Думаю, что существуют ещё. Существует ли общий способ построения таких квадратов? Может быть, можно привлечь что-нибудь из теории латинских квадратов?
Последний раз редактировалось vladb314 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
vicvolf
Сообщений: 3155
Зарегистрирован: 13 ноя 2009, 21:00

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

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

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

Строки и столбцы по условию не должны совпадать!
Последний раз редактировалось vicvolf 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
YURI
Сообщений: 5373
Зарегистрирован: 12 дек 2007, 21:00

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

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

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

Они не будут совпадать.
Последний раз редактировалось YURI 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
vicvolf
Сообщений: 3155
Зарегистрирован: 13 ноя 2009, 21:00

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

Сообщение 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 будут симметричны относительно этой диаганали. Для примера я оставил один квадрат, который уже приведен к данному виду.
Последний раз редактировалось vicvolf 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test

Аватар пользователя
vladb314
Сообщений: 111
Зарегистрирован: 17 июл 2007, 21:00

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

Сообщение 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 нулевой главной диагональю?
Последний раз редактировалось vladb314 29 ноя 2019, 15:15, всего редактировалось 1 раз.
Причина: test


Вернуться в «Дискретная математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 3 гостей