|
2010
8/13
|
|
2006
10/7
|
見た目も大きさも同じ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 なのでできません。
しかし、適当に考えた割には本当に面白い問題でした。付き合っていただいた方々ありがとうございます。
|
2006
10/3
|
見た目も大きさも同じ8個の重りがあります。7個は重さも同じですが1つは他よりわずかに軽いニセモノです。天秤を使ってニセモノを確実に特定するには何回天秤を使う必要があるでしょう。ただしこの天秤はただの天秤ではなく嘘つき天秤で、1回だけ嘘をつく（載せたものとは何の関係もなく左右に傾いたり釣り合ったりする）可能性があります。
前の問題のコメント欄で話しているときに思いついた問題。思いついたばかりなので実は私もまだ答えを知らない。解答熱烈募集中。
とりあえず元ネタの有名な問題の解法を単純に拡張すれば5回でできることは確実。4回以下でできる方法があればその方法を見つけ、同時にさらにそれ以下の回数ではできないことの証明もつけられればパーフェクトだと思う。
10/5（木）追記
昨日の晩ようやく解けた。真面目にやり始めてから3時間以上もかかった。もちろん9割以上は先入観から全然間違った方向性を模索していた時間だが。
できてみるとこれ適当に作った割にはものすごい良問だ。昔からパズルやったり作ったりするの好きだけど、このレベルのは生涯に数個しか作れないと思う。
ヒント
問題は有名な金貨8枚の問題の単純な拡張だが、解答は元の問題の単純な拡張ではだめ。元の問題のエッセンスはもちろん使わなければならないが、単純な拡張でできたと思ったらほぼ確実に間違っている。
最初から元の問題より相当に難しいことを覚悟して、一から原理原則を踏まえて考えた方がたぶん早く解ける。
10/7（土）追記
なかなか解答が寄せられないのでポイント懸賞付きではてなに持ち込んでみました。少し前から問題を知ってた人はチャンスです。
木戸孝紀