天秤でおもさを量る問題です

質問

どなたか教えていただけないでしょうか？

問題は、

８個の異なる分銅があります。
天秤はかりを用いて、この分銅の中で１番目と２番目に重い分銅を
なるだけ天秤を使わないで（つまり少ない回数で）見つけてください。

というものです。

自分の見つけた回答は、以下のようなものでした。

８個のトーナメント戦を行う。これで７回天秤を使う。
次に準優勝者（１人目）と、優勝者が対戦していないブロックの準決勝進出者（２人目、３人目）で
トーナメントを行う。これで２回天秤を使う。
７＋２で合計９回。

というものです。

ところが知人にこの解を見せると、

「８回以下では出来ない」という証明がなされていない。

といわれ、なるほど不完全な回答だなと思いました。

どなたか証明を知っている方が今いたら教えていただけないでしょうか？
そしてもうひとつ。
上記の「９回」は本当に正しいのでしょうか？

よろしくお願いします。

ついでにもうひとつ。
この種の問題の一般理論のようなものがもしあればそれも教えていただけないでしょうか？

回答No.3

stomachman · ベストアンサー

一対比較で１位を決めるのにはn-1回の比較が必要かつ十分である（∵トーナメントをやれば，比較を1回やる度に「こいつは１位ではない」と証明される分銅が1個だけ生じるから．トーナメントの組み方は関係ありません）．以上が「一般理論」でしょう．

　さて2位を決めるのには，「トーナメントにおいて，最終的に１位になった分銅と直接対決して負けて退場したやつ」すべての間で比較が必要になります．もちろん，トーナメントの組み方によって，必要な比較の数は異なります．
　たとえば「たまたま」分銅1は他の分銅と総当たりで勝負する（つまり，他の分銅はどれも1回だけ勝負し，どの勝負でも相手は分銅１である）というトーナメントをやって，「たまたま」分銅1が優勝した，という場合なら，残り全部の分銅の間でトーナメントをやり直すことになるから，あとn-2回の比較が必要です．
　あるいは「たまたま」分銅8の初戦は決勝戦であって，「たまたま」分銅8が優勝した，という場合，2位を決めるのに比較は要りません．

　さらに，「一対比較ではない比較（３個以上の分銅を一度に天秤に掛ける）」ということが検討されていません．たとえば，「たまたま」分銅1が100kg, 分銅2が10kg, 分銅3～8がそれぞれ1g以下，という状況において，「たまたま」分銅1と残り全部とを比較すれば1位が決まり，さらに「たまたま」分銅2と分銅1以外の残り全部とを比較すれば2位が決まる．だから，（分銅が何個あろうと）2回の比較で判定可能である（「これが１位であれが２位だ」と証明できる）ような場合が確かに存在する訳です．

　かくて，問題の設定の曖昧さが関わって来ます，上記のような「たまたま」をどう扱うか，ご質問には明言されていないという事が，その曖昧さです．
　もちろん「そんなたまたまなんか，認める訳が無い！」というのがフツーの考えでしょう．が，だったら「x回以下ではできない（たまたまを除く）」という言明の，命題としての厳密な意味は何か，ということを改めて問わねばなりません．要するに，「たまたま」じゃない，とはどういうことか，というのがポイントです．
　で，実際，ご質問にある「回答」は，「x回以下ではできない（たまたまを除く）」を厳密化した命題（一通りだけとは限りません）のどれかにおいて，おそらく最良の回答になっているように思われます．それらの命題さえはっきりすれば，証明は多分難しくないでしょう．
　最終的に，その証明ができるような命題のうち，最も条件が緩いものを選んで，問題を言い直すことになると思います．

お礼

回答　ありがとうございました。

回答No.2

MagicianKuma

nの場合は、n-1+Ceil(log[2]n)-1になると思います。証明は私には難しい。
n-1は1番目を決定するのに必要な回数、この1番目に負けた人を集めてトーナメントを同様にやれば2番目が見つかる。1番目に負けた人の数は、最大では、log[2]nを切り上げた人数となる。

お礼

回答　ありがとうございました。

回答No.1

EFA15EL

重さは全て異なり、どれぐらい違うかも分からない、と。
それは確かにトーナメントでもするしか無さそうです。

これで７回は確定。
次の対戦は準優勝と優勝者が準優勝者以外に破った分銅（２つ）ですよね。
優勝者の１回戦の相手が２位の可能性もあるのですから。

というわけで、少々相手は違いますが９回に同意します。

証明問題じゃないならこれで良いんじゃないかなあ。

お礼

回答　ありがとうございます。