裹〓β

Mr.ダンディ

序列がはっきりした16人のトーナメント戦と考え
1位が決まるまで　16-1＝15試合
途中で1位のものに負けた４人でトーナメントをして勝ち上がったものが　2位
となり
すべてで　15+3＝18　（試合）（回）と考えました。

　　 10月9日（木） 0:13:05　　　　42498

今年から高齢者

トーナメント方式で一番重いのを決めて（15回）、一番重いのに負けた4つ（3回）で二番目に重いのを決める。
書き込んだら、Mr.ダンディさんと同じでした。

　　 10月9日（木） 0:13:30　　　　42499

ベルク・カッツェ

トーナメントで一位を決め、二位の可能性があるのは一位の相手なのでその4つで再度トーナメント、と考えました。

時計見たら3分過ぎてて慌ててアクセス、出遅れなければあるいは・・・

　　 10月9日（木） 0:16:29　　　　42500

物理好き

トーナメント表を考えます。
最重
ー
↑　§
ーー
↑ § ↑ ↑
ーーーー
↑§↑↑↑↑↑↑
ーーーーーーーー
|§||||||||||||||
最
重
このトーナメントは15試合。
§まで進んで1位と戦った分銅のみ
2位になる権利がある。
§は4つ→あと3試合
15+3=18回

大阪府　　 10月9日（木） 0:25:28　　　　42501

ベルク・カッツェ

みなさん同じやり方のようですね。
同じ重さの分銅の中に一つだけ違う重さがあるならまとめて量れるんですが、全部違うと複数個まとめても仕方がないので、バラバラに量るしかないかなと。

　　 10月9日（木） 0:21:10　　　　42502

あめい

みなさんと全く同じです。
第一感(ほとんど当たらない)は、1対1なら1位が15回で決まるので最大15回、数個ずつのせることが可能ならもっと減らせる?だったのですが。

１～１６全部決めるには何回かかるのでしょう？総当たりの１２０回？
前回のみなさんの分析、(こちらは予想通り)わかる2割くらい、？8割くらいでしたがとてもおもしろかったです。

お馬崎　　 10月9日（木） 1:14:52　　　　42503

Mr.ダンディ

#42503　＞「１～１６全部決めるには何回かかるのでしょう？」
71回かな～？？
2ｎ個で　n(n+1)-1 回
(2ｎ+1)個で　n^2+2n(回）　となりましたが・・・？

〔後記〕考え方に勘違いがあり、上記の値は間違いであることが分かりました。
みなさん、スルーした下さい。

　　 10月9日（木） 9:28:36　　　　42504

ハラギャーテイ

おはようございます。認証頼りでした。

山口　　 10月9日（木） 6:10:33　　 HomePage:制御工学にチャレンジ　　42505

通りすがり

すべての順序を求めることは、要素の整列（ソート）問題に帰着します。
N 個の要素を整列するための比較回数 M は、以下を満足する必要があります。

　2^M >= N!

つまり、2 の M 乗は、N の階乗と等しいか大きくなければいけません（必要条件）。
ここで、ceil は切り上げを、log2 は 2 を底とするの対数を表す関数とすると、
M の最小値（下限）は、以下の式から求まります。

M = ceil(log2(N!))

しかし、現在までに、確認（証明）されている最小の比較回数を K とすると、
以下の表のようになっています。

N: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
-------------------------------------------------------------------
M: 0 1 3 5 7 10 13 16 19 22 26 29 33 37 41 45 49 53 57 62 66 70
K: 0 1 3 5 7 10 13 16 19 22 26 30 34 38 42 46 50 54 58 62 66 71

気づかれると思いますが、N が 12 ～ 19 と 22では、K = M + 1 になっています。

もっと詳しく知りたい方は、皆さんおなじみの数列辞典（OEIS）の
A036604 や A001768 あたりを見て下さい。

　　 10月9日（木） 6:38:53　　　　42506

あめい

#42504Mr.ダンディさん、#42506通りすがりさん
私の(自分からは考えようとはしないという)傲慢な好奇心にお答えいただきありがとうございます。
数列辞典の存在もこちらで初めて知った身としては、みなさんの常識とはかけ離れている部分の多いと思いますが、(おふたり以外のみなさんも)よろしくお願いします。

　　 10月9日（木） 8:27:04　　　　42507

Mr.ダンディ

私の#42504では
ｎ個のもの序列が決まっているときに、ｎ+1個目がどこに入るかで
それを中央のもの（偶数の場合2つ）と比較し、同じ側に属するものの小さい
ものから１つずつ比較して・・
と考えての式でしたが、1つずつ全てと比較する必要はなく
同じ側のもののなかで前半か後半か、さらに残りの前半か後半か・・と考えれば、
比較回数をもっと短縮できることが分かりました。
（お騒がせしました）
何故　#42506の　M = ceil(log2(N!))　の式になるのか　私にはすぐには難しそう・・

　　 10月9日（木） 10:49:20　　　　42508

まるケン

Googleってすごいね。
"A036604”を検索したら、トップに数列辞典（OEIS）がでたよ！

でもって、OEISで"yoshikawa"を検索すると、、、

算チャレってすごすぎるよ！！

ないしょ　　 10月9日（木） 11:33:20　　 MAIL:take4310@mobile.email.ne.jp HomePage:まるケンの部屋　　42509

あめい

　　 10月9日（木） 11:48:11　　　　42510

uchinyan

はい，こんにちは。さて，今回の問題は．．．
うーむ，今回も前回みたいなことはないだろうな，とちょっとおっかなびっくり，という感じで解きました。
しかも，最初はどう考えたらいいか手がかりがピンと来なかったのですが，最も重い重りならバイナリサーチだよな，と気付き，
その後は比較的容易に解けました。こんな感じで。

２番目に重い重りを見つけるわけですが，そのためには，まず，基準となる最も重い重りを見つける必要があります。
まず，16 個を適当に 2 個ずつの 8 組に分け，各組で重さを比較し，重い方の 8 個を選びます。これには 8 回。
次に，選んだ 8 個を適当に 2 個ずつの 4 組に分け，各組で重さを比較し，重い方の 4 個を選びます。これには 4 回。
さらに，選んだ 4 個を適当に 2 個ずつの 2 組に分けま，各組で重さを比較し，重い方の 2 個を選びます。これには 2 回。
そして，選んだ 2 個の重さを比較し，重い方の 1 個を選びます。これには 1 回。
この最後に残ったものは，常に重い方同士を比較してきたので，最初の 16 個の中で最も重い重りです。
ここまでで，8 + 4 + 2 + 1 = 15 回。
求める重りは２番目に重い重りなので，この最も重い重りと比較して軽かった 4 個の中にあるはずです。
何故ならば，これら 4 個以外の重りはこれら 4 個のいずれかと比較してより軽かったからです。
そこで，これら 4 個の中で最も重い重りを見つければ，それが２番目に重い重りになります。
これは同様にして，2 + 1 = 3 回。
結局，２番目に重い重りを見つけるには，15 + 3 = 18 回，が必要です。

．．．と思いますが。最小性は大丈夫なのかな。
多分，最初に書いたように，２番目に重い重りを見つけるには基準となる最も重い重りを見つける必要があると思うので，
大丈夫だろうと思うのですが。

ネコの住む家　　 10月9日（木） 17:34:39　　　　42511

Halt0

#42508 Mr.ダンディさん
1回の比較につき, どちらが重いかについて2通りの可能性があるので,
M回比較したとき, 全比較結果のパターンとして考えられるものは2^M通り
一方, 分銅の重さの順序として考えられるものはN!通り
2^M通りの結果を用いて, N!通りの結果を全て区別するためには 2^M ≧ N でなくてはならない. よって M ≧ ceil(log_2(N!)). という感じかと思います.

#42511 uchinyanさん
私も不安でしたが, 一般の n の場合に最小の評価回数が n+ceil(log_2(n))-2 (ceil は切り上げ)であることが証明できるっぽいです. ちゃんと読んでないですが↓
http://math.stackexchange.com/questions/1601/lower-bound-for-finding-second-largest-element

　　 10月9日（木） 12:09:30　　　　42512

uchinyan

掲示板を読みました。

今回は，皆さん，同じ考え方で，
まず一番重い重りをトーナメント方式で決め，
次に一番重い重りと直接に比較して軽かった重り同士においてトーナメント方式で一番重い重りを決める，
という考え方のようですね。
最小性の明確な議論はないですが，多分，
２番目に重い重りを見つけるには基準となる最も重い重りを見つける必要がある，
ということで大丈夫なのでしょう。

なお，すべての順番を決めるのは整列問題で，アルゴリズム論では有名な話で，プログラムを勉強した人ならばご存知でしょう。
答えは，#42506，#42512にあるように，バイナリソートです。
もっとも，これを何の予備知識もなしに独力で見つけるのは，それなりに大変だと思います。

その後，最小性に関しては，#42512のリンク先で議論されているらしい，との報告がありました。
Halt0さん，紹介をありがとうございます。

ネコの住む家　　 10月9日（木） 12:30:22　　　　42513

baLLjugglermoka

一番重いのが決まれば、２番目も同時に決まると思い込んでいました。

　　 10月9日（木） 13:08:49　　　　42514

baLLjugglermoka

今週の問題と全く同じ計算がありました。
http://www.nii.ac.jp/userdata/shimin/documents/H22/100714_2ndlec.pdf

　　 10月9日（木） 13:16:27　　　　42515

Mr.ダンディ

#42512 Halt0さん　有り難うございます。
なるほど、そういうことから　
2^M ≧ N がいえたのち、 M ≧ ceil(log_2(N!)). M ≧ ceil(log_2(N!)). となるのですね。
（「漸化式のようなものがつくれないか」ばかりを考えておりました）

　　 10月9日（木） 21:07:13　　　　42516

ましゃ

トーナメント方式で解きました。

　　 10月9日（木） 16:41:12　　　　42517

スモークマン

16回でダメな理由がわかりません...
まず、８個ずつに分けて、それぞれの組で一番重い重りを決めるには、７回ずつだから、2*7=14回。それをAとBとして、それらを比べたとき(15回目)Bが重かったとするとそれが１番重い。
軽かった方の重りAと、重かった重りBの組の２番目に重かった重りCを比べれば(16回目)、AがCより重ければAが２番目に重く、CがAより重ければCが２番目に重いと分かると思うのですが？
どこかおかしいのかなぁ ^^;...

別のPCからエントリーしてますOrz...

　　 10月9日（木） 20:03:22　　　　42518

Jママ

スモークマンさんへ

Bが含まれる8個の組で、Bと直接重さを比べた中に、
AやCよりも重たい分銅が含まれる可能性があるからではないでしょうか…？σ(^_^;)?

今回皆さんと同じ解法に行き着くまで
少し時間がかかってしまいました(^^;
面白い問題でした。

　　 10月9日（木） 20:51:19　　　　42519

スモークマン

Ｊママさんへ ^^
そうでしたわ ^^;
ありがとうございました Orz☆
そもそもCがBの組で2番目に重い事なんてわからないことに気付きました...

4個の4組から、3*4+3+3=18 と了解できましたぁ☆
楽しい問題でしたぁ♪

　　 10月9日（木） 21:29:13　　　　42520

mukku

なるほど１５＋３かぁ。。みんな頭いいなぁ

　　 10月9日（木） 22:24:31　　　　42521

大岡　敏幸

久しぶりに来ました。２位決定戦ですね。すでに書かれている方もおられるかもしれませんが、トーナメントでやりました。

１６チーム参加　　１位決定まで　　１５試合

準決勝には４チーム　　１位は決まっているので、残り３チームで２位を決定　　３試合

よって、１５＋３＝１８　　算数っぽくできたかな？　っと思っています（＾＾；

石川県　　 10月11日（土） 10:41:52　　　　42522

ばち丸

まさかと思ったら通っちゃった。分銅に1、・・・、16と番号を振り
はかりに乗せる組み合わせを（左側,右側）と書くことにすると
（1,2),・・・,(1,16)で2～16のうち一番重いのW1と2番目W2を出し、1とW1、W2で2個ずつ乗せて比べる。

大岡敏幸さん
納得です。気が付きませんでした。脱帽。↓。

　　 10月12日（日） 7:53:05　　 MAIL:hbmath1965@yahoo.co.jp 　　42523

Mr.ダンディ

大岡様#42522
優勝したチームをAとすると、準決勝でAと違うブロックの2チームのうち負けた方は２位になることはあり得ません。
このようにAと当たる前に負けたチームが２位になることはあり得ないので、Aと当たって負けたチーム（4チーム）
のなかでトーナメントをして２位を決めることになるのではないでしょうか？

　　 10月12日（日） 13:38:58　　　　42524

おすまん

前回は、まったく歯が立たず、今回もネットで調べてやっとこさ…orz
やはり常連さんには遠く及びません…（涙）

somewhere in the world　　 10月12日（日） 18:13:06　　　　42525

物理好き

約70%の方がトーナメントで解いているんですね。
私も解法がかぶるとは思いましたが、ここまでかぶるとは思いませんでした。

大阪府　　 10月12日（日） 20:15:48　　　　42526

スモークマン

#42524 Mr.ダンディさん
So do I ^^
トーナメント方式の発想は秀逸ですね☆
PC復活 ^^

金即是空 ^^;v　　 10月13日（月） 0:22:48　　　　42527

中野雄太

まず一位を決めるために最も公平なトーナメント戦を行い15回。
そして、その一位以外には負けていない4個でトーナメント戦を行い3回。
計18回

　　 10月13日（月） 18:09:27　　　　42528

中野雄太

まず一位を決めるために最も公平なトーナメント戦を行い15回。
そして、その一位以外には負けていない4個でトーナメント戦を行い3回。
計18回

　　 10月13日（月） 18:10:07　　　　42529

ベルク・カッツェ

＞ばち丸さん
上皿天秤は天秤ばかりの一種ですが、同じ重さかどうかを調べることはできても、どれだけ重いかは分かりません。どちらが重いかが分かるだけです。

　　 10月14日（火） 1:50:41　　　　42530

だいすけ

最低何回、なので、めっちゃ運の良い時は何回でできるかっていう問題かと思っちゃいました。

　　 10月14日（火） 21:39:25　　　　42531

大岡　敏幸

#42524 Mr.ダンディ様
ご指摘、ありがとうございます。重い順位　１・２・３・４とすると

準決勝が

1 vs 2 3 vs 4 になる可能性もあるので、決勝が 1 vs 2　になるとは限りません。１位を決めてからこの２・３・４で２位を決めますので、３チームによるリーグ戦を行います。

よって、１位を決めてから３試合追加で　　１５＋３＝１８　　　と導きました。少し周りくどい説明になりましたが、このような考えで投稿させて頂きました。　ご納得頂けたでしょうか。

#42523 ぱち丸様
賛同、感謝です。

石川県　　 10月14日（火） 23:13:43　　　　42532

ベルク・カッツェ

＞大岡　敏幸さん
トーナメントで1位が決まった段階で、2位の可能性があるのは4チームです。
一回戦から決勝までの、優勝チームの対戦相手となった4チームはすべて、優勝チームにしか負けていないので2位の可能性があります。他のチームは優勝チーム以外、つまり1位でない相手に負けていますので、2位の可能性はありません。
そしてその4チームでトーナメントを行うことで2位が確定します。

なお、2位の可能性があるチームが3チームだった場合、総当りをする必要はなく、2試合だけで充分になります。

2位と言うより2番目に強いチームと言ったほうが適切かも知れませんね。

　　 10月15日（水） 0:13:03　　　　42533

ベルク・カッツェ

ちょっと冗長でしたかね・・・分かりやすく説明するって難しい。

　　 10月15日（水） 0:17:14　　　　42534

Mr.ダンディ

大岡　敏幸様　#42532で書かれてあるように考えておられるのであろうと思ってはいました。
ベルク・カッツェ様の#42533 に付け加えて
2番目に重いものが優勝したものと１回戦や、２回戦で当たることもあるので、準決勝に残った（優勝したもの以外の）
3チームに２番目に重いものが残っているという保証はない。というのが私の言わんとするところでした。

　　 10月15日（水） 0:42:33　　　　42536