一些趣味谜题分享

前言
很多很有意思的谜题,考察逻辑思维。欢迎来看啊。
话说 AFO 已经有一段时间了,不过也没有感觉非常非常吃力。虽然还是有点不愉悦的事情,但是总都会过去的啦。
马上就会回竞赛班上课了喵。
正片开始
先来一个简单的练练手。
光路题
一束光线从一个 的网格图的西南角(可以视为 点)沿 角射入。撞到墙壁会发生全反射。请问这个光线最终会到达哪个角上?
题解
一种显然的做法是画出来,但这是不明智的。
不难发现由于光沿每个方格的对角线传播。初始情况在 。因此光经过的点的横纵坐标的奇偶性一定相同。因此对于剩下的三个角 ,只有东南角 是会被经过的。因此光最终落在东南角。
这个题太水了,就当新手教程。后面可没有那么简单。
帽子题
个人从高到矮从后往前站成一排,每个人头顶都有一个黑色或白色的帽子。后面的人可以看到前面每个人的帽子。现在需要从后往前每个人依次报出自己帽子的颜色,要求至少有 个人正确。注意每个人都不知道一共有多少个黑帽子或白帽子。
题解
显然不可能让每个人瞎猜。注意到大家能得到的信息都很有限,所以排在最后的那个人——能看到其他所有人帽子的人的信息至关重要。因此不难想到让这个人有答错的概率,来提供信息让前面的人都答对。
如何提供信息?因为你只能报黑/白颜色,因此显然无法把有多少黑帽子这样的信息藏在一个 bit 的信息中。但是黑帽子的个数的奇偶性是可以的。
商量好一个策略,例如最高的人用黑色表示看到了奇数个黑帽子,白色表示看到了偶数个黑帽子。那么随后依次的每个人都可以通过前面看到的人的黑帽子数和前面的人的回答综合得到的黑帽子的奇偶性来推出自己是不是黑帽子。
数点题
一个无限大的平面内有 个点(可以视为宽度不计,高度无限的柱子)。平面内有五个人(可以理想地认为他们宽度不计,高度有限),他们不能移动,但是可以环视四周。恰好有一个人能看到 个点,有一个人能看到 个,一个人能看到 个,一个人能看到 个,一个人能看到 个。
若已知平面内只有一个点,满足这个点上可以看到三个点。请画出一种可能的点的分布图。
题解
最大的突破口在于能看到两个点的位置和能看到三个点的位置。如果六点共线,站在中间就可以看到两个点,站在这条线外就可以看到六个点。但显然无法找到一个位置能看到 个点。还有一个情况是五点共线,另外一个点在外面,站在线上且不在任意两点间,就能看到两个点,在线上且在某两点间,就能看到三个点。然而这样的排列不符合条件“平面内只有一个点能看到三个点”。
因此点的分布一定在两条不平行的线上,两线的交点处可以看到两个点,如何保证只有一个位置能看到三个点?只需要分布在两线的点各三个,且六个点两两连线形成的三条线共点即可。文字描述比较抽象,看图:
蓝色位点表示看到两个点的位置,红色点表示看到三个点的位置。
此图中很容易找出能看到四、五、六个点的位置。
卡牌游戏
有 二十三张数字牌。你和对手拿牌,你先拿。你能拿 牌当且仅当存在至少一张还没有人拿的牌 满足 且 是 的约数。每当你拿走一张牌 后,你的对手将会拿走所有 的约数的牌。如果你没有牌可以拿了,剩下的没被拿的牌也全归对手。
你的目标是:最终你拿到的牌的数字和严格大于对手的。
题解
看起来,好像你对手总会拿走很多的牌,所以你会下意识地拿走最大的那些牌,比如 。然而,一旦你拿走了第一张牌,所有的质数牌就都不能再拿了,如果你选择拿走 ,对面就会拿到 ,这也太亏了。
如果要最小化你的“亏损”,可以考虑拿走较小的质数,比如 ,此时对面就会拿走 , 最终也会被拿走,但是这不影响。因为你还能拿 ,因为此时 还是在场的。类似的可以拿走 ,因为 在场——拿完 对手拿了 ,但是 还在,还能拿 。
按照这种思路,不难得到合法的答案:
你:,对手:。
检查武器
个人需要检查四个武器装配是否合格。九个人中有一个人是国防干部,作为检查组组长。然而其余 人当中混入了两个敌国间谍。已知组长和不是间谍的组员一定会汇报真实情况;间谍可能会汇报真实情况,也可能会汇报虚假情况(即合格武器汇报不合格,或不合格武器汇报合格)。
为了节省时间,九个人将会分成四组,每组检查一个武器。各组检查完成后,每个人都要汇报自己检查的结果(而不是以组为单位),即自己检查的武器是否合格。若已知四个武器中恰好有一个武器是不合格的,请问如何分组才能保证一定能找出那个不合格的次品。
题解
答案是 ,组长单独一组,剩下的分两个三人组和一个两人组。
因为已知组长一定汇报实情,所以组长可以单独检查一个武器。剩下 个人检查三个。注意到我们不需要四个武器是否正常的真实汇报,只需要三个,就能通过排除法得到第四个武器是否合格。
分一个两人组,两个三人组。讨论如下情况:
- 组长检查到的是不合格的,这是最简单的情况。
- 除组长外的三个组之内没有产生意见分歧,这说明二人组的两个人都是间谍且他们都说了慌,或者两个间谍都没有说谎。此时若所有人都汇报合格,则次品为二人组对应的武器,且两个人都是间谍。否则汇报次品的组对应的武器是次品。
- 三个组中有一个组产生了意见分歧,说明其他两个组的结果都是可信的。用排除法可以得到有意见分歧的组的武器是否正常。
- 三个组中有两个组产生了意见分歧,那么产生分歧的组至少有一个是三人组,且这个三人组一定只有一个间谍。因此取多数人的意见即可。然后使用排除法确定另一个组的武器是否为次品。
抽象函数求值
有一个严格增函数 ,定义域和值域都是正整数,且满足 。已知 ,求 的值。
题解
这题算是一个思维的变式,类似于脑筋急转弯。如果你直接考虑 的表达式,你会得不到结果(可能你会想到 ,但这显然不符合其定义域和值域都是正整数的条件)。
这个题的关键落在 是严格增函数和 这两个条件上。根据这个,我们很容易得到:因为 ,则 ,于是 。我们将其记作 。那么因为知道 ,所以有 。持续这样推下去,看能不能到达 。
下一步会很顺利:,然而我们会在 上卡住。前面没有任何信息告诉我们 的值,继续往后的 也是一样的道理。这个方法到这里就不行了吗?
并不是,继续往后可以得到 ,注意到 是严格增函数,,于是就很容易得到 。 和 就这么出现了。
继续可以得到 ,,,然后遇到一个不太能做的 ,接着是 ,后面出现了 ,回头得到 和 。
接着是 和 ,没关系,因为 ,用类似的方法就得到了 。
因此原问题的答案 就得出来了。
赚钱路线
如图是一个 的网格,你每次可以沿着一条边上下左右行动一步。你的目的是到达右下角,你已经行动两步了,目前在红色圆点的位置。
不幸的是,你刚刚得到消息,地方政府规定在这个区域行动会对你进行收费,并在你的目的地(即右下角)统一结算。每向右走一步,你的欠款 ;每向下走一步,你的欠款 ;每向左走一步,你的欠款 ;每向上走一步,你的欠款 。每条边只能走一次。
由于你在不知情的情况下已经从左上角向右走了两步了,所以你目前的欠款数是 。
你能否设计一条路线,使得最后你不仅不会欠款,反而会让政府给你倒贴钱(即你的欠款数为负数)呢?
题解
看起来,到达右下角需要向右和向下走,你的欠款数一定会增加,所以最后你会顶上一个巨额欠款,不说让人家倒贴钱,连抵消欠款都不可能。——真的是这样吗?
注意到虽然向右走和向下走看似增加了你的钱,向左走和向上走只能分别抵消它们的影响,但是你走的方式其实改变了这些运算的顺序。假设你持有 元欠款,那么走一个逆时针:下右上左,你的欠款会变成 元,比原来少了一块钱!
不过一直这样绕圈圈可不行,条件约束了我们不能重复经过一条边。不过,我们可以考虑绕一个大的逆时针圈,先想办法把欠款变成负数(《欠》),然后通过 操作起飞。
于是这样的正解就不难得到了,我们尽量绕逆时针圈子,可以得出:
即:下下左下右右右上上上左下左左左下下下右右右右。最后欠款为 元,也就是说你最终赚到了 元。
传送机器人
个人被分别困在不同的房间,有一个传送机器人,机器人上面有两个上下移动的拉杆(初始都在上面)和一个结束按钮。每当机器人传送到一个人面前时,这个人可以选择:
- 拉动其中一个拉杆,然后机器人会随机传送到 个人中的一个人面前(可能原地传送)。
- 按下按钮,此时按按钮的这个人,和先前拉动过拉杆的人都会离开房间。
设计一个方案,使得所有人最终都能离开(假设这 个人被困前知道这个规则并且可以充分讨论)。
你的方案应当是完备的,换句话说,他应该有 的概率可以让所有人离开,而不是“有概率”或“大概率”让所有人离开。显然有可能机器人已知都在不到 个人之间传送,但是你的方案不需要用很快的时间完成,它的耗时可足够长——如果运气不好的话。
题解
只有两个拉杆,只能表示出四种不同的状态,但是有 个人,显然拉杆是无法记录每个人是否拉过的。但是我们并不需要每个人是否拉过,只需要记录有多少个不同的人拉过。这看起来也不可能,因为两个拉杆只能产生 00,01,10,11 四种情况,无法记录 十个数字,而且如果重复传送到一个人,这个人必须拉动拉杆才行。
因此我们应该转化思路,我们不应该把计数的任务放在拉杆身上,而应该放在人身上,这样就很简单了。
在 个人之间选出一个固定的“领导人”来计数,用左拉杆表示是否有人拉动,右拉杆没有任何意义。如果机器人传送到了其他九个人中的一个,如果他们没有拉动过拉杆,而且左拉杆在上面,那么这个人就拉下拉杆。如果他已经拉过拉杆了,或者拉杆已经在下面了,就拉动右拉杆。
当机器人传送到领导人面前时,领导人的任务是看左拉杆有没有被拉下,如果被拉下,他就把他拉上去,并记录有一个人拉过左拉杆了,否则就拉动右拉杆。当领导人数出左拉杆已经被拉下九次时,说明其他每个人已经各拉动过了一次左拉杆,这时领导人就按下结束按钮,所有人都会成功逃脱。
这个过程可能持续很长,期望下也要拉动数百次拉杆,但是这总比落下任何一个人在密闭空间里饿死好。
蜂巢题
一个边长为五个单位正六边形的大正六边形蜂巢。每个单位正六边形为一个“房间”,定义两个房间相邻当且仅当两个房间之间有公共边。初始时所有的房间都没有被打蜡。你可以往里面放入若干蜜蜂。蜜蜂会按照如下方式给房间打蜡:
- 蜜蜂给自己初始所在的房间打蜡。
- 蜜蜂可以在打蜡且相邻的房间内自由移动。
- 如果一个没有打蜡的房间与至少三个打蜡的房间相邻,蜜蜂就会到这个房间给它打蜡。
求至少要多少个蜜蜂才能给整个蜂巢每个房间打上蜡。
求至少要放多少个蜜蜂才能让所有房间都打蜡。
题解
这样的问题相对复杂,我们应该寻找简化问题的方式。
注意到,假设一个没有打蜡的房间恰好和三个打蜡的房间相邻,这个房间被打蜡。所有打蜡的房间组成的图形的周长不变。原因很显然,没打蜡的房间造成了 的贡献,同时因为把三个房间一条打蜡的边界去掉了造成 的负贡献。
因为蜂巢一条边有五个房间,所以可以用周长的方法,得到至少需要 个蜜蜂才能做到。到这里我们证明出了一个下界。接下来思考如何证明下界的可行性。
应当先考虑小数据的情况。如果正六边形的边长是 ,显然只要一个蜜蜂;如果为 ,那么至少要 个蜜蜂。显然这三个蜜蜂所在的房间应该有同一个房间。与它们相邻。这是 trival 的。如果变成为 ,那么计算可得其周长为 ,至少需要五个蜜蜂。然而我们很容易得到六个蜜蜂的方案,和长度为 要三个蜜蜂的情况类似。
然后我们很快就会意识到,对于有三个蜜蜂的那一行,中间那只蜜蜂是不需要的,这个房间会被其他蜜蜂打上蜡。
这样的模式可以拓展到大小为 的蜂巢上,也就是一个倒着的 V 字形。
刻耳柏洛斯
哈迪斯(希腊神话中的冥王)将要释放地域中的一些亡灵,他命令所有亡灵排成一队,并把刻耳柏洛斯(希腊神话中的三头犬)喊到队伍的前面。三头犬的三个头分别指向队伍最前面的第一个,第二个和第三个人。然后三头犬会等概率随机选择这三个人中的一个,将其释放。排在被释放的人前面的人会出队并留在地狱,后面的人向前走补充前三个位置中的空缺。
假设队伍的长度接近无穷大,请问排在最后的人被释放的概率,以及排在第几位被释放的概率最大。
题解
我们可以抛开什么 啊,什么收敛不收敛之类的东西,用一个很简单的方法计算第一问。
显然每一轮下来都会有一个人被释放,考虑计算每一轮中被判处留在地狱中的倒霉蛋的数量的期望。因为这样的人的个数会在 中等概率随机(分别对应第一个、第二个、第三个人被释放),所以期望意义下,每有一个人被释放,就会有一个人留在地狱。因此队伍长度趋近于无穷大时,排在后面的人被释放的概率将会是 。
然后考虑第二问。不难发现,因为每轮下来队伍都会向前行进一个、两个或者三个位置,因此在某个位置上被释放的概率将会是前面三个位置对应的概率的平均值。
这是个很重要的发现,因为平均值意味着它一定不超过前三个位置释放概率的最大值。因此你总能在前面三个位置中找到一个位置,这个位置比后面的位置释放的概率更大。如此往前推就到了整个队伍的最前面三个位置。
感性理解一下不难得到第一个位置是最没戏的,第三个位置是概率最大的。精确计算可以得到三号位的释放概率为 ,是前三个位置最大的,也是所有的位置中最大的。
假币问题
有 个金币,其中有一个是假币。假币和其他金币的重量略有不同(注意你并不知道假币比真金币轻还是重)。你有一个天平,你可以称量至多三次,要求找出这其中的假币。
题解
是不是直接想到了 6-6,3-3,1-1 这样的分法?很遗憾,这是不可以的,你想的分法是用于已知假币比真币轻或重的情况,然而现在你并不知道,因此 6-6 得到不平衡的天平没有任何意义。
因此我们要更加往三分的方向靠。为了方便我们将这些金币编号 到 。
首先取 个金币分为两组 。第一次称量 两组。
若
那么可以知道假币在 中,而且 号金币是真金币。那么将 和 称量。
若
那么 中有一个是假币,第三次称量任意选其中一个和一个真币比较即可。
若
若 更重,因为 是真币,则说明 是假币(更重)或 中有一个假币(更轻)。将 和 称量,若相等则 是假币,若不等则较轻的是假币。
若 更轻,同理。将 称量,若相等则 是假币(更轻),若不等则较重的是假币。
若
不妨假设 , 的情况是类似的,和上面 和 类似。那么可以得到 中有一个假币, 是真币。要么 中有一个是重币,要么 中有一个是轻币。
将其重新分组为 。称量 和 。
若 ,则 中有一个是假币,随便拿一个和真币比较即可。
若 ,,不妨假设 要么是 中有一个更重,要么是 更轻。此时拿 称量。若相等则 是假币,否则重的是假币。
若 ,则要么 中有一个更重,要么是 更轻。同理即可。
帽子题——II
有 个人参加一个测试。每个人头顶上都有一个帽子,所有人站成一圈,使得每个人都能看到其他人帽子的颜色。一共有多少种帽子的颜色是未知的,每个人自己头上的帽子是什么颜色也是未知的,这 个人无法互相交流。测试的主办方告诉所有人,每个人最终都能通过逻辑推理的方式知道自己帽子是什么颜色。
随后测试的主办方将会定期摇铃,每次摇铃时,推出自己帽子颜色的人将会通过测试并立刻离开测试场地。于是发生了如下的事情:
- 第一次摇铃时,四个人通过测试并离开了。
- 第二次摇铃时,有若干人通过测试并离开了,他们都戴着红色帽子。
- 第三次摇铃时,没有人通过测试。
- 第四次摇铃时,有若干人通过测试并离开了,他们戴的帽子的颜色至少有两种。
- 又经过了若干次摇铃后,所有人最终都成功通过了测试。
你需要求出第五次摇铃时,有多少人通过了测试。
题解
这是一个相对困难的逻辑推理题。我们需要依次审视题目的每个条件带来的价值。为了方便,我们把带着同一种颜色的帽子的人称为同一组的人。
主办方告诉了所有人,每个人最终都能推出自己帽子的颜色,因此如果有一个人戴的帽子是独一无二的颜色,他将永远无法得到自己帽子的颜色。因此,每个组至少有两个人。
因为所有人都知道每个组至少有两个人,如果一个人看到其他人的帽子中有一个颜色只出现了一次,那么就能推出,自己的帽子一定也是这种颜色。这就是第一次摇铃发生的事情。这 个人中有两个二人组,因此这四个人都能推出自己的帽子的颜色。
如果一个人看到了两个人都戴着红色的帽子,他在第一轮之前是无法确定自己的帽子是否为红色的。但是如果只有这两个人戴着红色帽子,那他们将在第一轮意识到,并在第一次摇铃后离开。这个人发现这两个戴着红色帽子的人并没有离开,就能意识到了戴红色帽子的人不止两个——多出的那一个戴红色帽子的就是自己。这就是第二次摇铃发生的事情,带红色帽子的是三人组,这三个人都能意识到并通过测试。
至此,还剩下 人留在测试场地。按照上述方法归纳,第三次摇铃时,如果存在四人组,他们都会意识到并且得出结论。然而第三次摇铃时没有人推出了自己的帽子颜色,说明没有四人组。而第四次摇铃时,有至少两个组的人离开了,且离开的人都是五人组。不难得到只有可能为两个五人组(如果有三个,将会多出一个人戴着独一无二的帽子,不符合前文推理得到的结论)。因此第四次摇铃时,有两个五人组离开了。
第五次摇铃时,还剩下 个人,这六个人一定是一组。因此这个六人组离开了。所有人都通过了测试,符合条件。所以问题的答案是 。
异国守门人问题
有三个守门人站成一排。三个守门人分别叫做 T,F 和 R。T 总是说真话,F 总是说假话,R 说真话还是假话是随机的。你不知道三个人谁是 T 谁是 F 谁是 R,你可以通过向他们提问来找出他们谁是谁,每次提问你要选择一个人,并询问一个用“是”或“否”回答的问题,你选择的人会告诉你 OZO 或者 ULU。
然而你并不能理解这三个守门人的国家的语言,因此你不知道 OZO 和 ULU 哪个是“是”哪个是“否”。
你只能提问三次,你的目的是得出谁是 T,谁是 F,谁是 R。
题解
这是个很有名的问题,一度被认为是“史上最难的逻辑问题”。因为你不仅不知道谁是 T 谁是 F,还有一个乱说话的 R,而且你连他们的回答 OZO 和 ULU 的含义都不知道。如果连答案的意义都不知道的话,所有的推理都无从下手。
然而,我们有一种方法可以跳过理解 OZO 和 ULU 的含义——通过条件问句。假设问出这样一个问题:如果我问你 1+1=2,你会回答 OZO 吗?
- 如果 OZO 表示是,并且你问的是 T,那么他会回答 OZO。
- 如果 OZO 表示是,并且你问的是 F,他还是会回答 OZO。因为对于 2+2=4 这个问题,他会因为说谎回答 ULU,而对于这个问题,他会在说 ULU 的基础上说谎回答 OZO。这是负负得正的思想。
- 如果 OZO 表示否,类似的方法可以得到,两个人仍然都会回答 OZO。
用这个思想,假设我们用这种条件问句询问 T 或者 F 一个问题,如果结果是真,他们都会回答 OZO,如果结果是假,他们都会回答 ULU,这样就避开了 OZO 和 ULU 谁是是谁是否的问题。注意显然这种方法对 R 提问是无效的。
于是有一个基本的问法就成型了:我们先问一个问题,得到一个一定不是 R 的人,然后询问一个问题求出这个人是 T 还是 F,最后询问一个问题来鉴别出剩下两个人谁是谁。
据此得到一种可行的问法:
- 询问第二个人:如果我问你第一个人是不是 R,你会回答 OZO 吗?假设得到的结果是 OZO,那么有两种情况:你可能问的人就是 R;或者你问的人是 T 或 F,这样就能确定第一个人是 R。无论哪种情况,第三个人就一定不是 R。相反,如果得到的 ULU,就可以得出第一个人一定不是 R。
- 询问那个一定不是 R 的人:如果我问你你是不是 F,你会回答 OZO 吗?因为这个人一定不是 R,因此我们一定能得到这个人是 T 还是 F。——如果回答是 OZO,他就是 F,如果是 ULU,他就是 T。
- 得到了他是 T 还是 F 就很简单了,询问这个人:如果我问你第二个人是不是 R,你会回答 OZO 吗?然后根据回答就能得出三个人分别谁是谁。
- 标题: 一些趣味谜题分享
- 作者: Arahc
- 创建于 : 2023-07-30 08:00:00
- 更新于 : 2023-08-05 12:23:10
- 链接: https://arahc.github.io/2023/07/30/【杂项】一些趣味谜题分享/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。