Заполняем матрицу числами

[glorius_May]

Сколькими способами можно заполнить матрицу 4 на 4 целыми неотрицательными числами так, чтобы сумма чисел в каждой строке и в каждом столбце была равна 3?

[Bulinator]

$\sum\limits_{k=1}^4a_{ik}=\sum\limits_{k=1}^4a_{ki}=3$
У нас $4+4=8$ уравнений на $4\times 4=16$ неизвестных.

[glorius_May]

Bulinator в сообщении #397040 писал(а):

$\sum\limits_{k=1}^4a_{ik}=\sum\limits_{k=1}^4a_{ki}=3$
У нас $4+4=8$ уравнений на $4\times 4=16$ неизвестных.

И?

-- Вс янв 09, 2011 00:21:44 --

Эта задача эквивалентна другой - расположить 12 камушков на доске 4 на 4 так чтобы в каждом вертикальном ряду и в каждом горизонтальном ряду было ровно 3 камужка. Или я неправ?

[Bulinator]

Просто, выдаю мыслю для обсуждения.
Кстати эта система уравнений имеет ранг меньше 8-и.

-- Вс янв 09, 2011 02:23:07 --

glorius_May в сообщении #397041 писал(а):

Эта задача эквивалентна другой - расположить 12 камушков на доске 4 на 4 так чтобы в каждом вертикальном ряду и в каждом горизонтальном ряду было ровно 3 камужка. Или я неправ?

А... так у вас все элементы целые числа?

[glorius_May]

Bulinator в сообщении #397042 писал(а):

А... так у вас все элементы целые числа?

В роде написал что целые

[Bulinator]

Сорри, просмотрел. И решал задачу, которую сам додумал.

[glorius_May]

Bulinator в сообщении #397044 писал(а):

Сорри, просмотрел. И решал задачу, которую сам додумал.

Вот эта задача - та что я написал - на монгольской олимпиаде была.
А еще говорят будто монголы тупоябые...ни чего подобного!

[Bulinator]

glorius_May в сообщении #397041 писал(а):

Эта задача эквивалентна другой - расположить 12 камушков на доске 4 на 4 так чтобы в каждом вертикальном ряду и в каждом горизонтальном ряду было ровно 3 камужка. Или я неправ?

Допустим первая строка матрицы имеет вид 1020. Как должны быть расположены камушки?

[glorius_May]

Bulinator в сообщении #397047 писал(а):

glorius_May в сообщении #397041 писал(а):

Эта задача эквивалентна другой - расположить 12 камушков на доске 4 на 4 так чтобы в каждом вертикальном ряду и в каждом горизонтальном ряду было ровно 3 камужка. Или я неправ?

Допустим первая строка матрицы имеет вид 1020. Как должны быть расположены камушки?

Один в первой клетке и два в третьей

[caxap]

(Оффтоп)

glorius_May в сообщении #397039 писал(а):

Сколькими способами

1368?

[glorius_May]

caxap в сообщении #397097 писал(а):

(Оффтоп)

glorius_May в сообщении #397039 писал(а):

Сколькими способами

1368?

(Оффтоп)

НЭТ!
А почему 1368?

[caxap]

glorius_May в сообщении #397100 писал(а):

НЭТ!А почему 1368?

Извиняюсь, я ступил и не рассматривал варианты типа $\begin{pmatrix}1&0 &1& 1\\0& 3& 0& 0\\2& 0 &1& 0\\0& 0& 1& 2\end{pmatrix}$

(Оффтоп)

Наверное, всего матриц 2008, но законным способом получить это не могу.

[age]

Ну начнём с того, что поскольку все числа целые неотрицательные, то не может быть чисел больших 3. Далее, если на пересечении какой-то строки и какого-то столбца стоит 3, то все остальные их элементы нулевые.
Далее, есть только одна комбинация с 4 тройками, комбинаций с 3 тройками нету. Есть комбинации с двумя тройками и с одной тройкой. Это самые сложные случаи, их надо посчитать.

Далее есть $2\cdot3\cdot4=24$ комбинации с одними единицами и нулями.

Остаются комбинации с $\{0,1,2\}$. Если где-то стоит двойка, то значит должна быть единица и два нуля. Т.е. каждой двойке обязательно соответствуют два нуля и одна единица. Поэтому больше 4 двоек быть не может. Если 4 двойки, то должно быть 4 единицы и 8 нулей. Таких комбинаций по-моему только две диагональные.

Далее аналогично рассуждается для 3 двоек, двух двоек и одной двойки. В общем, считать надо, кажется.

[Bulinator]

У меня есть идея рассматривать кол-во нулей в матрице. Т.е. задавая нули с точностью до перестановок(каких?) можем восстановить матрицу.

[caxap]

Можно ещё разделить матрицу на 4 блока $2\times 2$. Нужно на каждой горизонтале и вертикале получить в сумме $6$. Возможно только следующие варианты (с точностью то перестановки строк):
Hack attempt!
Напр. блок "6" означает, что сумма чисел в нём равна 6, напр. $\begin{pmatrix}2&3\\1&0\end{pmatrix}$. Количество способов получить каждый блок:

$$$\begin{tabular}{|c|c|c|c|c|c|c|} \hline $0$&$1$&$2$&$3$&$4$&$5$&$6$\\ \hline $1$&$4$&$8$&$20$&$21$&$40$&$40$\\ \hline \end{tabular}$$

Но дальше уже проблемы: напр. если первый блок (5) $\begin{pmatrix}2&1\\1&1\end{pmatrix}$, то вариантов для второго блока (1) не $4$, а только $2$. Можно, конечно посчитать количество вариантов для каждого случая, но это долго.

(Оффтоп)

Не знаю, можно ли эту задачу решить быстро, не прибегая к перебору. Больше походит на задачу по информатике.