使用数字 2、3、4、… 19,每个数字恰好一次,用数字填充网格中的某些空白格,使得每行数字的乘积如图所示,每列数字的总和也是如此。
同样,从编号为 1 的方格开始的必须能够做出有效移动并落在编号为 2 的方格上,然后从那里它必须能够做出有效移动并落在编号为 3 的方格上,然后跳到 4,再跳到 5…… 最后落在编号为 20 的方格上。
归因:2024 年 6 月 MathsJam Shout 期刊。(保罗·泰勒 (Paul Taylor) 的谜题)
\endgroup
最佳答案
2
首先找到 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
|
您可以通过整数线性规划按如下方式解决问题。对于i , j∈ { 1 , … , 5 }我,杰∈{1,…,5}i,j\in\{1,\dots,5\}和k∈ { 1 , … , 20 }钾∈{1,…,20}k\in\{1,\dots,20\},让二元决策变量X額X我杰钾x_{ijk}指示单元格(一,一)(我,杰)(i,j)接受价值观钾钾k。 让C杰C杰c_j为列的所需和杰杰j, 然后让r我r我r_i是行的所需乘积我我i. 对于素数p ∈ { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 }页∈{2,3,5,7,11,十三,17,19}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). 约束条件为
\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}执行给定位置202020和111. 约束(3)\eqref{3}为每个单元格最多分配一个值。约束(4)\eqref{4}将每个值分配给一个单元格。约束(5)\eqref{5}强制执行列总和。约束(6)\eqref{6}强制执行行积。约束(7)\eqref{7}强制执行骑士的移动限制。
唯一的解决方案是
203。9。。8194。217。十三10712151851616111420。27163817121。19。15694十三1811。。10514\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
|
|