程序员的喵

两个有趣的数学 Puzzle

2022-05-13

前些天在老码农群里看到一个数学 Puzzle,让我联想到另一个红眼睛蓝眼睛的问题,感觉都涉及到一点递归和博弈的意思,仔细思考一下有些趣味,分享给大家。

Sum and Product

Sum and Product

随机选择两个数字,都是小于 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 个蓝眼睛。这个岛有三个奇怪的宗教规则。

  1. 他们不能照镜子,不能看自己眼睛的颜色。
  2. 他们不能告诉别人对方的眼睛是什么颜色。
  3. 一旦有人知道了自己的眼睛颜色,他就必须在当天夜里自杀。

注:虽然题设了有 5 个红眼睛,但岛民是不知道具体数字的。

某天,有个旅行者到了这个岛上。由于不知道这里的规矩,所以他在和全岛人一起狂欢的时候,不留神就说了一句话:你们这里有红眼睛的人。

最后的问题是:假设这个岛上的人足够聪明,每个人都可以做出缜密的逻辑推理。请问这个岛上将会发生什么?

这个问题不简单,这个游客说的话看起来没提供什么新的信息,但却能导致诡异的结果,因为 “大家都知道”和“大家知道大家都知道”是不一样的。

李永乐的这个讲解非常好,感谢 SedationH 在评论区推荐给我:

你真的看懂《皇帝的新装》了吗?心知肚明和说出来有啥区别?李永乐老师讲“呐喊”的力量

公号同步更新,欢迎关注👻