上皿天秤を３回使って

質問

ありがちな問題なのですが、

金塊が１２個あるがそのうち１個が偽物である。
上皿天秤を３回使ってどれが偽物かを判定したい。
ただし偽物が軽いか重いかはわからないものとする。

です。重いか軽いかわからないところで、私は「解なし」を答えにしたのですが、
解があればもちろん知りたいですし、なければないことを証明できないものでしょうか。
よろしくお願いします。

回答No.4

nagata · ベストアンサー

まず金塊にa,b,c,d,e,f,g,h,i,j,k,lと名前をつけます。
で、状態0から始めて以下の手順で天秤を使えば偽物が分かります。
----------------------------------------------
状態0：
天秤を使った回数0
偽物候補=
aで軽い,aで重い,bで軽い,bで重い,cで軽い,cで重い,
dで軽い,dで重い,eで軽い,eで重い,fで軽い,fで重い,
gで軽い,gで重い,hで軽い,hで重い,iで軽い,iで重い,
jで軽い,jで重い,kで軽い,kで重い,lで軽い,lで重い

(a,b,c,d)と(e,f,g,h) を比べる。
a,b,c,dが重い:状態1へ
e,f,g,hが重い:a,b,c,dとe,f,g,hの名前をそれぞれ入れ換えて状態1へ
吊合う:状態2へ
------------------------------------------------------
状態1：
天秤を使った回数1
偽物候補=
aで重い、bで重い、cで重い、dで重い
eで軽い、fで軽い、gで軽い、hで軽い

(a,b,e)と(c,d,f)を比べる
a,b,eが重い:状態3へ
c,d,fが重い:a,b,eとc,d,fの名前を入れ換えて状態3へ
吊合う：状態4へ
-------------------------------------------------
状態2：
天秤を使った回数1
偽物候補=
iで軽い,iで重い,jで軽い,jで重い,
kで軽い,kで重い,lで軽い,lで重い

(i)と(j)を比べる
iが重い:状態5へ
jが重い:iとjの名前を入れ換えて状態5へ
吊合う：状態6へ
------------------------------------------------------
状態3：
天秤を使った回数2
偽物候補=
aで重い、bで重い、fで軽い

(a)と(b)を比べる
aが重い：aが偽物
bが重い：bが偽物
吊合う：fが偽物
------------------------------------------------------
状態4：
天秤を使った回数2
偽物候補=
gで軽い、hで軽い

(g)と本物を比べる
gが重い：あり得ない
本物が重い：gが偽物
吊合う：hが偽物
-------------------------------------------------------
状態5：
天秤を使った回数2
偽物候補=
iで重い、jで軽い

(i)と本物を比べる
iが重い:iが偽物
本物が重い:あり得ない
吊合う：jが偽物
------------------------------------------------------
状態6：
天秤を使った回数2
偽物候補=
kで軽い,kで重い,lで軽い,lで重い

(k)と本物を比べる
kが重い:kが偽物
本物が重い:kが偽物
吊合う：lが偽物

お礼

ありがとうございました。
体系的に、そしてシステマチックに解くことができるとわかりすっきりしました。

ポイントは、勝手ながら今回書いて下さった量と個人的なわかりやすさで決めさせていただきます。

回答No.5

siegmund

ありがちな問題ですが，この問題とその拡張に関しましては
http://oshiete1.goo.ne.jp/kotaeru.php3?q=30706
が決定版と思います．
stomachman さんの業績が大きい．
私も多少寄与しています．

お礼

ＵＲＬ見てみました。
はっきり言ってすごいですね。
離散数学とか、計算量理論などを思い出してしまいました。
時間を見つけてじっくり分析してみます。

回答No.3

nozomi500

「ありがちな問題」ですので、過去の解答をご参考に。

参考URL：

http://oshiete1.goo.ne.jp/kotaeru.php3?q=89620

お礼

ありがとうございます。
検索するべきでした。

回答No.2

noname#1489

この問題には、ちゃんと解があります。ポイントは12個の金塊の載せ方と１～３回目の結果を総合的に判定することです。
説明がしやすいように12個の金塊に１～12まで番号をつけます。

１回目：左側に１～４、右側に５～８を載せます。
つりあった時の２回目：左側に８と９、右側に10と11を載せます。---------------------(a)
つりあわなかった時の２回目：左側に１と２と５、右側に３と４と６を載せます。------------(b)

(a)で２回目もつりあった時には、１～11は同じ重さであるから、左側に11、右側に12を載せれば、12が重いか軽いかがわかります。
(a)で２回目がつりあわなかった時には、左側に10、右側に11を載せます。これがつりあえば、１～８、10～11(12も)が同じ重さであり、２回目の天秤の傾き方で９が重いか軽いかがわかります。10と11がつりあわなかった時には、２回目の結果と合わせれば、10と11のどちらが重いか(または軽いか)が判定できます。

(b)で２回目がつりあった時には、左側に７、右側に８を載せれば、１回目の天秤の傾き方と合わせれば、７と８のどちらが重いか(または軽いか)が判定できます。
(b)で２回目がつりあわなかった時には、１回目と２回目の天秤の傾き方が同じ時は、左側に１、右側に２を載せます。１と２がつりあえば、１，２回目の結果から６が重い(または軽い)ことがわかり、つりあわなければ、１～３回目の傾き方から１または２が重い(または軽い)ことがわかります。
１回目と２回目の傾き方が逆の時は、左側に３、右側に４を載せます。３と４がつりあえば、１，２回目の結果から５が重い(または軽い)ことがわかり、つりあわなければ、１～３回目の傾き方から３または４が重い(または軽い)ことがわかります。

１～３回目、それぞれについて、つりあう場合、左側が下がる場合、右側が下がる場合に分けて回答すれば、わかりやすいかと思いますが、かなりの長文になりますので、このくらいで失礼いたします。もし、わからないような時は補足をお願いします。

お礼

ありがとうございます。
非常に説得される回答です。

しかし、これを中学生に宿題で出すとは．．．（私は大学生ですが）

回答No.1

hi-kun

以下のURLを参考にしてみては。
http://web2.incl.ne.jp/yaoki/nise_nn.htm
ページの一番下にある【寄せられた解答】から飛んでみてください。

参考URL：

http://web2.incl.ne.jp/yaoki/nise_nn.htm

お礼

ありがとうございます。
色々な人が取り組んでいるのですね。
ひょっとして有名問題だったのでしょうか