Сколькими способами можно заполнить цифрами 0, 1, . . . , 9 (можно с повторениями) таблицу 3 × 3 так, чтобы сумма цифр в каждой строке и каждом столбце равнялась 4?

задан 2 Ноя 13:43

у меня получилось 33...

(2 Ноя 14:01) all_exist

в ответе, вроде, должно быть 120, но вот как его получить не очень понятно. по идее по формуле, наверно, но вот как учесть что расстановка должна отвечать и по столбикам и по строчкам??

(2 Ноя 14:04) fedro

Условие странное - если сумма цифр = 4 ,то цифры 5,6,7,8,9 использовать нельзя

(2 Ноя 14:24) potter

Возможно, это связано с тем, что задача взята из ряда однотипных, отличающихся только суммой цифр в строчке. Задача из "Высшей пробы". Решения прошлых туров они, к сожалению, не публикуют(

(2 Ноя 18:39) fedro

в ответе, вроде, должно быть 120 - странный ответ...

(2 Ноя 21:21) all_exist

в смысле на сайте олимпиады указан ответ 120

(2 Ноя 21:29) fedro

я понимаю... но это не делает его менее странным... )))

(2 Ноя 21:35) all_exist

расписал решение подстановкой всех вариантов угловых клеточек, как однозначно определяющих всю таблицу на два а4, получил 157. и потом понял что перевороты не учтены. и такой зачем писал...

(2 Ноя 22:26) fedro

@all_exist: там действительно 120. Решение я знаю только переборное. Но вручную оно делается.

(2 Ноя 22:35) falcao

@falcao, значит я просто не вижу потерянных вариантов в своём переборе...(((

(2 Ноя 22:46) all_exist

а, нет... понял, что потерял...

(2 Ноя 23:24) all_exist

В общем виде там довольно сложная техника подсчёта. Вот на всякий случай ссылка.

(2 Ноя 23:51) falcao

Есть подозрение, что решить можно, учитывая факт, что 4 угловые клетки полностью определяют расстановку цифр таблицы. Соответственно можно отталкиваться от количества расстановок цифр в угловые клетки по аналогии с math.hashcode.ru/questions/80834/ но надо как-то отбросить варианты с неподходящими сочетаниями соседних цифр (суммасоседних>4)

(3 Ноя 19:51) fedro

@fedro: я брал 4 клетки в угловом квадрате, но это то же самое. Там получалась система неравенств. Она упрощается, но потом нужен кое-какой перебор. Если интересно, могу изложить более детально.

(3 Ноя 21:10) falcao

если можно, то да, было бы круто

(3 Ноя 21:53) fedro
показано 5 из 15 показать еще 10
10|600 символов нужно символов осталось
2

Я эту задачу решал перебором, не зная о том, что здесь есть общая формула. Когда получил значения для небольших $%n$%, у меня получились числа 1, 6, 21, 55, 120, посмотрел на oeis, и нашёл там эту последовательность. Выяснилось, что для этой задачи есть общая формула $%f(n)=\frac{(n+1)(n+2)(n^2+3n+4)}8=\frac{(n^2+3n+3)^2-1}8$%. Это породило мысль, что можно всё сделать в общем виде, избегая перебора. Сейчас у меня это получилось, и я изложу решение.

Общая задача такова: заполняем клетки таблицы $%3\times3$% целыми числами, которые принимают значения от $%0$% до $%n$%. Требуется найти число $%f(n)$% "магических квадратов", где суммы чисел в строках и столбцах равны $%n$%. Для частного случая имеем $%f(4)=\frac{31^2-1}8=120$%.

Формулу будем доказывать по индукции. Для "малых" значений типа $%f(0)=1$% и $%f(1)=6$% справедливость формулы очевидна. Пусть $%n\ge2$%.

Рассмотрим два вида таблиц. В первом случае на главной диагонали имеются нули. Рассмотрим случай, когда 0 находится в правой нижней клетке. Пусть на пересечении первых двух строк и столбцов получается таблица с числами $%a$%, $%b$%, $%c$%, $%d$%. Заполняя однозначно остальное, видим, что $%a+b+c+d=n$%, и это условие необходимо и достаточно. Число решений этого уравнения даётся готовой формулой для числа сочетаний с повторениями из $%4$% по $%n$%, что равно $%C_{n+3}^3$%.

Пусть теперь нули находятся на второй и третьей клетке главной диагонали. Это даёт $%d=0$%, и уравнение принимает вид $%a+b+c=n$%. Из тех же соображений, число решений равно $%C_{n+2}^2$%. Наконец, для случая $%a=d=0$% (три нуля на главной диагонали) получается $%C_{n+1}^1=n+1$%.

Применяя формулу включений и исключений, имеем $%3C_{n+3}^3-3C_{n+2}^2+(n+1)=\frac{(n+1)(n^2+2n+2)}2$%. Это число таблиц с наличием нулей на главной диагонали.

Второй случай: на главной диагонали нулей нет. Тогда вне главной диагонали не встречается число $%n$%. Вычтем по единице из чисел главной диагонали. Таблица окажется заполнена числами от $%0$% до $%n-1$%. Таких таблиц $%f(n-1)$% по предположению индукции. Имея такую таблицу, можем применить обратную операцию, прибавляя по главной диагонали единицы. Это говорит о том, что соответствие является взаимно однозначным.

Остаётся арифметика: мы доказали, что $%f(n)=f(n-1)+\frac{(n+1)(n^2+2n+2)}2$%. По предположению, $%f(n-1)=\frac{(n^2+n+1)^2-1}8$%, и далее имеем $$\frac{(n^2+3n+3)^2-1}8-\frac{(n^2+n+1)^2-1}8=\frac{(2n^2+4n+4)(2n+2)}8=\frac{(n+1)(n^2+2n+2)}2,$$ что и требовалось проверить.

ссылка

отвечен 4 Ноя 0:26

пока что не всё понял но это круто, спасибо)

(6 Ноя 22:47) fedro
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,159

задан
2 Ноя 13:43

показан
110 раз

обновлен
6 Ноя 22:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru