2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Числа в клетках и делимость на 10
Сообщение22.02.2014, 02:19 
Аватара пользователя
Расставьте числа от 1 до 9 в клетках таблицы $3\times 3$ так, чтобы сумма чисел в любом квадрате $2\times 2$ делилась на 10.

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

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

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

 
 
 
 Re: Числа в клетках и делимость на 10
Сообщение22.02.2014, 20:04 
Обозначим число в центре квадрата $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} $$

 
 
 
 Re: Числа в клетках и делимость на 10
Сообщение22.02.2014, 20:20 
Ktina в сообщении #829346 писал(а):
Существует ли алгоритм, позволяющий додуматься до решения без "тыка"?

А чем "тык" не алгоритм?
$$\begin{bmatrix}
1 & 4 & 9 \\
3 & 2 & 5 \\
8 & 7 & 6 \\
\end{bmatrix}$$

 
 
 
 Re: Числа в клетках и делимость на 10
Сообщение22.02.2014, 23:45 
Аватара пользователя
mihiv
Спасибо!

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

 
 
 
 Re: Числа в клетках и делимость на 10
Сообщение23.02.2014, 00:16 
Ktina в сообщении #829647 писал(а):
Алгоритм подразумевает строго определённый порядок действий, разве нет?
Что не мешает существовать алгоритмам прямого перебора. :wink:

 
 
 
 Re: Числа в клетках и делимость на 10
Сообщение23.02.2014, 15:29 
Аватара пользователя
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-ку (и это вполне понятно).

 
 
 
 Re: Числа в клетках и делимость на 10
Сообщение23.02.2014, 17:08 
Аватара пользователя
B@R5uk
Спасибо! Выражаю восхищение могуществом современной техники.

 
 
 
 Re: Числа в клетках и делимость на 10
Сообщение23.02.2014, 17:37 
Аватара пользователя
Ещё интересно, что если потребовать делимость не на десять а на целое число $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$ с последующим ростом -- это загадка.

 
 
 
 Re: Числа в клетках и делимость на 10
Сообщение24.02.2014, 09:31 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: Числа в клетках и делимость на 10
Сообщение24.02.2014, 12:45 
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$.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group