★ 第 5 回問題 ★


n2 以上の整数とする.
いまここに重さのわからない n 個のおもりがある.ただしどの 2 つのおもりも同じ重さではないとする. A君とB君は,天秤をつかってこれら n 個のおもりの重さの順序を決定しなければならない.
天秤の左右の皿には一つずつしかおもりを乗せることはできない.天秤の両皿におもりを乗せてどちらが重いか見ることを「操作」ということにする. まずはじめB君がこの作業をしていたが,すべての順序を決定する前にA君に交代することになった.
このときに,B君の調べたすべての操作の結果の記録(各々の操作でどの 2 つのおもりを比べ,どちらが重かったか)がA君に渡された.
A君がこれらの情報から, n 個のおもりの重さの順序として考えられるものが何通りあるか数えてみたところ,それは m 通りだった.
さらに,次の条件が成り立たないことがわかった:
うまくおもりを 2 つのグループ X, Y に分けると, X に属するどのおもりも, Y に属するどのおもりよりも重いことが, B君の残した記録のみからわかる.
k を,m ≦ 2k をみたす最小の整数とする.
A君がうまい方法をとれば必ず k 回以内の操作で重さの順序を特定できるといえるか.
いえる場合はその証明を,いえない場合はその反例とそれが反例になっていることの証明を示せ.
問題文に一部誤りがありましたので訂正しました( 7 月 2 日 13 時 30 分)

応募は締め切りました.

第 5 回問題解説・正解者発表へ/ 問題一覧へ /トップページへ ●6865
出題: 2006 年 7 月 1 日 (土) 19 時 00 分 00 秒
締切: 2006 年 7 月 15 日 (土) 23 時 30 分 00 秒
解説・正解者発表: 2006 年 8 月 1 日 (火) 19 時 30 分 00 秒
担当者: 栗林 司