院試の過去問

寝てる間に解法を思いついたのでメモ．

問

1000 個の数がある．
大きい順に並べたときに，1 〜 500 番目に入る数を 1 個，501 〜 1000 個目に入る数を 1 個取り出したい．
2 数を比較して大小関係を得る操作を最大 800 回行えるとき，どのようにすれば目的を果たせるか？

解

1000 個のうち無作為に 501 個以上取り出し，その最大値と最小値を探せば目的は果たせる．
まず，1000 個のうち無作為に 502 個を取り出し，2 個組 × 251 個に分割する．
次に，それぞれの 2 個組について大小を比較（比較 251 回）し，大きい方を「大集合」に，小さい方を「小集合」に追加する．ここで，502 個のうち最大値は必ず大集合に，最小値は必ず小集合に属しているはずである．
最後に，大集合の最大値を求め（比較 250 回），小集合の最小値を求め（比較 250 回）れば目的を果たせる．
（比較回数は合計 751 回）