脑力小体操：解答“不可能被解答的”问题

前文 空无一人的房间里的问题来自Microsoft Research。

有一排相连的房间，为了方便，从左到右编号为1、2、……、6(暂且考虑6间的情况)。相邻房间的墙壁上有一道门(为了方便，管这种叫间隔门)。

现在告诉你说，某个房间里有个能够预知一小段未来的超能力者，你的任务就是在下面的游戏里胜过他(他就会成为你的队友，然后变弱……)。

游戏规则如下

你每次可以打开任意一个房间的正门，如果超能力者恰好在里面，你胜出。

如果里面是空的，你要退出房间，关上门。稍等片刻，才能再次选择房间开门。

每次你退出房间后，超能力者就从间隔门来到左边或右边的房间(比如说原本在2号房，现在来到1号或3号)。请注意，在你退出后，超能力者必须移动——他不能停留在原来的房间里——同时，他必须在你离开房间关上门后才能移动，这是规则。

如果超能力者上一轮在1号或6号房，那他本轮只能去2号或5号。

因为超能力者的预知能力，所以他每次换房都是最有利自己的选择——除非选无可选。

游戏时间有限，不能无限玩下去。

原本是要求给出n=13时的(最差情况下的)最少开门次数(运气好的话，可能第一次开门就结束了)。

最关键的思路就是想到用奇偶分析。8成评论都想到了，大家厉害啊。

简要分析如下

如果一开始预言家在偶数号房间。那么我们第一轮就进入2号房，不在的话就依次向右开门，到3、4、5号房。因为根据假设，我每次进入的房间和预言家所在的房间具备相同的奇偶性，所以当我从2号房开始的时候，则不可能出现这种情况：我们两人交错而过，他在某轮跑到我上一轮所在的房间——他必然每次都在我的右侧房间里。

如果我到了5号房，依然没有逮住他，那就说明最开始的假设——预言家在偶数号房间——是错误的。也就说，从一开始，我每次进入的房间号数，和他待着的房间号数，奇偶性恰好相反。此时此刻，我在5号房，则他应该在2/4/6号房。

换而言之，如果我下一轮重复进入5号房，则此时我们二人的奇偶性必然一致。局面就变成，预言家必然在1或3号房——亦即在我左面的房间。与前面的分析类似，当我依次打开4、3、2号房间的时候，因为奇偶性一致，他不可能与我擦肩而过。最后必然被堵在某个房间里。

---

本期问题为历史上著名的“不可能问题”。

话说小美和小明、小红玩智力猜数游戏。小美在心里想了两个不为1(经评论后补充条件)的自然数x、y。

然后偷偷告诉小明——这两个数的和x+y；偷偷告诉小红——两个数的积xy。

要求他们二人猜出x和y是多少。

小明略微思索了一下，斩钉截铁地说道：我是不知道答案，但小红也绝对不可能知道答案。

未料想话音刚落，小红就笑了：既然你都这么说了，那我知道是哪两个数字咯。

小明也笑了：那我也知道答案了。

他们把数字写在了左右手上，然后同时展示给对方以及小美看。

小红和小明是对的。现在问你：x、y是哪两个数字？

稍微举例提示一下，如果小美告诉小明和=10，而10=3+7，也就是说存在一种情况：小红听到的积=21，那样根据因子分解，小红仅仅凭借最开始的条件，就能猜出x/y分别是3和7。因为对称性，哪个是3哪个是7并无所谓。

这样一来，小明就没有道理那么笃定地说“小红也绝对不可能知道答案”。

反过来，听到他这句话，小红则也获得了类似的信息，知道小明的和是无法写成两个素数的乘机滴……

如果有难度的话，可以加一个限制：x和y在100以内。但其实……应该……不需要这个条件……吧，或许。

赞一个 (13)