Числа в клетках и делимость на 10

[Ktina]

Расставьте числа от 1 до 9 в клетках таблицы $3\times 3$ так, чтобы сумма чисел в любом квадрате $2\times 2$ делилась на 10.

Бестолковый перебор "тыком" позволил отыскать следующий вариант:

$$\begin{bmatrix} 9 & 1 & 6 \\ 2 & 8 & 5 \\ 7 & 3 & 4 \\ \end{bmatrix}$$

Существует ли алгоритм, позволяющий додуматься до решения без "тыка"?

[mihiv]

Обозначим число в центре квадрата $a_0$, числа по периметру квадрата, начиная с левого верхнего по часовой стрелке обозначим $a_1,\dots , a_8.$ Можно получить если и не алгоритм, то определенные соотношения для $a_i$, которые облегчают поиск. Например, сумма чисел в каждом квадрате $2\times 2$ равна 20, сумма чисел на концах каждой диагонали квадрата равна $5+a_0, a_0\ne 1,9, a_1+a_2=a_7+a_6$ и т.д.

$$\begin{bmatrix} \\1& 8 & 3\\9 & 2 & 7\\4 & 5 & 6\end {bmatrix} $$

[venco]

Ktina в сообщении #829346 писал(а):

Существует ли алгоритм, позволяющий додуматься до решения без "тыка"?

А чем "тык" не алгоритм?

$$\begin{bmatrix} 1 & 4 & 9 \\ 3 & 2 & 5 \\ 8 & 7 & 6 \\ \end{bmatrix}$$

[Ktina]

mihiv
Спасибо!

venco
Алгоритм подразумевает строго определённый порядок действий, разве нет?

[arseniiv]

Ktina в сообщении #829647 писал(а):

Алгоритм подразумевает строго определённый порядок действий, разве нет?

Что не мешает существовать алгоритмам прямого перебора.

[B@R5uk]

arseniiv в сообщении #829649 писал(а):

Что не мешает существовать алгоритмам прямого перебора.

Кстати, вполне себе разумный вариант. Всего-то $9! =362880$ вариантов. Для современной техники -- раз плюнуть. Вот я нашёл все 9 нетривиальных решений:

$\begin{bmatrix}9&7&2\\6&8&3\\1&5&4\end{bmatrix}$, $\begin{bmatrix}9&5&6\\4&2&7\\1&3&8\end{bmatrix}$, $\begin{bmatrix}9&4&3\\2&5&8\\7&6&1\end{bmatrix}$, $\begin{bmatrix}9&4&3\\1&6&7\\8&5&2\end{bmatrix}$, $\begin{bmatrix}9&2&7\\1&8&3\\6&5&4\end{bmatrix}$, $\begin{bmatrix}8&5&7\\1&6&2\\4&9&3\end{bmatrix}$, $\begin{bmatrix}8&5&2\\3&4&9\\7&6&1\end{bmatrix}$, $\begin{bmatrix}7&8&3\\1&4&5\\6&9&2\end{bmatrix}$, $\begin{bmatrix}6&7&3\\5&2&8\\4&9&1\end{bmatrix}$

Полный набор из 72-х решений можно получить 8-ю симметриями квадрата (включая тривиальную).

Интересно, что у первого набора сумма чисел в малых квадратах $\begin{bmatrix}30&20\\20&20\end{bmatrix}$, у второго -- $\begin{bmatrix}20&20\\10&20\end{bmatrix}$, а у остальных же 7-ми -- $\begin{bmatrix}20&20\\20&20\end{bmatrix}$. Так же интересный факт: в центре квадрата может быть только чётное число или 5, причём каждое чётное число встречается в решениях по 2 раза, а 5 -- 1 раз. Решение с 5-ой в центре имеет в качестве сумм одни лишь 20-ки. Решение с 10-кой в суммах имеет в центре 2-ку, а решение с 30-кой в суммах -- 9-ку (и это вполне понятно).

[Ktina]

B@R5uk
Спасибо! Выражаю восхищение могуществом современной техники.

[B@R5uk]

Ещё интересно, что если потребовать делимость не на десять а на целое число $N$, то число нетривиальных решений $M$ будет иметь такую от $N$ зависимость:

           1       45360
           2        3240
           3         864
           4         216
           5         112
           6          56
           7          40
           8          26
           9          21
          10           9
          11           6
          12           3
          13           1
          14           0
          15           0
          16           2
          17           5
          18           5
          19           8
          20           7
          21           8
          22           5
          23           5
          24           2

Для $N\ge25$ количество равно нулю. Для $N\ge31$ отсутствие решений понятно: сумма четырёх цифр не может быть больше $30$. А вот убывание при увеличении $N$ количества решений $M$ до нуля при $N=14$ и $N=15$ с последующим ростом -- это загадка.

[ИСН]

(Оффтоп)

Это же таблица Менделеева и "островки стабильности"!

[mihiv]

B@R5uk в сообщении #829869 писал(а):

А вот убывание при увеличении $N$ количества решений $M$ до нуля при $N=14$ и $N=15$ с последующим ростом -- это загадка.

Под это можно подвести "теоретическую базу".
Пусть, например, $N=15$. В этом случае может быть только один квадрат с суммой 30, т.к. ее можно получить лишь одним способом: 6+7+8+9. Суммы для остальных трех квадратов равны 15.
Пусть $s_1=a_1+a_2+a_0+a_8=30$ (число в центре квадрата $-a_0$, остальные нумеруются по часовой стрелке, начиная с левого верхнего угла), тогда $s_2=a_8+a_0+a_6+a_7=15$ и, следовательно,

$$a_1+a_2=a_6+a_7+15\qquad (1)$$

Правая часть равенства (1) $\geq 18$, но сумма двух различных слагаемых, каждое из которых <10, меньше 18. Противоречие.
Если же все четыре суммы равны 15, то справедливо равенство: $4\cdot 15-3a_0-a_2-a_4-a_6-a_8=45$(т.к. сумма чисел в квадрате $3\times 3$ равна 45). Отсюда

$$15-2a_0=a_0+a_2+a_4+a_6+a_8\qquad (2)$$

Но левая часть равенства (2) меньше 14, а правая - больше 14.
Аналогично рассматривается случай $N=14$.