まずは、簡単なところから攻めていきます。
情報理論的に、天秤2回で偽装硬貨を特定できるのは、硬貨が4枚までの場合です。
というわけで、まずは、硬貨が4枚の場合で考えてみます。
繰り返しですが、天秤によって、重い・軽い・同じの3種類の情報が得られます。
というわけで、基本方針は「3つに分けて、そのうちの2つを天秤にのせる」です。
天秤が傾く→1か2が偽装、3と4は本物。
天秤が釣り合う→1と2は本物、3か4が偽装。
たとえば天秤が傾いた場合、つまり1か2が偽装硬貨の場合。
そのうちの片方を本物と比較します。
天秤が傾く→1が偽装。
天秤が釣り合う→1は本物、つまり2が偽装。
1回目で天秤が釣り合った場合も対称に考えたら良いです。
ここまでは簡単。
問題は硬貨が12枚の場合だ!
コメント