「コイン13個中1個の重量イレギュラーを3回の天秤使用にて抽出せよ」問題を、巨人の肩に乗って解いてみた。

たまには脳味噌、使ってやらないとね。

• 『2ちゃんねる』で話題の超難問“てんびん”をあなたは解けますか？ | デジタルマガジン
  • http://digimaga.net/2011/09/2ch-tenbin

だそうで。

解くよ。ヽ(´ー｀)ノ　（っていうかこのドキュメントを書く時点では既に解いているのでちょっと余裕）

まず、大前提として、これが本当に「解くことが可能な問題」なのかどうか、を明らかにしなければならない。絶対に解けない問題であったり、実はまだ解答がないとされている問題だったりした場合、ストレスフルに思索するだけ時間の無駄だからね。（あるいは、「天秤のバランスチューニングを操作する」などのチート無し、正攻法で解けるのか否か、みたいな視点も。）
また、上掲記事中にあるとおり

またよく似た問題の“おもり”の数は12個ですが、今回の問題は13個です。

ということで、おもり（コイン）の個数が 12個ならば、解法は「既知」ということである。
ならば、その「巨人」（≒インターネット）の肩に乗っかるのはいいよね！

• 天秤と12個の玉(解答編) - 色即是空
  • http://cero.seesaa.net/article/10440474.html

ここで参考になったのは解法そのもの、というよりはむしろ「この問題が solvable か、否か」に関する情報科学的解説。これはありがたい。　詳しい説明はリンク先を見ていただくとして、「13個のコイン」が果たして解けるのか、否か。
12個の場合、

• log₂(12*2) / log₂3 = 2.892789...　ということで、3回で可能。（ここは引用）
  • 12個の重いか、軽いかを天秤の右か、左か、釣り合うかで調べる、ということだね。

では 13個の場合はというと、

• log₂(13*2) / log₂3 = 2.965647...　ということで、やはり 3回で可能。

因みに 14個では、

• log₂(14*2) / log₂3 = 3.033103...　3回では不可能ということになる。

ということで、「13個までなら3回で解ける」ということがわかった。　…では、どうしようか。情報科学的には 3回のうち「2.97回」を使いきらなければ解けないので、大胆な無駄があってはアウトだ。そういう観点で先程の解法を眺めると、「1回目で釣り合った場合の残り 2回の操作」にまだ「若干の余力」がありそうに「見える」。折角の「3-state」を使い切れば、あと 1枚分の「情報力」をここにまかなってもらうことが可能かもしれない。
従って方針としては、1回目は 12個のときの解法そのまま（つまり、1回目に釣り合わなかった場合のプロトコルは 12個の場合と同様になる）で、釣り合った場合に「載せなかった残りを捌く」手順を考える、ということにする。

さて、以下、具体的な解法に迫りますよ（ヒントとなる情報含む）

＝＝＝＝＝＝　完全自力で解きたい方はここまで　＝＝＝＝＝＝

まず大前提として、1回目に天秤に載せなかった残りのコイン 5個中に重量イレギュラー品があるとわかったとして、では、 5個中 1個の重量イレギュラーを2回の天秤使用で抽出することはできるのかというと、これがなんと不可能。

• log₂(5*2) / log₂3 = 2.095903...　惜しい、約0.1回分の情報量不足。

では「解けない」のかというと、そういうことではない。我々は「1回目の試行」でかなりの情報を得ている。具体的には、「1回目で天秤に載せた 8枚のコインは「シロ」であるという「情報」」。つまり、確実に正規重量であるコインを手にしている、これは非常に重要。そしてこれが何を意味するのかというと、「2回目か3回目、もしくはその両方の試行に、必ずこの「正規重量コイン」を使用すること」これが必要十分条件であるということである。つまり、「正規重量と確定したコインを再度載せる」ことで解けるし、載せるような天秤操作でないと、解けない。
…手順が見えてきた。

本当はいろいろと手こずったり試行錯誤したりしたのだが、そういうのはバッサリ省略。あと、解題よりもこのページを書く（"deco" の）ほうがよっぽど時間を要した点についてはもはや不問とする。（ていうかたぶんまだ間違ってるとこ絶対あるよね）
はてなのばーか。

＝＝＝＝＝＝　以下ネタバレ　＝＝＝＝＝＝
（ものすごく読みにくくてすみません）

コインを　(１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13) とする。

• 未判明：赤
• 正規重量と判明：黄
• 重い・または軽いと判明：緑
• 重いと判明：青
• 軽いと判明：紫

にて示す。　
つまり、黄色以外の色のコインが残数 1個になれば「状況終了」ということ。

• 【１回目】(１) (２) (３) (４) − (５) (６) (７) (８)
  • (１) (２) (３) (４) ＞(５) (６) (７) (８)
    • • • • • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
    • 【２回目】(１) (２) (５) − (３) (６) (９)
      • (１) (２) (５) ＞(３) (６) (９)
        • • • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
        • 【３回目】(１) − (２)
          • (１) ＞(２)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
          • (１) ＜(２)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
          • (１) ＝(２)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
      • (１) (２) (５) ＜(３) (６) (９)
        • • • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
        • 【３回目】(３) − (９)
          • (３) ＞(９)
            • (１) (２) (３) (４) (５) (６)(７) (８) (９) (10) (11) (12) (13)
          • (３) ＜(９)
            　　　…は、「ありえない」
          • (３) ＝(９)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
      • (１) (２) (５) ＝(３) (６) (９)
        • • • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
        • 【３回目】(７) − (８)
          • (７) ＞(８)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
          • (７) ＜(８)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
          • (７) ＝(８)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)

• • (１) (２) (３) (４) ＜(５) (６) (７) (８) 　のケースに関しては記述省略

ここまでは 12個の場合と同じ（つまり、丸パクリ）
さてここから。

• • (１) (２) (３) (４) ＝(５) (６) (７) (８)
    • • • • • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
    • 【２回目】(９) (10) − (１) (11)
      • (９) (10) ＞(１) (11)
        • • • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
        • 【３回目】(９) (11) − (１) (２)
          • (９) (11) ＞(１) (２)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
          • (９) (11)＜(１) (２)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
          • (９) (11) ＝(１) (２)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)

• • • • (９) (10) ＜(１) (11) 　のケースについては記述省略

• • • • (９) (10) ＝(１) (11)
        • • • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
        • 【３回目】(12) − (１)
          • (12) ＞(１)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
          • (12) ＜(１)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)
          • (12) ＝(１)
            • (１) (２) (３) (４) (５) (６) (７) (８) (９) (10) (11) (12) (13)

というわけである。たぶんこれでオッケー（…のはず）
事象として対称なケースは一部省略しています。

12個の場合は全てのパスでイレギュラーが「重い」のか「軽い」のかまで判明するが、13個ではどうやら「重いか軽いかまでは判明しない」ケースが残る。

というか何この無駄な努力

おまけ

だいたい記載のバグ取りが終わったらしい状況*1で改めて自分の書いたものを眺めてみると、なるほど、そういうことか、と思うことがある。連番でコインを整理した上でその終了ステータスを（一覧形式で）見ていくと、少なくとも 1回は各番号が登場することになるわけだ。…って、それはまあ、至極アタリマエな話である。で、今回は記述を省略した部分も全て書けば、軽重まで判明するコインがちょうど 2回ずつ登場することになる。私の解法では (13) のコインのみ「軽重まではわからない」ので、終了ステータスは 25通りということになる。（飽くまで結果論として述べているに過ぎないが）
情報量的に解けるとわかっていても実際に解けるかどうかはたぶん別問題の気がするし、13個のケースで本当に「重いか、軽いか」まで全て詰められないのかどうかは私には（まだ）判らない。　→　【後日追記】 1回目に都合 8個を天秤に載せるプロトコルである限り、つまり 5個を残す限り、必ず「軽重までは判明しないケース」が生ずる。　∵ 2回の天秤使用における場合分けの最大分岐数は 3² = 9 。いっぽう、5個のコインいずれか 1個に重量イレギュラーがあるという設定における場合の数は 5 * 2 = 10 。1だけ足りない。因みに「1回目が釣り合わなかった場合」の最大分岐数は 2 * 3 * 3 = 18 、コイン軽重の場合の数は 8 * 2 = 16 で 「余力」が 2 あるわけだが、1 〜 3 の 3つ（3個）の整数の積で ちょうど 16 を作ることができないのでこの「余り」を残り 5個のほうに振り分けることはできない。（現実には「ありえない」ケースで消費されている。）　←まあ、あとからはなんとでも言えるわな＞自分 *2

ついでにいうと
…よくよく見返してみたら、「私が考えた (>ω<)」と言っている部分も、12個のときの手順と殆ど変わらないじゃないか。

とんだ再発明だ。

あと、この手の問題が何故「解けてもあんまりすっきりしない」のかというと、「ほらね」「おおー」とならないからであろう。「私が正答に辿り着いたこと」を示すのに、全てのケースを試行して示さなくてはならない。勿論、「じゃあ実際にやってみせてよ」と言われたなら、何度やっても成功することが可能なわけだけれども、別にそういう日常的実用性のために問題を解いたわけではない。
…いや、解けたことが嬉しくないわけじゃあないんだ、別に。

更におまけ

標記リンク先記事に、いつの間にかしれっと解答へのリンクが追加されていた。

• shin-scope : 偽物を見破れ！解答編
  • http://gkanshin.exblog.jp/6155171

因みにこの↑エントリが上げられたのが 2006年。
2手目が若干異なる。

*1:夜中の 3時になってもまだ書き損じ・抜けがあったりだの、更新しようと思ったらはてながメンテナンスに入ったりだの。

*2:このエントリの頭のほうで「解けることがわかった（ｷﾘｯ）」みたいに書いているけども、現実には「整数の壁」に阻まれて不可能だった可能性もあるわけで、軽率の誹りは免れない。