2012 山梨大学 工(コンピュータ理工学科)学部推薦MathJax

Mathematics

Examination

Test

Archives

2012 山梨大学 工(コンピュータ理工学科)学部推薦

易□ 並□ 難□

【1】

1 2 3 n

 上のように,数字 1 2 3 n の書かれた n 枚のカードがあります.このカードを並べてできるすべての順列に対して,となりあうカードの前後の位置の交換を何回か行うことによって,上のように, 1 から小さい順に n まで並ぶようにします.下に, n=3 のときの順列 2 3 1 に対して,交換方法と回数の例を示します.

例 方法1  2 3 1 2 1 3 1 2 3 (交換回数 2 回)

となりあう 3 1 1 3 に交換,交換してできた順列 2 1 3 でとなりあう 2 1 1 2 に交換,以上の 2 回の交換で 1 2 3 の順になります.

  方法2  2 3 1 3 2 1 3 1 2 1 3 2 1 2 3 (交換回数 4 回)

となりあう 2 3 3 2 に交換,交換してできた順列 3 2 1 でとなりあう 2 1 1 2 に交換,交換してできた順列 3 1 2 でとなりあう 3 1 1 3 に交換,交換してできた順列 1 3 2 でとなりあう 3 2 2 3 に交換,以上の 4 回の交換で 1 2 3 の順になります.

 すべての順列に対して,となりあうカードの交換で 1 から小さい順に n まで並ぶようにするための最小の交換回数が存在します.この最小の交換回数に関して,下の問1,問2,問3について,説明をしてください.

問1  n=3 のときの順列 2 3 1 を,となりあうカードの交換で 1 2 3 と並ぶようにするための最小の交換回数は 2 回となることを説明してください.

問2  n=3 のとき, 3 枚のカードでできるすべての順列の中で,となりあうカードの交換で 1 2 3 と並ぶようにするための最小の交換回数が,最大となる順列,および,その交換回数を求めてください.求め方の説明もしてください.

問3  n=4 のとき, 4 枚のカードでできるすべての順列の中で,となりあうカードの交換で 1 2 3 4 と並ぶようにするための最小の交換回数が,最大となる順列,および,その交換回数を求めてください.求め方の説明もしてください.

inserted by FC2 system