2017年入試問題研究に戻る京大特色入試総人理系1番解答
問1 $ n+1 $ 枚のカードのうち，1から $ n $ のカードの部分について，手順の効率 $ P(n) $ で裏返すとき， ×が現れれば， $ n+1 $ 枚のカードについても $ m $ が求まる． すべて◯なら， $ n+1 $ 番のカードを裏返すことで， $ m $ が求まる． よって， $ n+1 $ 枚のとき手順の効率 $ P(n)+1 $ で $ m $ が求まる．よってその最小値について， \[ P(n+1)\leqq P(n)+1 \] が成り立つ．
問2 $ n< n' $ のとき $ P(n) > P(n') $ とする．
$ n $ 枚のカードが置かれたその右に×を $ n'-n $ 枚裏返しておく．この $ n' $ 枚について， 手順の効率 $ P(n') $ で $ m $ が求まり，その結果 $ n $ 枚のときの $ m $ も求まる． これは $ P(n) $ が $ n $ 枚のときの手順の効率の最小値であることに反する． よって， $ n< n' $ ならば $ P(n)\leqq P(n') $ である．間3 $ P(n) $ 個のところに◯か×を並べる． すべて◯は1通り， ×が1つは $ P(n) $ 通り， ×が2つは最後が×なので， $ P(n)-1 $ 通りあり， あわせて $ 2P(n) $ 通りある． 図1では $ P(3)=2 $ なので，4通りである．
それに対して， $ m $ が $ 0\leqq m \leqq n $ のいずれかの値で定まり， 並べ方を変えることですべての値をとる．よって， $ 2P(n)\geqq n+1 $ が成り立ち， $ n $ を大きくすると， $ P(n) $ はいくらでも大きな値をとる．
問4 $ P(2)=2 $ なので1となる最大値は1である．よって $ N(1)=1 $ ． 上の例より $ P(3)=2 $ である．
$ P(4)=P(2)+1=3>P(3) $ となるので， $ N(2)=3 $ である．問5 $ N(p-1)+p $ 枚のカードがあるとする． このとき，左から $ p $ 枚目のカードを引く． それが×なら，1枚目から順に2枚目の×が出るまで引くことで，あわせて多くとも $ p $ 回の操作で $ m $ が分かる．
それが◯なら，引いたカードの右にある $ N(p-1) $ 枚のカードについて， $ p-1 $ 回の手順の効率で◯から×に変わる位置を求め， $ m $ を確定することができる．
したがって $ N(p)\geqq N(p-1)+p $ である．
$ N(p) $ 枚のカードを並べる． 左から $ p $ 枚目のカードを引く． それが○のとき，その右にある $ N(p)-p $ 枚のカードから $ p-1 $ 回の操作で $ m $ の位置を確定できる． したがって， $ N(p)-p \leqq N(p-1) $ である． あわせて $ N(p)=N(p-1)+p $ である． $ N(1)=1 $ なので， $ N(p)=\dfrac{p(p+1)}{2} $ となる．問6 \[ \begin{array}{rcr} 4◯→7◯→9◯→10◯&:&m=10\\ 4◯→7◯→9◯→10×&:&m=9\\ 4◯→7◯→9×→8◯&:&m=8\\ 4◯→7◯→9×→8×&:&m=7\\ 4◯→7×→5◯→6◯&:&m=6\\ 4◯→7×→5◯→6×&:&m=5\\ 4◯→7×→5×&:&m=4\\ 4×→1◯→2◯→3◯&:&m=3\\ 4×→1◯→2◯→3×&:&m=2\\ 4×→1◯→2×&:&m=1\\ 4×→1×&:&m=0\\ \end{array} \] より， $ P(10)\leqq 4 $ である．明らかに $ n=10 $ のとき3回では解けない． よって， $ P(10)= 4 $ である．