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

[ewert]

Если есть хотя бы одна тройка, то количество (664) находится сравнительно быстро -- там шесть вариантов, но они достаточно простые. Проблема в том, как наковырять 1344 оставшихся варианта для случаев, когда в матрице присутствуют только единицы и двойки.

[Bulinator]

Есть два типа строк, состоящих из трех единиц и одного нуля(пример 1101) и сосотоящих из одной двойки, одной единицы и двух нулей.
Будем искать кол-во мартиц с одной двойкой
Пусть первая строка имеет вид:
1020
xxxx
xxxx
xxxx
Последний столбец сразу восстанвливается:
1020
xxx1
xxx1
xxx1
Далее, единица в предпоследнем столбце может быть в трех разных местах. Задвая ее сразу же восстанавливаем матрицу. Например единица в предпоследнем столбце находится на второй строке, тогда матрица имеет вид:
1020
0111
1101
1101
В итоге, строк второго типа у нас 12, они могут находится в любой из четырех строк и еще 3 разных выбора позиции единички:
$12\cdot 4\cdot 3=144$.
Нигде не наврал?

[ewert]

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

Нигде не наврал?

Нет, всё верно.

Для двух двоек -- выстроим их по диагонали:

2ххх
х2хх
хххх
хххх

В правом верхнем квадратике два на два каждый столбец имеет не менее одной единички (иначе в последних столбцах не набираются тройки), но и каждая строка -- не более одной единички. Итого получаем два варианта:

2001 2010
0210 0201
хх11 хх11
хх11 хх11

После чего оставшийся левый нижний квадратик заполняется тоже двумя способами, итого дважды два -- четыре. Умножаем на возможное количество расстановок двоек: $C_4^2\cdot4\cdot3=72$ и получаем окончательно 288 вариантов, и это правда.

Аналогично можно насчитать 672 варианта с тремя двойками и 216 вариантов с чётырьмя. Но всё это страшное занудство.

-- Вс янв 09, 2011 19:28:34 --

Да, а 144 для одной двойки я бы считал так. Эту двойку можно расположить 16 способами; для определённости считаем, что она в левом верхнем углу. Тогда в первой строке и в первом столбце стоят по одной единичке, это 9 вариантов; для определённости берём вариант

2100
1ххх
0ххх
0ххх

Он заполняется однозначно: крестики в последних двух строках и в последних двух столбцах обязаны быть единичками, после чего последний (левый верхний) крестик оказывается нулём. Итого $16\cdot9=144$.

[Bulinator]

Утверждение:
Задавая нули матрицы мы, тем самым однозначно задаем матрицу.
Пример:
$ \left( \begin{array}{cccc} x &0 &x & 0\\ 0 & x & x &x \\ x & x & 0 & x\\ x & x & 0 & x \\ \end{array} \right)\Rightarrow \left( \begin{array}{cccc} 1 & 0 & 2 & 0\\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 \\ \end{array} \right) $


$ \left( \begin{array}{cccc} x &0 &x & 0\\ 0 & x & 0 &x \\ x & 0 & x & x\\ 0 & x & x & x \\ \end{array} \right)\Rightarrow \left( \begin{array}{cccc} 2 & 0 & 1 & 0\\ 0 & 2 & 0 & 1 \\ 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 \\ \end{array} \right) $
и.т.д.

В каждой строке и в каждом столбце должно быть как минимум по одному нулю. Остается понять, как эти нули (не)могут быть расположены.

(Оффтоп)

Но это уже утром

[ewert]

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

Задавая нули матрицы мы, тем самым однозначно задаем матрицу.

Вовсе нет. Например:

хх00
хх00
00хх
00хх

-- это вовсе не один вариант.

[Bulinator]

ewert
Ну да, я об этом еще ночью засыпая подумал. Случай с 8-ю нулями и 4-мя двойками стоит особняком.

[ewert]

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

Случай с 8-ю нулями и 4-мя двойками стоит особняком.

х00х
0х00
00х0
х00х

Не знаю, сколько особняков ещё можно понастроить, но вряд ли это занятие благодарное.

[Ales]

Такие целочисленные матрицы (сумма строки = сумма столбца = одинаковое целое) образуют группу по сложению.

[ewert]

Ales в сообщении #397505 писал(а):

Такие целочисленные матрицы (сумма строки = сумма столбца = одинаковое целое) образуют группу по сложению.

Допустим. И что?...

[Ales]

ewert в сообщении #397509 писал(а):

Ales в сообщении #397505 писал(а):

Такие целочисленные матрицы (сумма строки = сумма столбца = одинаковое целое) образуют группу по сложению.

Допустим. И что?...

Целые неотрицательные образуют полугруппу.
Может быть, матрица с суммой 3 представима в виде суммы трех матриц с суммой 1, каждая.
Таких матриц (сумма по строке=1) всего $4!=4\cdot 3\cdot 2\cdot 1=24$.

-- Пн янв 10, 2011 12:08:29 --

Ответ: $\frac {24^3} {3!}=24 \cdot 96=2304$.

[ewert]

Ales в сообщении #397514 писал(а):

Ответ: $\frac {24^3} {3!}=24 \cdot 96=2304$.

Но ведь правильный-то ответ -- это всё-таки 2008.

[Bulinator]

15% точности. Нормально!

[Ales]

ewert в сообщении #397555 писал(а):

Ales в сообщении #397514 писал(а):

Ответ: $\frac {24^3} {3!}=24 \cdot 96=2304$.

Но ведь правильный-то ответ -- это всё-таки 2008.

Судя по обсуждению, 2008 - это только гипотеза.

Но чтобы мое решение было верным надо:
1. показать, что любая матрица с числом 3 раскладывается в сумму матриц с числом 1
2. показать, что такое разложение единственно с точностью до перестановки.

У нас есть линейное подпространство матриц, таких что (сумма строки = сумма столбца = одинаковое число).
Шесть уравнений на 16 неизвестных, размерность линейного подпространства 10.
В этом линейном подпространстве содержится решетка из целых матриц.
Кстати эти матрицы - коммутируют с матрицей состоящей из одних единиц. Обозначим такую матрицу, через $[1]$.
Тогда, если A - матрица из условия задачи, то $A\cdot [1]=[1]\cdot A =3[1]$.

-- Пн янв 10, 2011 14:33:37 --

Я когда пытался доказать теорему Ферма, на таких матрицах собаку съел.

[ewert]

Ales в сообщении #397578 писал(а):

Судя по обсуждению, 2008 - это только гипотеза.

Нет, это факт.

[Ales]

Замечу еще, что такие целочисленные матрицы образуют алгебру.