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枚のケースの図解も作りました。
偽コインのペアが
⑤に含まれていれば残り５回の詠唱で確定。
さもなければ
④に含まれていれば残り４回の詠唱で確定。
さもなければ
③に含まれていれば残り３回の詠唱で確定。
さもなければ
②に含まれていれば残り２回の詠唱で確定。
さもなければ
①に含まれていれば残り１回の詠唱で確定。
さもなければ
※で確定
ということになります。
ふと思い立ちまして、
chatgpt-4o-latest-20250326 にたいして
下記のように出題しましたが、誤答を返して来ました。なお、英文なのはそのほうが生成AIにとって理解しやすいとわかったからです。
(誤答についてはナンセンスなので省略いたします。)
出題内容の下には、私がいま取り組んでいることも付記させていただきます。
皆さんにご助力を願えれば幸いです。よろしくお願い申し上げます。
♦出題内容♦
Fake Coins and a Magic Bag
You have a collection of 9 coins in total: 3 gold coins, 3 silver coins, and 3 bronze coins. Among these, exactly one gold coin, exactly one silver coin, and exactly one bronze coin are counterfeit.
Assume that the three coins of each metal are distinguishable (e.g., labeled G_1, G_2, G_3, S_1, S_2, S_3, B_1, B_2, B_3).
You are provided with a magic bag that has the following property:
When you place any subset of coins into the bag and cast a spell, the bag glows if and only if the subset contains all three counterfeit coins simultaneously, regardless of any additional genuine coins that might be included.
If the subset contains only one, only two, or none of the counterfeit coins, the bag does not glow.
All tests are deterministic and error-free. There are no restrictions on how many or which coins you may include in a single test, and coins may be reused in multiple tests.
Your task is to devise a strategy that is guaranteed to identify all three counterfeit coins using no more than 5 tests.
Justify your answer with a logical or mathematical argument.
♦出題内容はここまで♦
♥私が今もがいていること♥
この出題についてどのようなヒント(誘導)を追加すれば生成AI(chatgptなど)が正解に辿り着くか工夫をしているのですが悪戦苦闘しております。
皆さんに伺いたいのですが
なにか良いアイデアはないものでしょうか？
申し遅れました。
決定木を求めてほしかったんです。
下記の図のような。
分割統治戦略で二分木を作りそれぞれの枝において分析に必要な情報ビットが過度に大きくならないように。
