有趣的数学 Puzzle - Sum and Product
前些天在老码农群里看到一个数学 Puzzle，让我联想到另一个红眼睛蓝眼睛的问题，感觉都涉及到一点递归和博弈的意思，仔细思考一下有些趣味，分享给大家。
随机选择两个数字，都是小于 100 的正整数。Sandy 被告知数字的总和，而 Peter 被告知数字的乘积，假设两个人都是足够理智的情况下，Sandy 和 Peter 之间发生了这个对话：
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I don't know the numbers.
Sandy: I don't know the numbers.
Peter: I do know the numbers.
那么这两个数字是多少？
先自己别看屏幕想个几分钟😏
注意前提是两个人都聪明和理智，知道如何通过目前的情况去推算。
从 1 到 100 两两组合一共有 4590 对数字。Sandy 说我不知道，其实里面隐含着一些信息，因为他知道两个数字之和，所以他说我不知道意味着肯定不是 1 + 1, 1 + 2 … 这种组合，因为这些组合的和在这 4590 对数字中是唯一的。因此 Peter 可以根据 Sandy 的信息排除掉这些组合。
类似的 Peter 每次说我不知道的情况下也可以排除一些组合，依次类推如果经过七轮之后，Peter 说我知道了那个组合，也就有了答案。
通过下面这个 Python 程序更容易理解，源处 Peter And Sandy ：
from collections import defaultdict
# build pairs
pairs = []
for i in range(1, 100):
for j in range(i, 100):
pairs.append((i, j))
def singles_operation(f):
results = defaultdict(list)
for a, b in pairs:
results[f(a, b)].append((a, b))
singles = []
for (k, value) in results.items():
# We want to return only the product/sum with one result because if
# peter/sandy have this product/sum, then they'll know the two numbers
if len(value) == 1:
singles.extend(value)
# Sorted for readability
return sorted(singles, key=lambda x: x[0])
def remove_products():
singles = singles_operation(lambda x, y: x * y)
print('peter removed', singles)
for s in singles:
pairs.remove(s)
def remove_sums():
singles = singles_operation(lambda x, y: x + y)
print('sandy removed', singles)
for s in singles:
pairs.remove(s)
for i in range(7):
remove_products()
remove_sums()
# This is the result because it returns the only pair with a product
# not created by anything else left in the list.
print('result', singles_operation(lambda x, y: x * y))
此问题最早据说是澳大利亚的华裔数学神童陶哲轩在网上贴出来的：
一个岛上有 100 个人，其中有 5 个红眼睛，95 个蓝眼睛。这个岛有三个奇怪的宗教规则。
注：虽然题设了有 5 个红眼睛，但岛民是不知道具体数字的。
某天，有个旅行者到了这个岛上。由于不知道这里的规矩，所以他在和全岛人一起狂欢的时候，不留神就说了一句话：你们这里有红眼睛的人。
最后的问题是：假设这个岛上的人足够聪明，每个人都可以做出缜密的逻辑推理。请问这个岛上将会发生什么？
这个问题不简单，这个游客说的话看起来没提供什么新的信息，但却能导致诡异的结果，因为“大家都知道”和“大家知道大家都知道”是不一样的。
以N=2为例，公开宣告之后，红1立刻获得了一个新的2阶知识：「红2知道岛上有红眼睛」，在公开宣告之前，他没有能力判断这个2阶命题的真假，因为在这之前命题的真假依赖于红1自己的眼睛颜色。同样，红2也获得了新知识「红1知道岛上有红眼睛」。
N=3时，公开宣告使得红1立刻获得了一个新的3阶知识：「红2知道红3知道岛上有红眼睛」，在此之前，这个3阶命题的真假也是依赖于红1自己的眼睛颜色（红则为真，蓝则为假）。同样，红2和红3也获得了类似的知识。N=4,5,6,...依此类推。
简单说，「岛上有红眼睛」这件事本来只是一项「共有知识」（Mutual knowledge），公开宣告使它变成了一项「公共知识」（Common knowledge）。这两种知识的区分在认知逻辑里面非常重要，在博弈论中有广泛的应用。
久而久之，我们越来越习惯于把「你懂的……」挂在嘴边，习惯于对房间里的大象视而不见，选择性遗忘了一个我们其实早就知道的重要事实：「大声说出来」跟「彼此心照不宣」有着决定性的区别。我们不是没有力量。一条恰当的宣言，哪怕它的内容只不过是「我知道」这么简简单单的一句话，也有可能引起整个社会的信念结构的根本改变，让许许多多人断然行动起来。这就是我们每一个人的力量。 ref
李永乐的这个讲解非常好，感谢 SedationH 在评论区推荐给我：