和與積的問題

和與積的問題（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