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

[ewert]

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

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

$\begin{pmatrix}2&1&0&0\\1&2&0&0\\0&0&2&1\\0&0&1&2\end{pmatrix}=$

$=\begin{pmatrix}0&1&0&0\\1&0&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}+\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}+\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}=$

$=\begin{pmatrix}0&1&0&0\\1&0&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}+\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}+\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}=$

$=\ \ldots$

Сколько вариантов набирается?...

[Ales]

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

Сколько вариантов набирается?...

Значит разложение не единственно.

[ewert]

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

Значит разложение не единственно.

Притом весьма нерегулярно неединственно. Увы.

[Ales]

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

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

Значит разложение не единственно.

Притом весьма нерегулярно неединственно. Увы.

Но мое решение, хоть и не верное, больше похоже на решение олимпиадной задачи.
Тот кто придумал задачу, знал что-то нам не известное. Решение задачи - простое следствие из этого.

-- Пн янв 10, 2011 15:44:48 --

Мне кажется, что ответ должен делиться на 24 - число перестановок строк. А 2008 не делится на 24.

-- Пн янв 10, 2011 16:06:05 --

А вот и не должен делиться на 24: если три строчки одинаковые, то всего 4 перестановки строк и 4 перестановки столбцов.
2008 - 16 = 1992 делится на 12. ОК.

[caxap]

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

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

Я тоже на компьютере перебрал все варианты квадратов. Подходят 2008 шт.

[Ales]

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

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

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

Я тоже на компьютере перебрал все варианты квадратов. Подходят 2008 шт.

Значит точно 2008. Но перебор - не лучший способ решения. Наверное, есть какой нибудь хитрый и быстрый способ.

-- Пн янв 10, 2011 16:54:26 --

Еще: все эти матрицы коммутируют с матрицей $S=[1]-E$.
Если у матрицы есть обратная, то она обладает тем же свойством (сумма по строке=сумма по столбцу=одинаковое число).
Сумма строки - норма для алгебры, отображает алгебру в кольцо целых чисел.

[ewert]

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

Я тоже на компьютере перебрал все варианты квадратов.

Я тоже сперва на компьютере тупым перебором, но потом пересчитал и вручную все 10-12 (или сколько их там) вариантов. Сошлось.

(Оффтоп)

На компьютере примерно так:

type  vector = array[1..4] of byte;

var  aa: array[1..256] of vector;
     num, all, i,k, i1,i2,i3,i4: integer;
     a1,a2,a3,a4: vector;

begin

  num:=0;
  for i1:=0 to 3 do
    for i2:=0 to 3 do
      for i3:=0 to 3 do
        for i4:=0 to 3 do
          if i1+i2+i3+i4=3 then begin
            inc(num);
            aa[num][1]:=i1;   aa[num][2]:=i2;
            aa[num][3]:=i3;   aa[num][4]:=i4;
            writeln(num:3, '  ', aa[num][1]:2, aa[num][2]:2,
                    aa[num][3]:2, aa[num][4]:2);
            end;
  readln;

  all:=0;
  for i1:=1 to num do
    for i2:=1 to num do
      for i3:=1 to num do
        for i4:=1 to num do begin
          a1:=aa[i1];    a2:=aa[i2];    a3:=aa[i3];    a4:=aa[i4];
          if a1[1]+a2[1]+a3[1]+a4[1]<>3 then continue;
          if a1[2]+a2[2]+a3[2]+a4[2]<>3 then continue;
          if a1[3]+a2[3]+a3[3]+a4[3]<>3 then continue;
          if a1[4]+a2[4]+a3[4]+a4[4]<>3 then continue;
(*
          k:=0;
          for i:=1 to 4 do   if a1[i]=2 then inc(k);
          for i:=1 to 4 do   if a2[i]=2 then inc(k);
          for i:=1 to 4 do   if a3[i]=2 then inc(k);
          for i:=1 to 4 do   if a4[i]=2 then inc(k);
          if k<>4 then continue;
(**)
          inc(all);
          writeln;
          writeln(all:5, '  ', a1[1]:2, a1[2]:2, a1[3]:2, a1[4]:2);
          writeln('':5,  '  ', a2[1]:2, a2[2]:2, a2[3]:2, a2[4]:2);
          writeln('':5,  '  ', a3[1]:2, a3[2]:2, a3[3]:2, a3[4]:2);
          writeln('':5,  '  ', a4[1]:2, a4[2]:2, a4[3]:2, a4[4]:2);
          end;
  readln;

  end.

(глючит паскалевский парсер)

[Simba]

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

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

С матрицами я работать не умею, остановимся на камушках Будем действовать так: сначала выбирем куда класть камни, а затем (если камни различные (мало ли?)) расположим камни. В кажом ряду и каждой строке должно быть по 3 камня, т.е. должна быть 1 пустая клетка в кажом ряду или столбце, т.е. нельзя чтобы в каком-то ряду или строке имелись 2 пустые клетки. Тогда кол-во способов выбрать эти позиции равно $4!$. Ну а кол-во способов расставить эти камушки, если они различны, равно $12!$. В итоге $N=4! \cdot 12!$
Только мне кажется это совсем не эквивалентные задачи...

[ewert]

Simba в сообщении #399483 писал(а):

Только мне кажется это совсем не эквивалентные задачи...

Совсем разные. Во всяком случае, в лично Вашей интерпретации -- у вас каждый элемент матрицы должен быть равен нулю или единичке, и потом зачем-то все единички ещё и считаются разными. Последнее странно: тогда, по логике вещей, и нули тоже следовало бы различать.

[Simba]

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

Совсем разные. Во всяком случае, в лично Вашей интерпретации -- у вас каждый элемент матрицы должен быть равен нулю или единичке, и потом зачем-то все единички ещё и считаются разными. Последнее странно: тогда, по логике вещей, и нули тоже следовало бы различать.

Ну, интерпретация это не моя. А в данном случае - про камушки: нули - это пустые места, их не отличить друг от друга, а камни - еденицы, но иногда и камни разные бывают, я и для того написал "если они(камни) различны ...".