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

[Гость]

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

[VAL]

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

160000. A в чем проблема?

[glorius_May]

Source of the post

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

160000. A в чем проблема?

B каждой строке И в каждом столбце, a не ИЛИ.

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

[VAL]

Source of the post

Source of the post

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

160000. A в чем проблема?

B каждой строке И в каждом столбце, a не ИЛИ.

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

Я, как водится, невнимательно прочел условие
Столбцы вообще не заметил

[VAL]

Наверное, можно и общую формулу вывести (через принцип включений-исключений), но для данного частного случая можно и разумным перебором:
1) 4 тройки - 24 способа;
2) 2 тройки, 2 двойки, 2 единицы - 144 способа;
3) 1 тройка, 3 двойки, 3 единицы - 192 способа;
4) 1 тройка, 2 двойки, 5 единиц - 288 способов;
5) 1 тройка, 9 единиц - 16 способов;
6) 4 двойки, 4 единицы - 144 способа;
7) 3 двойки, 6 единиц - 672 способа;
2 двойки, 8 единиц - 288 способов;
9) 1 двойка, 10 единиц - 144 способа;
10) 12 единиц - 24 способа.

Итого 1936 способов, если ничего не напутал. (Ho это вряд ли )

[glorius_May]

Source of the post
Наверное, можно и общую формулу вывести (через принцип включений-исключений), но для данного частного случая можно и разумным перебором:
1) 4 тройки - 24 способа;
2) 2 тройки, 2 двойки, 2 единицы - 144 способа;
3) 1 тройка, 3 двойки, 3 единицы - 192 способа;
4) 1 тройка, 2 двойки, 5 единиц - 288 способов;
5) 1 тройка, 9 единиц - 16 способов;
6) 4 двойки, 4 единицы - 144 способа;
7) 3 двойки, 6 единиц - 672 способа;
2 двойки, 8 единиц - 288 способов;
9) 1 двойка, 10 единиц - 144 способа;
10) 12 единиц - 24 способа.

Итого 1936 способов, если ничего не напутал. (Ho это вряд ли )

B книжке ответ 2008
a почему не знаю

[VAL]

Пересчитал. Нашел ошибки (кто б сомневался!? )
Легче не стало

Source of the post
Наверное, можно и общую формулу вывести (через принцип включений-исключений), но для данного частного случая можно и разумным перебором:
1) 4 тройки - 24 способа;
2) 2 тройки, 2 двойки, 2 единицы - 144 способа;
3) 1 тройка, 3 двойки, 3 единицы - 192 способа;
4) 1 тройка, 2 двойки, 5 единиц - 288 способов 192 способа;
5) 1 тройка, 9 единиц - 16 способов;
6) 4 двойки, 4 единицы - 144 способа 216 способов;
7) 3 двойки, 6 единиц - 672 способа;
2 двойки, 8 единиц - 288 способов;
9) 1 двойка, 10 единиц - 144 способа;
10) 12 единиц - 24 способа.

Итого 1936 1912 способов, если ничего не напутал. (Ho это вряд ли )

B книжке ответ 2008
a почему не знаю

Наверное, эта задачка на олимпиаде в 2008-м году предлагалась

PS: Кстати, если в 4-й строке оставить вариант до исправлений, получится, как раз, 2008. Сейчас еще раз проверю.

[СергейП]

Source of the post Пересчитал. Нашел ошибки (кто б сомневался!? )
Легче не стало

Source of the post Наверное, можно и общую формулу вывести (через принцип включений-исключений), но для данного частного случая можно и разумным перебором:
1) 4 тройки - 24 способа;
2) 2 тройки, 2 двойки, 2 единицы - 144 способа;
3) 1 тройка, 3 двойки, 3 единицы - 192 способа;
4) 1 тройка, 2 двойки, 5 единиц - 288 способов 192 способа;
5) 1 тройка, 9 единиц - 16 способов;
6) 4 двойки, 4 единицы - 144 способа 216 способов;
7) 3 двойки, 6 единиц - 672 способа;
2 двойки, 8 единиц - 288 способов;
9) 1 двойка, 10 единиц - 144 способа;
10) 12 единиц - 24 способа.

Итого 1936 1912 способов, если ничего не напутал. (Ho это вряд ли )

B книжке ответ 2008
a почему не знаю

Наверное, эта задачка на олимпиаде в 2008-м году предлагалась

PS: Кстати, если в 4-й строке оставить вариант до исправлений, получится, как раз, 2008. Сейчас еще раз проверю.

Если не напутал, то в 4-ой строке все-же 288:
- место для 3 - 16 способов
- в матрице 3Х3 есть строка и столбик из 1-ек, строку выбираем 3-мя способами, столькими же столбик, всего 3*3
- в оставшейся матрице 2Х2 две 2-ки можно разместить 2-мя способами.
Всего

[VAL]

Source of the post
Если не напутал, то в 4-ой строке все-же 288:
- место для 3 - 16 способов
- в матрице 3Х3 есть строка и столбик из 1-ек, строку выбираем 3-мя способами, столькими же столбик, всего 3*3
- в оставшейся матрице 2Х2 две 2-ки можно разместить 2-мя способами.
Всего

Считал абсолютно так же. Оба раза. Как я при этом смог при перемножении указанных чисел (во второй раз) получить 192, Бог весть! :blink: