赤いメダルと青いメダルと白いメダル
-
ホームワーク
援軍なしでいけるやりかたについて以下のページを参考に考えてみてください。
●天秤を 3 回だけ使って 12 枚のコインの中から重さの異なる 1 枚を見つける方法‖kamadox の日記
( http://stdkmd.com/blog/2001/11/1601.html )
※私はこちらを拝見して機械式の天秤にドハマリしたのです。
-
@Hannibal さん
面白い、平衡3進コードが解になるようになっているのですね。
これで{Σ(n=0,k-1)3^n}個までk回で行ける訳が分かりました。
有難うございます。(^^♪
-
@Hannibal さんが発言 :
ホームワーク
援軍なしでいけるやりかたについて以下のページを参考に考えてみてください。プラマイ三進コード
コイン 番号 3^2 3^1 3^0 1 0 0 1 2 0 1 -1 3 0 1 0 4 0 1 1 5 1 -1 -1 6 1 -1 0 7 1 -1 1 -8 -1 0 1 -9 -1 0 0 -10 -1 0 -1 11 1 1 -1 -12 -1 -1 0 この表が出来れば、天秤の傾きの組合わせから偽コインの番号が判明するということなのですね。偽コインが1枚のときには、この方法で一般的に行けるのですね。少ない毒味回数で多くのビンの中から毒入りのワインを探すパズルを思い出しました。毒ワインを見つける場合には、二進(生・死)なのが、天秤では3つの可能性になっているところが違いますが、似た原理のように感じました。天秤のほうでは、左右の枚数が同じでなければ測定が成立しないという制限があり、ここで符号反転を使っているところが特色ですね。
改訂しました。
改訂しました。追加:
あるコインが偽のときには、それを含むコイン集合も天秤測定では偽と振る舞う点が、方法が成立する前提ですね。だから偽が複数あると成立しません。前提が成立する場合には、2つの部分集合を作る操作をN回行い、
- どのコインも1度は部分集合に含まれる(1度も選ばれないコインも1個なら許容できる)
- どの2つのコインも同じ部分集合にN回全てで入るようなことがない
- 2つの部分集合のサイズは、N回のそれぞれについて、等しい(援軍がない場合の天秤測定特有の条件)
ように出来れば、天秤の振る舞い→偽コインを含む部分集合の組み合わせが判明→1つの偽コインを特定、とできるということですね。プラマイ三進数は、その部分集合選択を、コイン番号に対応付ける方法の1つということでしょうか。
毒ワインの判定の場合にも、あるワインが毒入りなら、そのワインを含む集合も毒入りとして振る舞います。1つの部分集合をN通り作って、N人の毒見係の生死によって、毒ワインを含む部分集合の組み合わせを得ます。そして、そこから1つの毒ワインを特定します。二進数を用いて、部分集合の選択をワイン番号に対応付けることが可能です。同じ原理です。
-
みなさんからの
ご意見が脳味噌に染み込みます。
ありがたいことです。援軍ありから援軍無しにする方法で変わり種があります。
●平衡3進援軍無し
1 CCA CCB
2 CAB CBA
3 CAC CBC
4 CAA CBB
5 ABB BAA
6 ABC BAC
7 ABA BAB
8 ACB BCA
9 ACC BCC
10 ACA BCB
11 AAB BBA
12 AAC BBC●平衡3進援軍有り
1 CCA CCB
2 CAB CBA
③ CBC CAC +
④ CBB CAA +
⑤ BAA ABB *
6 ABC BAC * +
⑦ BAB ABA *
⑧ BCA ACB *
9 ACC BCC
10 ACA BCB
11 AAB BBA
⑫ BBC AAC +3,4,5,7,8,10の【6個すなわち全体の半分】の符号をひっくりかえしたものです。
並べかえると
④ CBB CAA
③ CBC CAC
2 CAB CBA9 ACC BCC
10 ACA BCB
6 ABC BAC⑤ BAA ABB
⑦ BAB ABA
⑧ BCA ACB11 AAB BBA
⑫ BBC AAC
1 CCA CCB……と、なんとなく対称性らしきものが浮かんできますね。
kamadoxさんの日記で紹介されていた一般的かつ強力な方法ではなく、場当たり的かつ手探りなものですが、これじたいひとつのパズルになっています。
-
@Hannibal さん
kamadoxさんの日記で紹介されていた一般的かつ強力な方法ではなく、場当たり的かつ手探りなものですが、これじたいひとつのパズルになっています。
私は一般解と理解していました。なぜなら、教えていただいたブログを読むと、最後に以下のように書いてあり、その先を見ると、kamadoxさんの方法で、一般的な解が得られそうな記述があったからです。ただし、以下の実際のスクリプトは現在は機能していないようなので、確かめることはできませんでした。
天秤を N 回だけ使って (3^N-1)/2 枚のコインの中から重さの異なる 1 枚を見つける方法
(...)
2004 年 12 月 6 日の日記に関連記事があります。http://stdkmd.com/blog/2004/12/0601.html
天秤を N 回だけ使って (3^N-3)/2 枚のコインの中から重さの異なる 1 枚を見つける方法
下の枠の内側は JavaScript が有効なとき N=2~10 について「天秤を N 回だけ使って (3N-3)/2 枚のコインの中から重さの異なる 1 枚を見つける方法」を表示できます。例えば (...)
-
平衡3進法は偽物1個をみつけだす機械式判定法にうってつけでした。
ところが、偽物が複数枚のときには平衡3進法はこのままでは全く使い物になりません。
「6枚中3枚の軽い偽物を天秤3回で」や「赤いメダルと青いメダルと白いメダル」では、平衡3進法の利用は難しいようです。
出題時に
「2進法で3桁あるのを平衡3進法の2桁で表せ」と解釈していいのかなあ……よくわかりませんが。と愚痴をこぼしております。
(^ω^)それではこの問題は、いったん
【クローズ(solved)】とさせて頂きます。有り難うございました。
-
@Hannibal さん
お疲れ様でした。偽コインが複数枚ある場合に、どう拡張できるのか?あるいは、まったく別の方法が必要なのかは興味深いですね。ビジュアルな理解をもう少し追ってみたいです。
-
@ソム さん
私は「kamadoxさんの日記で紹介されていた一般的かつ強力な方法」と書いております。
それに対して私の手作りの
1 CCA CCB
2 CAB CBA
③ CBC CAC +
④ CBB CAA +
⑤ BAA ABB *
6 ABC BAC * +
⑦ BAB ABA *
⑧ BCA ACB *
9 ACC BCC
10 ACA BCB
11 AAB BBA
⑫ BBC AAC +が場当たり的だと申しております。
書き方が悪くて誤解を招いたようですね。すみませんでした。
-
@Hannibal さん
あ、そういうことですね。私の読み違いでした。失礼しました。
-
@ソム が発言 :
ただし、以下の実際のスクリプトは現在は機能していないようなので、確かめることはできませんでした。
以下の場所で、使えるようになっていました:
偽物のコイン - STUDIO KAMADA
http://stdkmd.com/fakecoin/コインの枚数が29523枚も試せるようです。