順列と論証２

2016年10月26日

１の続きです。

１．(東京大)
$N$ を正の整数とする． $2N$ 個の項からなる数列
$\{a_1,~a_2,~\cdots,~a_N,~b_1,~b_2,~\cdots,~b_N\}$
を　 $\{b_1,~a_1,~b_2,~a_2,~\cdots,~b_N,~a_N\}$
という数列に並び替える操作を「シャッフル」と呼ぶことにする．並び替えた数列は $b_1$ を初項とし， $b_i$ の次に $a_i$ ， $a_i$ の次に $b_{i+1}$ が来るようなものになる．また，数列 $\{1,~2,~\cdots,~2N\}$ をシャッフルしたときに得られる数列において，数 $k$ が現れる位置を $f(k)$ で表す．例えば $N=3$ のとき， $\{1,~2,~3,~4,~5,~6\}$ をシャッフルすると $\{4,~1,~5,~2,~6,~3\}$ となるので， $f(1)=2,~f(2)=4,~f(3)=6,~f(4)=1,~f(5)=3,~f(6)=5$ である．
(1) 数列 $\{1,~2,~3,~4,~5,~6,~7,~8\}$ を3回シャッフルしたときに得られる数列を求めよ．
(2) $1 \leqq k \leqq 2N$ を満たす任意の整数 $k$ に対し， $f(k)-2k$ は $2N+1$ で割り切れることを示せ．
(3) $n$ を正の整数とし， $N=2^{n-1}$ のときを考える．数列 $\{1,~2,~3,~\cdots,~ 2N\}$ を $2n$ 回シャッフルすると， $\{1,~2,~3,~\cdots,~2N\}$ に戻ることを証明せよ．

２．(鳥取大)
1から $n$ までの数が1つずつ書かれた $n$ 枚のカードを円周上に時計まわりに並べる．2が書かれたカードから始めて，時計まわりに1枚おきにカードを取り除く操作を続けていき，カードが最後の1枚になるまで円周上を何回でもまわる．そして残った1枚のカードに書かれた数を $f(n)$ とする．ただし，1枚おきに取り除く操作は，まだ円周上に残っているカードに対して行う．例えば， $n=9$ のときには，2, 4, 6, 8, 1, 5, 9, 7の数が書かれたカードが順に取り除かれるので $f(9)=3$ である．また， $n=10$ のときには，2, 4, 6, 8, 10, 3, 7, 1, 9の数が書かれたカードが取り除かれるので $f(10)=5$ である．このとき，次の問いに答えよ．ただし， $f(1)=1$ とする．
(1) 2から8までの $n$ に対して， $f(n)$ の値を求めよ．
(2) 自然数 $n$ に対して， $f(2n)=2f(n)-1,~f(2n+1)=2f(n)+1$ が成り立つことを示せ．
(3) 自然数 $n$ に対して， $f(2^n)=1$ が成り立つことを示せ．
(4) $f(2^{10}+2^9+\cdots+2+1)$ の値を求めよ．

３．(早稲田大)
円周上に $m$ 個の点 $\mbox{P}_1,~\mbox{P}_2,~\cdots,~\mbox{P}_m$ がこの順に配置され，各点 $\mbox{P}_i$ に1つの実数 $c_i$ が与えられている~ $(i=1,~2,~\cdots,~m)$ ．ただし $m \geqq 3$ とする．
さらに， $(c_1,~c_2,~\cdots,~c_m)$ は条件
(＊) 各点の値は，隣接する2点の値の和に等しい
を満たす．
(1) $m=3$ の場合に $(c_1,c_2,c_3)$ の値を求めよ．
(2) $c_1=a,~c_2=b$ とおくとき $c_7$ を $a,~b$ で表せ．ただし， $m \geqq 7$ とする．
(3) 条件(＊)を満たし，かつ $c_1 \ne 0$ となる $(c_1,c_2,~\cdots,c_m)$ が存在するのは $m$ がどのような自然数の場合か． $m$ が満たすべき必要十分条件を求め，その理由を簡単に述べよ．

コメント一覧

まだ、コメントがありません