問 10枚のコインのうち2枚が重い偽コインである時に天秤でそれを見つける最善手を答えよ(偽コインの重さは等しいとする) Facebookでの議論
西尾の解
- 最悪4手で確定できる。3手では不可能なのでこれは最善手である。
- 基本方針解説
- 10枚のコインのうち2枚が重いコインである場合、10C2で45通りの可能性がある。
- 3枚ずつ乗せると左が傾くのは右に偽コインが乗らない7C2=21からどちらにも乗らない4C2=6を引いた15通りであり、ちょうど1/3の確率。
- これが最も情報量の多い分け方であるのでこれを初手にする。
- 皿にどう乗せるかの選択肢は以前の選択によって狭まらないので、常に情報量が最大となる選択をする貪欲法で最適解が得られる
- 具体的な手法の解説
- それぞれのコインを0〜9と呼ぶ
- ターン1をT1と呼ぶ
- T1: 3枚ずつ比較する
- T1で片方が下がった場合
- T2: 下がった皿から2枚を選んで比較する
- 片方が下がった場合
- その皿にあったコインは偽確定する
- 残り1枚は、T2で選ばなかった1枚とT1で選ばなかった4枚の中のいずれかである
- T3: この5枚を2枚2枚1枚に分ける
- 候補が2枚になれば1手で確定できる(T4)
- 釣り合った場合
- その2枚が重いか、T2で選ばなかった1枚が重くて外の4枚の中に1枚重いコインがある。
- 「T2の2枚と、外の4枚のうちの2枚を比較」左が下がったら、その2枚が重い。釣り合ったなら(左は0枚なので)右も0枚、外の2枚のうちのどちらか。右が下がったらその2枚のうちのどちらか。
- 片方が下がった場合
- T2: 下がった皿から2枚を選んで比較する
- T1で釣り合った場合
- T2: 各皿から1枚ずつと、載せなかった4枚のうちの2枚を比較する
- T2で左が下がった場合
- その2枚のうちに1〜2枚ある
- T3: この2枚を比較
- 釣りあったならその2枚が偽
- 釣り合わなかった場合、重い方が偽
- T1で釣り合ったことから、残りの1枚はT1で皿に乗せた4枚のうちの偽コインがなかった側の2枚のどちらかである
- 候補が2つなので1手で特定できる(T4)
- T2で右が下がった場合
- その2枚のうちに1〜2枚ある
- T3: この2枚を比較
- 釣りあったならその2枚が偽
- 釣り合わなかった場合、重い方が偽
- T1で釣り合ったことから、残りの1枚はまだ皿に乗せてない2枚のどちらかである
- 候補が2つなので1手で特定できる(T4)
- T2で釣り合った場合
- この中に偽コインはない
- もし偽コインがあるなら左に1枚右に1枚あることになるが、それはT1で釣り合ったことと矛盾する
- 残る可能性は「T1で皿に乗せたコインのうちT2で選ばなかったものに左右1枚ずつある」か「今まで皿に乗せてない2枚が偽」
- T3: 「T1で左の皿に乗せたコインのうちT2で選ばなかったもの」2枚を比較する
- 釣りあったなら「今まで皿に乗せてない2枚が偽」
- 釣り合わなかった場合、下がった側の1枚が偽に確定
- 残りの1枚はT1で反対側の皿に乗せ、T2で選ばなかった2枚のどちらか。
- 候補が2枚なので1手で確定する(T4)
- T2で左が下がった場合
- T2: 各皿から1枚ずつと、載せなかった4枚のうちの2枚を比較する
- T1で片方が下がった場合
detail
- それぞれのコインを0〜9と呼ぶ
- T1: (0, 1, 2), (3, 4, 5)
-
3枚ずつ比較する
-
left: ((0, 1), (0, 2), (0, 6), (0, 7), (0, 8), (0, 9), (1, 2), (1, 6), (1, 7), (1, 8), (1, 9), (2, 6), (2, 7), (2, 8), (2, 9))
-
equal: ((0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (6, 7), (6, 8), (6, 9), (7, 8), (7, 9), (8, 9))
-
right: ((3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (5, 6), (5, 7), (5, 8), (5, 9))
-
left T2: ((0,), (1,))
- 片方が下がった場合、下がった皿から2枚を選んで比較する
- left: ((0, 2), (0, 6), (0, 7), (0, 8), (0, 9))
- equal: ((0, 1), (2, 6), (2, 7), (2, 8), (2, 9))
- right: ((1, 2), (1, 6), (1, 7), (1, 8), (1, 9))
- left T3: ((1, 2), (6, 7))
- 片方が下がった場合、その皿にあったコインは偽確定する
- 残り1枚は、T2で選ばなかった1枚とT1で選ばなかった4枚の中のいずれかである
- この5枚を2枚2枚1枚に分ける(コンピュータは少しトリッキーな分け方をしてるが未確定を左右2枚ずつでいい)
- 候補が2枚になれば1手で確定できる
- left: ((0, 2),)
- equal: ((0, 8), (0, 9))
- right: ((0, 6), (0, 7))
- equal T3: ((0, 1), (6, 7))
- 釣り合った場合は、その2枚が重いか、T2で選ばなかった1枚が重くて外の4枚の中に1枚重いコインがある。
- 「T2の2枚と、外の4枚のうちの2枚を比較」左が下がったら、その2枚が重い。釣り合ったなら(左は0枚なので)右も0枚、外の2枚のうちのどちらか。右が下がったらその2枚のうちのどちらか。
- left: ((0, 1),)
- equal: ((2, 8), (2, 9))
- right: ((2, 6), (2, 7))
-
equal T2: ((0, 3), (6, 7))
- 釣り合った場合、各皿から1枚ずつと、載せなかった4枚のうちの2枚を比較する
- left: ((0, 3), (0, 4), (0, 5), (1, 3), (2, 3))
- equal: ((1, 4), (1, 5), (2, 4), (2, 5), (8, 9))
- right: ((6, 7), (6, 8), (6, 9), (7, 8), (7, 9))
- left T3: ((0,), (3,))
- 左が下がった場合、その2枚のうちに1〜2枚ある
- この2枚を比較して、釣りあったならその2枚が偽
- 釣り合わなかった場合、重い方が偽
- T1で釣り合ったことから、残りの1枚はT1で皿に乗せた4枚のうちの偽コインがなかった側の2枚のどちらかである
- left: ((0, 4), (0, 5))
- equal: ((0, 3),)
- right: ((1, 3), (2, 3))
- equal: ((1,), (2,))
- 釣り合った場合、この中に偽コインはない
- もし偽コインがあるなら左に1枚右に1枚あることになるが、それはT1で釣り合ったことと矛盾する
- 残る可能性は「T1で皿に乗せたコインのうちT2で選ばなかったものに左右1枚ずつある」か「今まで皿に乗せてない2枚が偽」
- なので「T1で左の皿に乗せたコインのうちT2で選ばなかったもの」2枚を比較する
- 釣りあったなら「今まで皿に乗せてない2枚が偽」
- 釣り合わなかった場合、下がった側の1枚が偽に確定
- 残りの1枚はT1で反対側の皿に乗せ、T2で選ばなかった2枚のどちらか。候補が2枚なので1手で確定する
- left: ((1, 4), (1, 5))
- equal: ((8, 9),)
- right: ((2, 4), (2, 5)) src
-