Question

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

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

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

Answer 1

首先找到 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

Answer 2

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

X 1 ， 1 ， 20 X 2 ， 5 ， 1 \sum 钾 X 額 ​ ​ \sum 我 \sum 杰 X 額 ​ ​ \sum 我 \sum 钾 钾 X 額 ​ ​ \sum 杰 \sum 钾 ν 页 （ 千 ） X 額 ​ ​ X 額 ​ ​ = 1 = 1 \leq 1 = 1 = C 杰 = ν 页 （ r 我 ） \leq \sum （ 我' ， 杰') \in 否 伊 ​ X 我' ， 杰', k + 1 对于所有 i, j 对于所有 k 对于所有 j 对于所有的 i, p 对于所有 i 、 j 和 k < 20 （1） （2） （3） （4） （5） （6） （7）

\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}执行给定位置 $20$ 20和 $1$ 1. 约束 $(3)$ \eqref{3}为每个单元格最多分配一个值。约束 $(4)$ \eqref{4}将每个值分配给一个单元格。约束 $(5)$ \eqref{5}强制执行列总和。约束 $(6)$ \eqref{6}强制执行行积。约束 $(7)$ \eqref{7}强制执行骑士的移动限制。

唯一的解决方案是

$203 。 9 。。 8194 。 217 。十三 10 7121518516161114$
\begin{matrix} 20 &. &2 &7 &16 \\3 &8 &17 &12 &1\\. &19 &. &15 &6\\9 &4 &13 &18 &11\\. &. &10 &5 &14\end{matrix}

数学 – 根据乘积，总和以及骑士移动约束填充网格 – 谜题交换

最佳答案
2

数学 – 根据乘积，总和以及骑士移动约束填充网格 – 谜题交换

最佳答案 2

最佳答案
2