見た目も大きさも同じ8個の重りがあります。7個は重さも同じですが1つは他よりわずかに軽いニセモノです。天秤を使ってニセモノを確実に特定するには何回天秤を使う必要があるでしょうか。ただしこの天秤はただの天秤ではなく嘘つき天秤で、1回だけ嘘をつく（左に傾く・右に傾く・釣り合うの中から間違った結果を出す）可能性があります。
まず私の解答を書きます。正解は4回です。4回で確実に特定する手順は以下の通り。
１２３
４５６
７８９
重りを上のような3×3の行列風に並べます（９はダミー）。
4回の各測定で、横・縦・右斜め・左斜めの列ごとに3個ずつをそれぞれグループとし、９が入っていない2グループを天秤に載せます。
釣り合った場合は皿に載っている6個を、傾いたら上がった皿に載っている以外の6個に白判定回数を+1します。
4回目が終わった時各重りの白判定回数が1以下のものが1つだけ残ります。それがニセモノです。
次に3回以下ではできないことを示します。結果的にニセモノを特定できた時、同時に天秤が何回目にどんな嘘をついたか、あるいは嘘をつかなかったかも全て特定されます。
天秤を3回使う時、天秤の嘘のつき方は1-3回目でそれぞれ2通りの嘘をつく、あるいは全くつかないの7通りがありえます。さらにニセの重りがどれかで8通りの場合があるので、問題全体の場合の数は 7 * 8 = 56 通りです。
対して天秤から得られる情報は最高でも 3 ^ 3 = 27 通りしかありません。3回で確実にニセモノを特定できるということは、27通りの結果を見ただけで56通りの問題のどれかひとつを確実に言い当てられることを意味し、これは明らかに不合理です。
よって3回では特定できません。
解説
元となった有名な金貨8枚の問題（ビルゲイツの面接試験にももちろん載ってる）に適当に条件を付け加えてみたら意外にもすごく面白い問題に化けてしまいました。
一見答え方も元の問題と同じに見えます。元の問題は2回で特定できます。それを応用すれば、各測定を2回繰り返し、嘘が出て割れた場合だけもう一回必要なので答えは5回……と言いたくなります。
しかし！ 正解は4回でした。4回でできる方法があったんです。面白いですね。最初は元の問題の先入観から「まず１２３と４５６番の重りを天秤に載せて、釣り合った場合……」という風にニセモノを特定する方向で考え始めたので、ややこしすぎてハマりました。
で答えてもらったDanielさんの解答を見るとそれでできないわけではないですが。
解法を見つけるには元の問題に立ち返って、そもそも天秤で何をしているのか、そして特定できたと言うためには最後にどのような状態になっていなければならないかをちゃんと原理から見直さないといけませんでした。
まず天秤が釣り合うということは皿に載っている全ての重りが白だということです。天秤が傾くということは上がった方の皿に載っているもの以外の全ての重りが白だということです。
そして3/3/2個に分けるのは、天秤の1回で3通りを識別できる特性を最大現生かすためです。
そしてここからがポイントですが、今回の天秤が1回だけ嘘をつくかもしれない中で、ニセモノを特定できたと言える条件は他の7個の重り全てが2回以上白判定を受けていることです。
2回以上白判定を受けていれば最低でもどちらかは真実、すなわちその重りは本物です。逆に言えばその条件を満たせなければ失敗です。
条件を満たすには、もっとも運が悪い場合でも確実に白判定の数が0や1の重りを追いつめ、その数を減らすことができるようにグループ分けしなければなりません。
それを可能にする方法は、ある時点でもっとも白判定回数の少ないものが最大限別々になるような3グループに分けて計り続ける方法です。ここまで来てようやく行列風のグループ分けに思いいたりました。
具体例
ニセモノは3、2回目に嘘が出て釣り合うはずが左に傾く場合。ただし3*3の数字は、
１２３
４５６
７８９と同じ位置にある番号の重りの白判定回数。
１回目：１２３・４５６・７８９がグループ
０００
１１１
１１１２回目：１４７・２５８・３６９がグループ
１０１
２１２
２１２３回目：１５９・２６７・３４８がグループ
２１１
２２３
３１３４回目：１６８・２４９・３５７がグループ
３２１
３２４
３２４結論：1回しか白判定されていない３がニセモノ。
3回でできないことを示した方法はもっと一般的にできます。k回天秤を使い、重りがn個の時、
n(2k+1) > 3^k
ならば特定不可能です。問題は n=8 k=4 だったので 72 <= 81 なので特定できたのは不思議ではありません。
というか私が諦めずに4回でできる方法を探したのは先にこっちの式でできないと決まったわけではないとあたりをつけていたからです。
また、この式から重りが9個でも、81 = 81 なのでできるかもしれないことが分かります。現に上の解答の手順でダミーを本物と区別しないだけでできます。
天秤を3回しか使わない場合、できるのは3個までということも分かります。4個になると28 > 27 なのでできません。
しかし、適当に考えた割には本当に面白い問題でした。付き合っていただいた方々ありがとうございます。
コメント
楽しく拝見させて頂きました。
こちらの “Seeking Mathematical Truth in Counterfeit Coin Puzzles” と題されたページに類似問題が掲載されています。「嘘つき」ではなく「壊れた」天秤があって計測結果は常にランダム (= たまたま正しい計測結果と一致する可能性あり)、天秤が 3 台あってどれが壊れているかは見分けが付かない、というものです。
https://tkido.com/blog/337.html
面白いのは、この壊れた天秤パズルのページに載っている解法はそのまま嘘つき天秤にも使えることです。あいにく逆はできないようです。
おはようございます、途中で寝ずに解きました…w。行列まで行かずに正解貰ったのがちょっと心苦しいです。これが9個だったら…とは少し思ったんですけれど。
ともあれ楽しく取り組める問題でした。ありがとうございました。
「はてな」には私が途中で寝てしまった場合分けで解いた人がいましたか。ｗ
そんな複雑な分け方をしていかなくても、3×3の行列で考えればいいというのはとてもエレガントでいいですね。
しかし、何人がその発想まで辿り着けるかが気になる所です。