和与积的问题

和与积的问题（Sum and Product Puzzle）是一道逻辑谜题，又因为其题面上似乎缺乏足够的解题信息而得名不可能的谜题（The Impossible Puzzle）。该谜题由汉斯·弗赖登塔尔得于1969年首次发表，而别名“不可能的谜题”则由马丁·加德纳所提出。尽管略显困难，此谜题仍然是可解的，并有很多与之类似的谜题。

## 简介

### 谜题

此谜题有许多版本，以下为最原始的版本：

已知$x$和$y$是两个大于1的整数，满足$x$小于$y$，而两数之和不大于100（即$x, y \in \mathbb{Z}$，$1 < x < y$，$x + y \le 100$）。

S和P则是两位逻辑非常好的数学家。另外，S知道两数之和$x + y$，P则知道两数之积$xy$。两人都知道上述资讯后，对话如下：

- S先说：“P不知道$x$和$y$的值。”
- P回复：“现在我知道$x$和$y$的值了。”
- S再说：“现在我也知道$x$和$y$的值了。”

请问$x$和$y$两数分别为多少？

### 谜底

P知道的乘积为52，S知道的和为17，换句话说，$(x, y) = (4, 13)$。

## 解析

### 数学家视角

以下将按对话顺序分析数学家P和S的想法：

#### 获取资讯后

P：已知积 $p = 52$，$(x, y)$可能为$(2, 26)$或$(4, 13)$，因此不知两数具体为何。

S：已知和 $s = 17$，$(x, y)$可能的情况如下：

可能的 $(x, y)$ 组合｜乘积 $p$｜只考虑乘积时可能的解 $(x, y)$

$(2, 15)$｜$30$｜$(2, 15)$、$(3, 10)$、$(5, 6)$

$(3, 14)$｜$42$｜$(2, 21)$、$(3, 14)$、$(6, 7)$

$(4, 13)$｜$52$｜$(2, 26)$、$(4, 13)$

$(5, 12)$｜$60$｜$(2, 30)$、$(3, 20)$、$(4, 15)$、$(5, 12)$、$(6, 10)$

$(6, 11)$｜$66$｜$(2, 33)$、$(3, 22)$、$(6, 11)$

$(7, 10)$｜$70$｜$(2, 35)$、$(5, 14)$、$(7, 10)$

$(8, 9)$｜$72$｜$(2, 36)$、$(3, 24)$、$(4, 18)$、$(6, 12)$、$(8, 9)$

由上表可知，在所有S认为可能的乘积$p$下，P皆不能确定两数具体为何，因而说出：“P不知道$x$和$y$的值”。

#### S第一句话后

P：若S能断言自己（P）不知道两数，则S手中的$s$对应的所有可能乘积，均可引出超过一组可能的解。

因此，P分别针对$s = 17$和$s = 28$的可能情况：

- $s = 28$时，$(x, y) = (5, 23)$而$p = 115$，和$(x, y) = (11, 17)$而$p = 187$，两个可能乘积都只能引出一种可能解，使得S无法断言P不知道两数。
- $s = 17$时，经验证后其满足条件。

此时P确定$s = 17$，$(x, y) = (4, 13)$，因而说出：“现在我（P）知道$x$和$y$的值了”。

#### P回应后

S：若P能宣告他知道$x$和$y$的值，则P手中的$p$对应的可能组合中，“恰好只有一组”的和$s$能满足“所有对应的可能乘积，均可引出超过一组可能解。”的筛选条件。

因此，S分别针对自己手中的7种可能乘积进行模拟与排除：

可能乘积 $p$｜P考虑的可能组合与对应的和 $s$｜P核验 $s$ 是否满足条件｜结果

$30$｜$$\begin{aligned} (2, 15) &\to s = 17 \\ (3, 10) &\to s = 13 \\ (5, 6) &\to s = 11 \end{aligned}$$｜$s = 17$与$s = 11$皆满足｜P无法确定

$42$｜$$\begin{aligned} (2, 21) &\to s = 23 \\ (3, 14) &\to s = 17 \\ (6, 7) &\to s = 13 \end{aligned}$$｜$s = 23$与$s = 17$皆满足｜P无法确定

$52$｜$$\begin{aligned} (2, 26) &\to s = 28 \\ (4, 13) &\to s = 17 \end{aligned}$$｜$s = 28$可拆为质数和$5 + 23$（不满足）；仅剩$s = 17$满足｜P可确定答案（唯一解）

$60$｜$$\begin{aligned} (2, 30) &\to s = 32 \\ (3, 20) &\to s = 23 \\ (4, 15) &\to s = 19 \\ (5, 12) &\to s = 17 \\ (6, 10) &\to s = 16 \end{aligned}$$｜$s = 23$与$s = 17$皆满足｜P无法确定

$66$｜$$\begin{aligned} (2, 33) &\to s = 35 \\ (3, 22) &\to s = 25 \\ (6, 11) &\to s = 17 \end{aligned}$$｜$s = 35$与$s = 17$皆满足｜P无法确定

$70$｜$$\begin{aligned} (2, 35) &\to s = 37 \\ (5, 14) &\to s = 19 \\ (7, 10) &\to s = 17 \end{aligned}$$｜$s = 37$与$s = 17$皆满足｜P无法确定

$72$｜$$\begin{aligned} (2, 36) &\to s = 38 \\ (3, 24) &\to s = 27 \\ (4, 18) &\to s = 22 \\ (6, 12) &\to s = 18 \\ (8, 9) &\to s = 17 \end{aligned}$$｜$s = 27$与$s = 17$皆满足｜P无法确定

由上表可知，唯有$p = 52$时P可以排除其他干扰项并得出唯一解。

此时S确定$p = 52$，$(x, y) = (4, 13)$，因而说出：“现在我（S）也知道$x$和$y$的值了”。

### 读者视角

谜题给出的基本条件称为条件A：$x, y \in \mathbb{Z}$，$1 < x < y$，$x + y \le 100$。

令两数之和为$s$，两数之积为$p = xy$，以下所有数对$(x, y)$皆预设符合条件A。

从S的第一句话可知，$s$所拆分出的每一组$(x, y)$，其乘积$p$皆可拆分成多于一组符合条件A的数对。因此，S在只知道$s$的情况下，便能肯定P无法单凭$p$确定$x$和$y$的值。（条件B）

从P的第一句话可知，P在知道$p$并得知$s$符合条件B后，检视了$p$的所有可能分解$(x, y)$，发现其中“恰好只有一组”对应的和$s = x + y$符合条件B，故P得以确定$x$和$y$的值。（条件C）

从S的第二句话可知，S在得知P已确定答案后，检视了$s$的所有可能拆分$(x, y)$，发现其中“恰好只有一组”对应的积$p = xy$符合条件C，故S亦得以确定$x$和$y$的值。（条件D）

依据条件A，$s$的最小值为$2 + 3 = 5$，最大值为$100$。以下筛选出所有符合条件B的$s$可能值：

- 若$x, y$皆为质数，则$p = xy$只有唯一分解，故$s$不可能拆分为两个质数之和。由此可排除所有不小于$8$的偶数（根据哥德巴赫猜想，大于$2$的偶数皆可表示为两个质数之和，且在$100$以内皆成立；注意到$6 = 3 + 3$不满足$x < y$），以及“$2 + \,$奇质数”的形式。
- 若$p = q^3$（$q$为质数），则$p$仅有唯一分解$(q, q^2)$，故$s$不可能拆分为$(q, q^2)$，由此排除$6 = 2 + 2^2$。
- 若$p$含有大于$50$的质因数$q$，由于$y < 100$，必定有$y = q$，故$p$仅有唯一分解$(x, q)$，由此排除所有不大于$100$且可拆为$(x, 53)$及以上质数的$s$，即排除不小于$53 + 2 = 55$的整数。
- 若$p = 2q^2$（$q > 10$为质数），由于$y < 100$，$y$不可能为$q^2$，故$p$仅有唯一分解$(q, 2q)$，即$s$不可能为$3q$。由此排除$51 = 3 \times 17$。

$s$剩余的可能值为：

$11, 17, 23, 27, 35, 37, 41, 47, 53$（记为集合$*$）

上述可能值皆符合条件B。因为$s$为奇数，任何拆分出的$(x, y)$必为一奇数$a$与一偶数$2b$：

- 当$b = 1$时，$a$必为合数（否则即为“$2 + \,$奇质数”，已被排除）。由于$a \le 53 - 2 = 51$，故$a$必有小于等于$7$的质因数$q$。乘积$p = 2a$可另拆为$a/q$与$2q$，易知其和不大于$100$，符合条件A。
- 若$a \neq b$，则乘积$p = 2ab$亦可拆为$2a$与$b$。由于$a \le 53 - 4 = 49$，其和$2a + b = (a + 2b) + (a - b) = s + (a - b) \le 53 + (49 - 2) = 100$，符合条件A。
- 若$a = b$，则$a$为合数（$a$不是质数，因其$3$倍不在集合$*$中）。此时$a = s/3 \le 53/3 < 18$，故$a$必有质因数$3$。乘积$p = 2a^2$可另拆为$2a/3$与$3a$，其和$2a/3 + 3a < 66 \le 100$，符合条件A。（亦可直接验证，集合$*$中仅有$27$为$3$的倍数。）

接下来检查集合$*$中的$s$可能值是否满足条件D：

注意到若$p = 2^k q$（其中$q$为奇质数），则$p$仅有一组和为奇数的可能拆分$(2^k, q)$。因此，若其和$2^k + q$符合条件B（即属于集合$*$），则$p$必然符合条件C。

- $11$可拆分为$(4, 7)$与$(8, 3)$，对应的乘积$28 = 2^2 \times 7$（和为$11$）与$24 = 2^3 \times 3$（和为$11$）皆符合条件C，故$11$不满足条件D。
- 同理，$23$可拆为$(4, 19)$与$(16, 7)$；$27$可拆为$(4, 23)$与$(8, 19)$；$35$可拆为$(4, 31)$与$(16, 19)$；$37$可拆为$(8, 29)$与$(5, 32)$；$47$可拆为$(4, 43)$与$(16, 31)$，故$23, 27, 35, 37, 47$皆不满足条件D。

剩余需要检查的$s$可能值为$17, 41, 53$：

- $41$拆分为$(4, 37)$的积符合条件C。另外拆分为$(2, 39)$时，积$78$可拆为$(6, 13)$（和为$19$）与$(3, 26)$（和为$29$），由于$19$与$29$皆不在集合$*$中（不符合条件B），故$(2, 39)$的积亦符合条件C，导致$41$不满足条件D。
- $53$拆分为$(16, 37)$的积符合条件C。另外拆分为$(5, 48)$时，积$240$可拆为$(15, 16)$（和为$31$）与$(3, 80)$（和为$83$），由于$31$与$83$皆不在集合$*$中，故$(5, 48)$的积亦符合条件C，导致$53$不满足条件D。

检查$17$的各拆分组合：

- $(2, 15)$的积可拆为$(5, 6)$，和为$11$（符合条件B），故$(2, 15)$的积不符合条件C。
- 同理，$(3, 14)$的积可拆为$(2, 21)$（和为$23$）；$(5, 12)$的积可拆为$(3, 20)$（和为$23$）；$(6, 11)$的积可拆为$(2, 33)$（和为$35$）；$(7, 10)$的积可拆为$(2, 35)$（和为$37$）；$(8, 9)$的积可拆为$(3, 24)$（和为$27$）。上述各拆分的积所对应的另一组拆分，其和皆属于集合$*$（符合条件B），故这些拆分的积皆不符合条件C。

因此，$17$的所有拆分中，唯有拆分为$(4, 13)$时其积才符合条件C，故$17$满足条件D。

由于$17$是集合$*$中唯一满足条件D的值，由此可得出$s = 17$，$x = 4$，$y = 13$。

## 外部链接

- Puzzles by John Burkardt
- The Impossible Problem by Torsten Sillke
- Two Mathematicians Problem on mathforum
- Model Checking Sum and Product
- Survey: The Freudenthal problem and its ramifications