Fake coins and a magic bag
https://jkoizumi144.com/puzzles.html
の冒頭に次のようなパズルがあります。
引用開始
1. Fake coins and a magic bag
There are 7 gold coins and 9 silver coins. Among them, there is one fake gold coin and one fake silver coin. You want to identify these fake coins using a magic bag. When you put coins into the magic bag and cast a spell, it emits a suspicious glow only if both fake coins are inside the bag. How many times do you need to cast the spell to determine both fake coins?
引用終わり
①:5 回の呪文の詠唱では無理だという考察をします。
バッグが光る・光らないの1ビットの情報を５つ集めても、最大で 2^5 = 32 通りの分別ができるにすぎません。
一方において
金銀の偽コインのありうるケースを数えあげると
7✕9=63
です。
32 < 63
ですから、
5 回の呪文の詠唱では無理そうと判断できます。
②:７回の詠唱で偽コインをつきとめる方法はあります。(省略)
③: 6回の詠唱ですますクレバーな方法があるのかどうか気になります。
63 < 2^6 = 64
ですから、《コレだけでは良い方法が無いとは断言できない》という…パズルとしては良い線を突いている感じがします。
実際、金が8枚、銀が8枚だと、６回の詠唱ですます方法はありますので、こちらが元のパズルの姿で、それをひねって金７枚銀９枚に直してあるような……
このヒネリにどんな意図があるのか頭を傾げています。
皆様のお知恵をお貸しください。
金７枚銀９枚のケースでは
６回の呪文詠唱で確実に偽コインを特定できると判明いたしました。
難しく考えていたためにどツボに嵌っていたようです。
お騒がせいたしました。
せっかくですので
金３枚銀５枚のケースで
呪文詠唱４回のやり方をひとつご案内させていただきます。
金をG1, G2,G3
銀をS1,S2,S3,S4,S5
とします。偽コインのありうるケースは15通りです。添付の図をご覧ください。
１回目の計測では①をカバーするように袋にいれて呪文を唱えます。袋が光れば、残り３回の呪文で①のなかにある偽コインペアを確定させる課題はイージーです。
１回目の計測で光らない場合には次のステップに行きます。
２回目の計測では②をカバーするように袋にいれて呪文を唱えます。袋が光れば、残り２回の呪文で②のなかにある偽コインペアを確定させる課題はイージーです。
２回目の計測で光らない場合には次のステップに行きます。
３回目の計測では③をカバーするように袋にいれて呪文を唱えます。袋が光れば偽コインペアは確定です。(G1:S5)
３回目の計測で光らない場合には次のステップに行きます。
４回目の計測では④をカバーするように袋にいれて呪文を唱えます。袋が光れば偽コインペアは確定です。(G2:S5)
４回目の計測で光らない場合には偽コインペアは確定です。(G3:S5)
なお、上記のやり方は容易に拡張できて
金7枚銀9枚のケースで呪文６回で済ませる方法があることがわかります。
金7枚銀9枚のケースの図解も作りました。
偽コインのペアが
⑤に含まれていれば残り５回の詠唱で確定。
さもなければ
④に含まれていれば残り４回の詠唱で確定。
さもなければ
③に含まれていれば残り３回の詠唱で確定。
さもなければ
②に含まれていれば残り２回の詠唱で確定。
さもなければ
①に含まれていれば残り１回の詠唱で確定。
さもなければ
※で確定
ということになります。
