\begingroup

使用数字 2、3、4、… 19,每个数字恰好一次,用数字填充网格中的某些空白格,使得每行数字的乘积如图所示,每列数字的总和也是如此。

同样,从编号为 1 的方格开始的必须能够做出有效移动并落在编号为 2 的方格上,然后从那里它必须能够做出有效移动并落在编号为 3 的方格上,然后跳到 4,再跳到 5…… 最后落在编号为 20 的方格上。


归因:2024 年 6 月 MathsJam Shout 期刊。(保罗·泰勒 (Paul Taylor) 的谜题)

\endgroup


最佳答案
2

\begingroup

首先找到 19 的位置:

19 是 1710 的因数 = 19 x 90,因此 19 位于第 3 行。它必须是从 20 开始的骑士移动,位于第 2 列。数字 19 位于第 3 行第 2 列。

然后对于 17:

17 是 4896 = 17 x 288 的因数,因此 17 位于第 2 行。它不能位于第 1 列,因为这会超过给定的总和。第 3 列是第 2 行中唯一可用的奇数单元格。数字 17 位于第 2 行第 3 列。

然后对于 18:

18 必须是从 17 和 19 开始的骑士移动。数字 18 放置在第 4 行、第 4 列。

对于 11、12、13:

11 和 13 是 92664 = 11 x 13 x 648 的因数。它们都在第 4 行。它们都不能在第 1 列,因此它们必须在第 3 列和第 5 列。数字 12 必须是从每个数字移动一个骑士:数字 12 放在第 2 行,第 4 列。

对于 14、15、16:

如果 13 位于第 4 行,则 14 必须位于第 5 行第 3 列或第 5 列。从这两个单元格中,数字 15 应位于第 3 行第 4 列。如果 15 和 17 都位于原位,则 16 必须是两者的骑士移动。第 2 列中的列总和将被超过,因此数字 16 应位于第 1 行第 5 列。

继续:

第 2 行包含 17、12 和 1。此行中其余数字的乘积为 24。这需要两个数字,其中一个必须是奇数。这只能是 3 x 8。

数字 3 放在第 2 行第 1 列。


数字 8 放在第 2 行第 2 列。数字 7 放在第 1 行第 4 列。

第 3 行包含 19 和 15。此行剩余数字的乘积为 6。数字 3 已放置在第 2 行,因此第 3 行中唯一的其他数字是 6。

数字 2 放置在第 1 行第 3 列。(骑士从 3 和 1 移动)


数字 4 放置在第 4 行第 2 列。


数字 5 放置在第 5 行第 4 列。

数字 9 放在第 4 行第 1 列。

数字 10 放在第 5 行第 3 列。


数字 11 放在第 4 行第 5 列。


数字 13 放在第 4 行第 3 列。


数字 14 放在第 5 行第 5 列。


数字 6 放在第 3 行第 5 列。

完成的网格:

20..2 7 16 
  3 8 17 12 1..19..15 
 6 
  9 4 13 18 11 
 ...10 5 14
 

\endgroup

\begingroup

您可以通过整数线性规划按如下方式解决问题。对于i , j∈ { 1 , , 5 }{15}i,j\in\{1,\dots,5\}k∈ { 1 , , 20 }{120}k\in\{1,\dots,20\},让二元决策变量XXx_{ijk}指示单元格(i,j)接受价值观k。 让CCc_j为列的所需和j, 然后让rrr_i是行的所需乘积i. 对于素数p { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 }{235711十三1719}p\in\{2,3,5,7,11,13,17,19\}, 让ν名词νn\nu_p(n)成为p进位估价nnn,即p在质因数分解中nnn。 让= { () : | i | | j| =2}={||||=2}N_{ij}=\{(i’,j’):|i-i’| \cdot |j-j’|=2\}是单元格的骑士移动邻居的集合(i,j). 约束条件为

X1 1 20X2 5 1XXXνXX= 1= 11= 1=C=νr) X, k + 1对于所有 i , j对于所有 k对于所有 j对于所有的 i , p对于所有 i j 和 k < 20(1)(2)(3)(4)(5)(6)(7)(1)X1120=1(2)X251=1(3)X1对全部 (4)X=1对全部 (5)X=C对全部 (6)νX=νr对全部 (7)XX+1对全部  和 <20

\begin{align}
x_{1,1,20} &= 1 \tag1\label1 \\
x_{2,5,1} &= 1 \tag2\label2 \\
\sum_k x_{ijk} &\le 1 && \text{for all $i,j$} \tag3\label3 \\
\sum_i \sum_j x_{ijk} &= 1 && \text{for all $k$} \tag4\label4 \\
\sum_i \sum_k k x_{ijk} &= c_j && \text{for all $j$} \tag5\label5 \\
\sum_j \sum_k \nu_p(k) x_{ijk} &= \nu_p(r_i) && \text{for all $i, p$} \tag6\label6 \\
x_{ijk} &\le \sum_{(i’,j’) \in N_{ij}} x_{i’,j’,k+1} && \text{for all $i,j$ and $k < 20$} \tag7\label7
\end{align}
约束
(1)\eqref{1}(2)\eqref{2}执行给定位置202020111. 约束(3)\eqref{3}为每个单元格最多分配一个值。约束(4)\eqref{4}将每个值分配给一个单元格。约束(5)\eqref{5}强制执行列总和。约束(6)\eqref{6}强制执行行积。约束(7)\eqref{7}强制执行骑士的移动限制。

唯一的解决方案是

20398194217十三10712151851616111420271638171211915694十三181110514

\begin{matrix} 20 &. &2 &7 &16 \\3 &8 &17 &12 &1\\. &19 &. &15 &6\\9 &4 &13 &18 &11\\. &. &10 &5 &14\end{matrix}

\endgroup