命题:一个有趣的悖论

最近在复习大一的离散数学,看到一道好玩的悖论题目,分享一下。
原文:

Albert announces to his class that he plans to surprise them with a quiz sometime next week.

His students first wonder if the quiz could be on Friday of next week. They reason that it can’t: if Albert didn’t give the quiz before Friday, then by midnight Thursday, they would know the quiz had to be on Friday, and so the quiz wouldn’t be a surprise any more.

Next the students wonder whether Albert could give the surprise quiz Thursday. They observe that if the quiz wasn’t given before Thursday, it would have to be given on the Thursday, since they already know it can’t be given on Friday. But having figured that out, it wouldn’t be a surprise if the quiz was on Thursday either. Similarly, the students reason that the quiz can’t be on Wednesday, Tuesday, or Monday. Namely, it’s impossible for Albert to give a surprise quiz next week. All the students now relax, having concluded that Albert must have been bluffing.

What, if anything, do you think is wrong with the students’ reasoning?


译文:

艾伯特老师宣布,他下一周会给同学们来一次“突击”测验。

他的学生首先开始考虑能不能是周五,结论是否定的:如果测验放在周五,也就是前4天都没有测验的话,那么周四下课的时候同学们就知道测验一定是在周五的,这场测验就算不上“突击”的了(1)。

接下来同学们又开始向前推,他们发现也不可能是星期四:(1)处已经证明了不能是在周五测验,如果放在周四测验的话,那么在周三下课的时候同学们就会知道肯定是在周四测验了——周一周二周三没测,周五不可能,只能是周四了,这场测验就算不上“突击”了(2)。形似地,同学们接着往下推,不可能是周三 -> 不可能是周二 -> 不可能是周一。也就是说,艾伯特老师不可能给我们一次突击测验,他是在吓唬我们!

你认为学生的想法错在哪里?




我先用反证法证明学生错了:

如果学生的说法是对的,即P : 老师不可能在下周给我们来一次突击测验。那么如果老师在下周任意一天安排一次测验,上课的时候学生的反应是这样的:不会有测验的哈哈 -> 握草老师抱的是什么 -> 我擦居然要测验。也就是说,老师达到了“突击”的目的。即┐P : 老师在下周给我吗来一次突击测验。由(p -> ┐p) -> ┐p,我们可以得到学生的说法是错的。

书上说这是一个悖论(就是说我上面的推理也不会成立),但没有给出解释。我曾经和我的一个舍友讨论了半个小时,也没能说服对方。

我的想法是对“突击”的理解导致的悖论的发生,“突击”(surprise)可以有两个理解:

  1. 学生上课的时候没有想到今天会测验。
  2. 除周五以外,学生上课前不知道测验会安排在哪一天。

题目中学生的推论是基于2的,但是在推周五之外的时候假设周五已经不可能测验了,这就是导致错误的地方——2的基础就是除周五外学生不知道安排在哪一天——即周五也是可能的,在推周四的时候不能说周五不会测验。我的反证法是基于1的。但老师的说法并不知道是哪一个的,所以说,这个题是无解的。

以上就是我的一些想法,并不知道对错,还望各位看官提出自己的见解。




参考:

  1. Mathematics for Computer Science
原文地址:https://www.cnblogs.com/liqiuhao/p/7785034.html