PuzzleCat

【趣题分享】寻找冗余——硬币问题解答

本题目改编自b站up主 亮蓝色暖水瓶 在某谜题群内分享的题目,已获授权 硬 币 游 戏 解 答 问题回顾 桌子上有9枚硬币, 主持喵 指定其中一枚,由我们设定正面反面, 主持喵 再指定一枚没有指定过的硬币,我们再设定正反……如此往复,直到…

萨菲喵
萨菲喵
Produced by 喵喵喵解谜~6 min read2089 words简体中文

本题目改编自b站up主亮蓝色暖水瓶

在某谜题群内分享的题目,已获授权




问题回顾

桌子上有9枚硬币,主持喵指定其中一枚,由我们设定正面反面,主持喵再指定一枚没有指定过的硬币,我们再设定正反……如此往复,直到只剩一枚硬币没有被指定过,这枚硬币由主持喵设定其正反。现要求另一个喵能只通过硬币的局面按照我们事先商量好的对策选取5枚硬币涵盖那枚主持喵设定的硬币。(具体问题见上一篇推文,点击页面最下方阅读原文




01


题目一

功夫喵出题

功夫喵在桌子上摆着9枚硬币。



9枚硬币,我们允许提取5枚来涵盖功夫喵所设定的硬币X,也就是说最后一枚硬币无论是被设定为正面还是反面,我们都可以将它归到某一个类当中。那么我们只需要在前8枚硬币中设定4枚正面朝上,4枚反面朝上。最终就必然有5枚硬币朝向是相同的。问题也就解决了。



这个问题很简单,但很明显存在了大量冗余,前8枚硬币中,4枚正面的硬币是前四枚还是后四枚,亦或者是中间四枚,这个地方还存在着大量变化。这就是问题或者策略的冗余,是可以深入的地方。



02


题目二

牡丹喵出题

牡丹喵在桌子上摆着由5x5枚硬币组成的方阵。



第二道题问题没有变,但硬币数量从9枚跃至25枚(5*5)。由于主持喵可以随意指定硬币的位置,导致硬币的指定变化很多,我们应当在众多变化中寻找一些不会改变的东西。比如每一行都有一枚硬币是这一行最后指定的,基于这点再效仿第一个问题,我们可以每一行的前四枚被指定的硬币都设定为正面朝上,而最后一枚设定为反面朝上。那么最终要么是某一行有五枚正面朝上的硬币,要么是每一行都有且只有一枚反面朝上的硬币。



如果你仅仅思考到这里就尝试下一个问题,那么你很可能会被局限在四正一反这样的思路中。尝试五正一反,尝试每行每列除了最后一枚都是正的,诸如此类,都离第三个问题的解答相距甚远。因为这种方法在第二个问题中就存在着一个致命的问题——没有冗余,策略没有冗余,那么多出了一行哪来的余力进行处理呢?

在这个问题上,有喵提交过另一种更加接近问题本质的回答(四静一变):每一行的前四枚硬币被指定到的硬币不翻面,而最后一枚翻面。我在改编题目的过程中,让两名玩家能够同时在房间里商量对策,所以他们都可以观察到硬币的初始摆放情况。基于这方面的思考,让我们比原来更易于得到这样的答案。(实际上原问题中两个玩家商量对策时只知道硬币数量)

现在,我们再深入一点这个问题,无论是四正一反,还是四静一变,我们都是让最后一枚硬币成为特殊的存在。这实际上是对X位置的一种弱化。

很显然的一点是:因为主持人指定的硬币X是最后一枚硬币,所以如果我们任意框定若干枚硬币,且这些硬币中含有X,那么X也一定是这些硬币中的最后一枚。

换句话说,如果某一枚硬币是某一些硬币中的最后一枚,那么它就可以是X的“候选人”,我们可以将这样的硬币称作是Y。Y中的Y就是X。

那么我们的目的就是通过某种方法,让最终Y的数量不超过5枚。

Y是四正一反方案里的反,也是四静一变里的变。

那么第二题方案的本质是:让每行都产生一枚特殊的硬币Y。

至于这枚硬币是正是反,是翻面还是不翻面,都是不重要的。

如果我们注意到四静一变这种策略不在乎硬币的初始摆放,我们就能发现:我们可以指定任意一种摆放局面为【初始】,而我们只需要根据我们所指定的【初始】设定每一个被指定到的位置的硬币并使得每一行的最后一枚被指定的硬币与【初始】相反即可。如果注意到了这点,就会发现这里是一个非常巨大的冗余点,四正一反的策略仅仅是【初始】为全正时的特殊解。而注意到这些以后,我们就可以想办法让每一行都足够特别。



03


题目三

萨菲喵出题

萨菲喵在桌子上摆着由6x5枚硬币组成的方阵。



我们要保证Y的数量不超过5,那么每一行可以且仅可以设定一枚Y,主持喵只要根据我们设定的初始开局将某一行还原,这一行就存在着6枚硬币,且它们都可能是X。那么我们应当设想一种办法,在这一行中剔除一枚硬币。自然,首要考虑的是这一行的第一枚被指定的硬币。

每一行的最后一枚被指定的硬币Y是X的候选人。

而每一行的第一枚被指定的硬币必然不是X的候选人,我们将之称为Z。

为了找出硬币Z,我们在硬币设定的那一刻就应开始对这一行进行布局。一共有六列,所以Z有6种可能,我们可以设定6种类别,让每一种对应上一串特定的6位的2进制串,那么菱纱喵就可以根据每一行的类别,找出这一行的Z硬币。但是这个2进制串里有一个不稳定的存在Y,为了让菱纱喵能够识别出来,每一串码中的任意一位数字产生错误,都应不会与其他的码混淆。那我们只需要让这些二进制码串中两两差异都不少于3个即可。

稍加尝试,既可以得到这样的一组二进制码串。(0/1表示正/反)

(1)000000

(2)000111

(3)111000

(4)011011

(5)101101

(6)110110

任意行所指定的第一枚硬币Z所在的列k => 该行选择的模式(k)。

任意行所指定的最后一枚硬币Y则由我们设定为与模式相反。

最终,若每行都有一枚Y,则提取五枚Y硬币。

若有一行没有Y,则排除该行的Z,提取剩余五枚硬币。

这样,不论主持喵如何操作,我们都成功选中了他所藏匿的硬币。可对于主持喵来说,这是否代表着,有时候我们即使知道一切,却也无能为力呢?





答题结果

根据邮箱情况,功夫喵牡丹喵问题的首位破解者为【皮皮喵】,而萨菲喵的问题并没有人/喵回答正确。



文字 | 月饼喵

美工 | 萨菲喵


Comments

No comments yet

    【趣题分享】寻找冗余——硬币问题解答 - PuzzleCat