FAQ
RSS
魔法の袋と偽造コイン
千夜一夜
このクイズのヒント
-
ヒント知らないよ
このクイズの参加者（4人）
算数・数学クイズ
算数・数学クイズ
天秤パズル
広告
広告
クイズ大陸関連書籍
|
|
ツイート
|
回答募集は終了しました。
|
4回だと思います
昨晩、この呪文回数でできると思いつきまして
嬉しくなって出題してしまいました。  なので、呪文の最少必要回数だけ囁いておきます。 間違っていたらどうしよう (汗  )
千夜一夜
とりあえず情報をば。
①金貨４枚銀貨4枚のケースでは ４回の呪文詠唱で金銀両方の偽コインを確実につきとめることができます。 こちらをまずは考えてみると福がつくかもです。 ②金貨３枚銀貨５枚のケースでは ３回の呪文詠唱では足りません。 金貨をABC
銀貨をabcdeとする 【１回目】ABabcd それぞれの回で、反応した場合をα、反応しなかった場合をβとする。 【２回目α】Aabcd 【２回目β】Cabcd 【３回目αα】Aab 【３回目αβ】Bab 【３回目βα】Cab 【３回目ββ】ABe 【４回目ααα】Aa 【４回目ααβ】Ac 【４回目αβα】Ba 【４回目αββ】Bc 【４回目βαα】Ca 【４回目βαβ】Cc 【４回目ββα】Ae 【４回目βββ】(何でもいい) αααα→Aa αααβ→Ab ααβα→Ac ααββ→Ad αβαα→Ba αβαβ→Bb αββα→Bc αβββ→Bd βααα→Ca βααβ→Cb βαβα→Cc βαββ→Cd ββαα→Ae ββαβ→Be βββ→４回目の結果によらず、Ce 特定までの最大回数４回、うまくいけば３回で決定できる。
偽物の銀貨と金貨が両方入っている場合のみ反応するって、むしろ偽物が本物では
 
千夜一夜
感服なのは回答の様式にです。
なるほど、こういうまとめかたもあるのですね もちろん 大正解 です。 ふふふ  金貨７、銀貨９ ６回の呪文詠唱でもできますよね！？袋は偽物探し用途に開発されたものですので 偽コインの枚数を増やすと大変そうではあります。 金貨７と銀貨９でも多分できるだろうけどパターンが結構多い。
簡単に書くと、 最初はABCDabcdefghで、反応があれば金貨か銀貨を半分ずつ減らして絞り込めばOK そうじゃなければ、EFabcdefghを試す。反応があれば、金貨か銀貨を半分ずつ減らして絞り込む。 反応が無ければGabcdefghを試す。反応があれば同様に、銀貨を半分ずつ減らしていく。 これでも反応が無ければ、iが偽物確定なので、残りの３回で金貨７枚のどれが偽物なのかを絞り込む。半分ずつ試せばOK 組み合わせのパターンを半分ずつにするように比較すれば、どんなやり方でもなんとかなる。 最初は金貨７枚×銀貨９枚で６３通りあったけど、金貨４枚×銀貨８枚で検証すれば３２通りに絞り込める。みたいな。
金貨65535枚と銀貨65537枚の場合はたったの32回でできるって！
袋に入りきらなかった 
千夜一夜
 たしかにたった 32 回でできますね！！！7✕9 の長方形を方眼紙に描いておいて 面積32、面積16，面積8 と順に長方形を削っていくのが簡明です。 
金銀パールプレゼント【何？】
問題を変化させて金銀銅の３種の硬貨が５枚づつあり、３種ともに１枚づつ偽硬貨がある、 魔法の袋は金銀銅の偽硬貨が同時にはいッているときに呪文を唱えれば光る。 ７回の呪文詠唱で全ての偽硬貨をみつけるには？ というパターンもあります。 下記の英文で、各社のAIにぶっこんでみましたがどのAIも解けずです。 今のところ人類は面目を保っています。７回に違いないと云うAIもありますが具体的な手順までは提示できずという雰囲気。 Fake Coins and a Magic Bag You have a collection of coins consisting of 5 gold coins, 5 silver coins, and 5 bronze coins. Among these, exactly one gold coin, exactly one silver coin, and exactly one bronze coin are counterfeit. You are provided with a magic bag that has the following property. Property When a subset of coins is placed into the bag and a spell is cast, the bag emits a suspicious glow if and only if all three counterfeit coins (the gold, the silver, and the bronze) are included in that subset. Determine the minimum number of spells (i.e., tests using the magic bag) required to uniquely identify the counterfeit gold coin, the counterfeit silver coin, and the counterfeit bronze coin. 偽コイン2個の場合→〇
偽コイン0～1個の場合→× （金貨K1～K3, 銀貨G1～G5） 1 K1K2＋G1G2G3G4→ 〇 2 K1＋G1G2G3G4 → ○ 3 K1＋G1G2 → 〇 4 K1＋G1 → 〇 （2～4の他のパターンは省略） 1 K1K2＋G1G2G3G4→× 2 K3＋G1G2G3G4 →〇 3 K3＋G1G2 →〇 4 K3＋G1 →〇 （2～4の他のパターンは省略） 1 K1K2＋G1G2G3G4→× 2 K3＋G1G2G3G4 →× 3 K1K2＋G5 →〇 4 K1＋G5 →〇 （2～4の他のパターンは省略） 1 K1K2＋G1G2G3G4→× 2 K3＋G1G2G3G4 →× 3 K1K2＋G5 →× 4 K3＋G5 →〇
説明が分かりにくいかもしれませんが、これでいかがでしょうか？
千夜一夜
即時に理解できませんでしたので
少々お待ちを  お待たせいたしました。 正解！ です。 ストレートな解ですね。 金貨G1～G7, 銀貨S1～S9
1 G1G2G3G4＋S1S2S3S4S5S6S7S8 →〇 2 G1G2G3G4＋S1S2S3S4 →〇 3 G1G2G3G4＋S1S2 →〇 4 G1G2G3G4＋S1 →〇 5 G1G2＋S1 →〇 6 G1＋S1 →〇 （2～6の他のパターンは省略） 1 G1G2G3G4＋S1S2S3S4S5S6S7S8 →× 2 G5G6G7＋S1S2S3S4S5S6S7S8 →〇 3 G5G6G7＋S1S2S3S4 →〇 4 G5G6G7＋S1S2 →〇 5 G5G6＋S1 →〇 6 G5＋S1 →〇 （3～6の他のパターンは省略） 1 G1G2G3G4＋S1S2S3S4S5S6S7S8 →× 2 G5G6G7＋S1S2S3S4S5S6S7S8 →× 3 G1G2G3G4＋S9 →× 4 G5G6G7＋S9 →〇 5 G5G6＋S9 →〇 6 G5＋S9 →〇 （3～6の他のパターンは省略）
金貨7・銀貨9ですが、こちらも分かりにくいかもしれません
ご指摘ありがとうございます。 確かに2番目のブロックでは偽コインを特定できませんね。
千夜一夜
御回答中の
３つあるブロックのうち ２番目のものですが。 第２項で袋が光ったらその時点で詰んでいるような気がいたします。 というのは、第５項で光らなかった時に G5S2,G6S2,G7S1,G7S2 の4通りの可能性が残るからです。 あと１回の呪文詠唱では偽コインを特定できません。 うーゆ？
そろそろ
略解をば。 ③③③③①金３ ③③③③①金２ ②②②②◎金１ 銀銀銀銀銀 ５４３２１ あり得る偽コインの組み合わせ１５通りを示したのが上図です。 (１)③の８ペアのなかに偽コインペアがあるかどうかを調べます。 すなわち銀２、銀３、銀４、銀５、金２、金３を対象に呪文を唱えます。 もしも袋が光ったらあとは簡単です。残り呪文３回で偽コインペアを特定できます。 もしも袋が光らなかったら(２)に進みます。 (２)②の４ペアのなかに偽コインペアがあるかどうかを調べます。 すなわち銀２、銀３、銀４、銀５、金１を対象に呪文を唱えます。 もしも袋が光ったらあとは簡単です。残り呪文２回で偽コインペアを特定できます。 もしも袋が光らなかったら(３)に進みます。 (３)①の２ペアのなかに偽コインペアがあるかどうかを調べます。 すなわち銀１、金２、金３を対象に呪文を唱えます。 もしも袋が光ったらあとは簡単です。残り呪文１回で偽コインペアを特定できます。 もしも袋が光らなかったら◎が偽コインペアです。 以上の手順により最大４回の呪文詠唱で偽コインペアを特定できます。 コツとしては、《最初に》袋が光るまでは 袋の中にいれる偽コインペアの対象は ８ペア→４ペア→２ペアと、だんだんと半分にすることです。 また、《最初に》光ったあとに残りの呪文回数で特定可能かどうかも検証しておきたいですね。
略解よりもさらに略ですが。
金７枚銀９枚の図解です。 考え方は金３枚銀５枚のときと同じです。 呪文詠唱は６回で十分となります。 ⑤⑤⑤⑤⑤⑤⑤⑤②金７ ⑤⑤⑤⑤⑤⑤⑤⑤②金６ ⑤⑤⑤⑤⑤⑤⑤⑤②金５ ⑤⑤⑤⑤⑤⑤⑤⑤②金４ ④④④④④④④④①金３ ④④④④④④④④①金２ ③③③③③③③③◎金１ 銀銀銀銀銀銀銀銀銀 ９８７６５４３２１
金銀パールプレゼントの問題は
海外のパズル掲示板に出題したところ 翌日には正解者がでました。 …ひと工夫必要でして  なかなか非常識な思いつきが必要？ 金銀銅3種各5枚の場合について考えます．
以下金のコインをそれぞれG1,...,G5と呼ぶことにして， 同様に銀はS1,...,S5，銅はB1,...B5とします． また袋に入れて呪文をとなえる試行について， G1,G2,G3,S1,S4,S5,B1を入れるのをF(123,145,1)等と表記することにします． まずは解法の指針について簡単に考察したあと，解答を書きます． 解答だけ見る場合は後半の[解答]以降を読んで下さい． [考察] 答えとしてあり得る偽コインの組み合わせは5×5×5=125通りです． まずはこれを125個の単位立方体からなる5×5×5のキューブに対応させます． ルービックキューブを5×5×5にしたようなイメージです． 各単位立方体をブロックと呼ぶことにします． キューブを構成する各ブロックを区別するためGSB座標をつけます． たとえばG1S2B4が答えのときは(1,2,4)の位置にあるブロックが答えです． ここで答えのブロックは赤に塗られていてそれ以外は白とします． すると最初の問題は，袋をうまく使って赤いブロックの位置を割り出すことに対応します． ここで例えばF(123,123,123)を実行するとどうなるか考えてみます． 袋が光った場合は赤いブロックが対応する3×3×3の部分キューブの中にあり， 光らなかった場合は外側にあります． つまりこの魔法は何らかの直方体でキューブを切り取ったときに， 赤いキューブがその中にあるかどうか確認することが出来る魔法です． 厳密にはF(14,24,1)等の直方体でない切り取りも存在しますが， 本質的には大きな違いではなく， また今回は直方体のみで最後までたどり着ける解法を作ります． あとはどのような直方体で切り取っていくかを考えることになります． ここで全パターンが125通りで，これは2^6<125<2^7であるので， 最低でも7回は魔法が必要です． ところで最初にF(123,123,123)の切り取りをすると， 光った場合はパターン数が3×3×3=27<2^5なので，残り5回で絞り込めそうですが， 光らなかった場合125-27=98>2^6なので更に7回以上魔法が必要です． どちらに転んでも残り回数を6回以内に抑えるためには， 内外ともに2^6=64通り以下に抑える必要があります． つまり直方体を選ぶ際に一方にブロックが固まらないようにする (2^kを超えないようにする)のが重要です． 以下ではこのことに気をつけながら直方体を選んでいきます． まずは一回目の魔法ですが，F(1234,1234,1234)とすれば 内側は64個で外側は61個です． ここで赤ブロックが内側にあった場合は二分探索で簡単です． 赤ブロックが外側の場合を考えます． 残った61個のブロックはもともとのキューブの3枚の面に対応します． この内天井の面(B=5)にあるブロックは25個です． 更に一つの辺(G=1,S=5,Z=1234)を加えると29個になりちょうど良さそうです． 具体的にはF(2345,12345,1234)とすれば内側32個外側29個です． ここで赤が内側の場合は2つの4×4の面に分離できるので簡単です． 外側の場合を考えます． 内外ともに16以下になれば良いですが， これは天井面から4×4の面を切り取ればよいです． 具体的にはF(1234,1234,5)とすれば良いです． 今度は内外ともに切り分けやすい形なので後は簡単です． 以上を踏まえて解答を書きます． [解答] 手順1:F(1234,1234,1234) 光った場合はG5,S5,B5は本物です． 後は各色の偽物を独立に，それぞれ2回の試行で特定できます． 例えばGの偽物を特定する場合F(12,1234,1234)とすると， 光った場合はG1かG2が偽物であり，光らなかった場合はG3かG4が偽物です． 同様にF(13,1234,1234)をして双方の結果を比較すると偽物が特定できます． したがって総試行数は1+2×3=7回です． 手順1で光らなかった場合ですが， G5,S5,B5のうち少なくとも1つは偽物です．...① それを踏まえて手順2に進みます． 手順2:F(2345,12345,1234) 光った場合はB5が本物であることが確定するので， G5かS5の少なくとも1つは偽物です． またG1が本物であることも確定します． 手順2-1に進みます． 手順2-1:F(2345,5,1234) 光った場合はS5が偽物であることが確定します． またGとBの偽物候補はそれぞれ4種なので独立に各2回で特定できます． 総試行数は3+2×2=7回です． 手順2-1で光らなかった場合ですが， 手順2と手順2-1ではS以外の構成は変えていないので， S1,S2,S3,S4の中に偽物があったことが確定し，S5は本物です． したがってS5とB5が本物なので①よりG5は偽物です． またSとBの偽物候補はそれぞれ4種類なので，独立に各2回で特定できます． 総試行数は3+2×2=7回です． 続いて手順2で光らなかった場合ですが， G1かB5の少なくとも一方は偽物です． もしB5が本物であればG1が偽物なので①からS5が偽物です． すなわち「B5が偽物」か「G1とS5が偽物」のどちらかは成り立ちます．...② これを踏まえて手順3に進みます． 手順3:F(1234,1234,5) 光った場合はB5が偽物であることが確定し， GとSの偽物の候補はそれぞれ4種類なので，独立に各2回で特定できます． 総試行数は3+2×2=7回です． 手順3で光らなかった場合ですが， B5が偽物である場合はG5かS5の少なくとも一方は偽物です． ②と合わせると， 「G5かS5の少なくとも一方が偽物」と「G1とS5が偽物」のどちらかは成り立ちます．...③ 手順3-1に進みます． 手順3-1:F(1,12345,12345) 光った場合はG1が偽物です． ③よりS5も偽物です． またBについては情報がありませんが，3回の試行で簡単に特定できます． 総試行数は4+3=7回です． 手順3-1で光らなかった場合ですが， G1が本物であることが確定します． したがって②よりB5が偽物であることも確定します． 同様に③よりG5とS5の少なくとも一方が偽物です．...④ すなわち答えとしてあり得るのは， (2,5,5,),(3,5,5),(4,5,5),(5,5,5),(5,1,5),(5,2,5),(5,3,5),(5,4,5) の8通りです． 手順3-2に進みます． 手順3-2:F(2345,5,5) 光った場合はS5とB5が偽物であり， Gの候補は4種類なので残り2回で確定します． 総試行数は5+2=7回です． 手順3-2で光らなかった場合ですが， B5は既に偽物でありG1は本物(G2,G3,G4,G5の中に偽物がある)ので，S5は本物です． したがって④からG5が偽物であることも確定するので， S1,S2,S3,S4の中から2回の試行で偽物を特定できます． 総試行数は5+2=7回です．
3種各5枚の場合を考えてみました。
千夜一夜
油断してました、すみません。
今、お酒入ってまして、明日拝見致します。 申し訳ありません。 (手順2あたりからバリアントがあるのですね。) 追伸です 正解！！！ ツボを押さえている感じが好きです
logi さんへ。
多量に文字化けしていて申し訳ありません とりあえず。 私が事前に用意していたのが以下です。 ざっとチェックした範囲では本質的にlogiさんによる御回答と同じはずです。よろしくお願いいたします。 Let C_u = {(i, j, k) | 1 ≤ i ≤ 5, 1 ≤ j ≤ 5, 1 ≤ k ≤ 5} be the set of all possible combinations of indices for the gold, silver, and bronze coins; this set has 125 elements. If we let g ∈ {1, 2, 3, 4, 5} be the index of the counterfeit gold coin, s ∈ {1, 2, 3, 4, 5} the index of the counterfeit silver coin, and c ∈ {1, 2, 3, 4, 5} the index of the counterfeit bronze coin, then the set representing the triplet of counterfeit coins is the singleton set F = {(g, s, c)}. We now define the following subsets of C_u: C_1 = {(i, j, k) | 2 ≤ i ≤ 5, 1 ≤ j ≤ 4, 2 ≤ k ≤ 5}. The number of elements in C_1 is 64. C_21 = {(i, j, k) | i = 1, 2 ≤ j ≤ 5, 2 ≤ k ≤ 5}. The number of elements in C_21 is 16. C_22 = {(i, j, k) | 2 ≤ i ≤ 5, j = 5, 2 ≤ k ≤ 5}. The number of elements in C_22 is 16. Define C_2 as the union: C_2 = C_21 ∪ C_22. Thus, the number of elements in C_2 is 32. Also, let T_2 = {(i, j, k) | 1 ≤ i ≤ 5, 2 ≤ j ≤ 5, 2 ≤ k ≤ 5}. Then we have: C_2 = T_2 ∩ (C_u - C_1). Next, define C_3 = {(i, j, k) | 2 ≤ i ≤ 5, 1 ≤ j ≤ 4, k = 1}. The number of elements in C_3 is 16. Define C_41 = {(i, j, k) | i = 1, 2 ≤ j ≤ 5, k = 1}. The number of elements in C_41 is 4. And C_42 = {(i, j, k) | 2 ≤ i ≤ 5, j = 5, k = 1}. The number of elements in C_42 is 4. Let C_4 = C_41 ∪ C_42. The number of elements in C_4 is 8. Also, let T_4 = {(i, j, k) | 1 ≤ i ≤ 5, 2 ≤ j ≤ 5, k = 1}. Then: C_4 = T_4 ∩ (C_u - (C_1 ∪ C_2 ∪ C_3))). Next, define C_5 = {(i, j, k) | i = 1, j = 1, 2 ≤ k ≤ 5}. The number of elements in C_5 is 4. Finally, define C_6 = {(i, j, k) | i = 1, j = 1, k = 1}. The number of elements in C_6 is 1. It is clear that for any two different sets X and Y chosen from {C_1, C_2, C_3, C_4, C_5, C_6}, we have X ∩ Y = ∅. Moreover, C_u = C_1 ∪ C_2 ∪ C_3 ∪ C_4 ∪ C_5 ∪ C_6. In terms of element counts, we have: 125 = |C_u| = |C_1| + |C_2| + |C_3| + |C_4| + |C_5| + |C_6| = 64 + 32 + 16 + 8 + 4 + 1. To determine the indices g, s, and c of the counterfeit coins, we proceed with the following operations: First Spell: We test whether F = {(g, s, c)} is a subset of C_1. If the result is true (i.e., the bag glows), then it is almost evident that g, s, and c can be determined with the remaining 6 spells. If the result is false, we move on to the next step. Second Spell: We test whether F = {(g, s, c)} is a subset of T_2. If the result is true, then it immediately follows that F ⊂ C_2 = C_21 ∪ C_22. Then, with the remaining 5 spells, g, s, and c can be determined almost trivially. If the result is false, we proceed to the next step. Third Spell: We test whether F = {(g, s, c)} is a subset of C_3. If the result is true, then with the remaining 4 spells g, s, and c can be determined almost trivially. If false, we continue to the next step. Fourth Spell: We test whether F = {(g, s, c)} is a subset of T_4. If the result is true, then it immediately follows that F ⊂ C_4 = C_41 ∪ C_42. Then, with the remaining 3 spells, g, s, and c can be determined almost trivially. If the result is false, we move on to the next step. Fifth Spell: We test whether F = {(g, s, c)} is a subset of C_5. If the result is true, then with the remaining 2 spells, g, s, and c can be determined almost trivially. If the result is false, then F = {(g, s, c)} must be equal to C_6, which implies that g = s = c = 1.
文字化けの部分は恐らく不等号と空集合記号なので，
補完して読ませていただきました． 本質的には同じことをしているようです． 集合論の記法をつかうと，（読める人には）とても読みやすいですね！ C_iとT_jを上手く使い分けているのが素敵です．
千夜一夜
この金銀パールの魔法のカバンの問題はTをみつけるのがひとつの変化球になっていますね。
そのあたりが苦手なのか生成AIが解いてくれないのが興味深いです。 人間には突破できそうというヤマカンが働くのですが…… 生成AIはすぐに諦めます。 ※なお、生成AIに尋問したら、この手のパズルは学習済みではないとのことでした。 |
問題へジャンプ