京大特色入試総人理系1番
$n$ を正の整数とする．表に○か×が描かれた $n$ 枚のカードが裏を上にして横一列に置かれており，カードには左端から順に $1,2,\cdots,n$ と番号が振られている．0以上 $n$ 以下のある整数 $m$ に対し，左から $m$ 枚が○であり残りが×であることは分かっているが，$m$ の値は分かっていないとする．例えば $m=0$ なら全てのカードは×である．×が高々2回現れるまでカードを１枚ずつ裏返すことにより $m$ の値を知る方法を考える．
$n=3$のときには，「最初に番号2のカードを裏返し，それが○なら次に番号3のカードを，×なら番号1のカードを裏返す｣という方法により，どのような場合でも確実に $m$ の値を知ることができる．このような，それまでに裏返したカードから得られた情報に基づいて次に裏返すカードを決めるような裏返す順番の決め方で，×が高々2回現れるまで裏返すことにより，どのような場合でも確実に $m$ の値を知ることができるものを，大きさ $n$ の問題を解く手順と呼ぶことにする．上記の手順を図1のように表すことにする．また，図2は大きさ3の問題を解く手順の別の例である．
それぞれの手順において，裏返す必要のある回数の最大値をその手順の効率と呼ぶことにする，図1の手順の効率は2であり，図2の手順の効率は3である．大きさ $n$ の問題を解く手順の効率の最小値を $P(n)$ とおく．
問1 $P(n+1)\leqq P(n)+1$ であることを示せ．
問2 $n< n'$ ならば $P(n)\leqq P(n')$ であることを示せ．
間3 $n$ を大きくすると，$P(n)$ はいくらでも大きな値をとることを示せ．
問1〜問3と $P(1)=1$ より，1以上の整数 $p$ に対し，$P(n)=p$ となる整数 $n$ のうち最大のものが存在することがわかる．このような $n$ を$N(p)$ とおく．
問4 $N(1)$ および $N(2)$ を求めよ．
問5 $p\geqq 2$ のとき，$N(p)$ を $p$ と $N(p-1)$ で表せ．
問6 大きさ10の問題を解く手順のうち，効率が $P(10)$ であるものの例を１つ，図で表せ．