解3(1)-2016年京都大学特色入試の類題の解答

どうも．

としなかです．

今回の解説はとても長いです．

ですので，小問ごとに解説を投稿しようと思います．

というわけで，早速問3の解説を始めましょう．

皆さんは解けたでしょうか？

かなり難しかったでしょう．

実際の入試に出題されたら，この大問の平均点は1/10になるでしょうね．（笑）

特色入試では誘導があったので，恐らく6/18くらいは平均点があったと思いますが……（数学好きの猛者の平均点で6/18はあまりにも低いけど）

今回は(1)の解説です．

(2),(3)に比べて幾分か簡単ではありますが，それでもかなり難しかったはずです．

(1)は難度Cです．

それでは解説を始めましょう．

適当なa,nで実験してみて気づいたでしょうか？

まずはa=5,n=5のときについて考えてみましょう．

下のような並びのとき，重複度5になります．（重複度とは，回転して同じ並べ方になるようなものの総数）

実際に，上の並びを回転して同じになるものは以下の４つがあります．

また，次の並びは重複度1です．

他の場合も考えたらわかりますが，a=5,n=5のときは重複度1のものと重複度5のものしかありません．

それに対して，a=5,n=6のときについて考えてみましょう．

このとき，重複度1のものと重複度6の並べ方も存在しますが，次の並びは重複度3になります．

実際に，上の並びと回転して同じになるものは以下の２つがあります．

さて……

n=5のときは重複度は1と重複度5の２つしかありませんが，n=6のときは重複度1と重複度6以外にも重複度3が存在します．

その違いはいったい何でしょうか……？

それはnが素数であるか否かであります．

dをnの約数とすると，重複度dとなる並びが存在します．

すなわち，nが素数のとき，重複度は1とnしか存在しません．

これを指針に解答しましょう．

解答に入る前に，１つ補題を示しておきましょう．

★証明★

まず，m,2m,...,pmのそれぞれをpで割った余りが異なることを示す．

次の式を満たす異なる整数a,bが存在すると仮定する．

このとき，式変形をすると次のようになる．

mはpの倍数ではないので，

となり，1≤a<b≤pであることから，a=bとなる．

よって，m,2m,...,pmのそれぞれをpで割った余りは異なる．

m,2m,...,pmはp個の整数であり，pで割った余りは0～p-1のp種類あるので，任意の整数n' (0≤n'≤p-1)に対してkm≡n'となる整数k (1≤k≤p)が存在する．よって，題意は示された．

★★★★

問3(1)を解く際にこの補題が必要になります．

では，以下解答．

★解答★

ある１枚のカードに書かれている数字をx(1)とし，それから左回りにx(2),x(3),...,x(n)とする．

左にm個回転して同じ配列になるようなものを考える．ただし，1≤m<nである．

このとき，次の式が成り立つ．

このとき，x(1+m)を左にm個回転させたものx(1+2m)もx(1+m)と等しくなるので，x(1)=x(1+m)=x(1+2m)=...となる．

ここで，先ほどの補題より1+km≡0 (mod n)となるkが存在するので，x(1)=x(1+km)=x(n)となる．

よって，x(1)=x(n)である．

同様にして，任意のi=1,2,...,n-1についてx(i)=x(n)となる．

すなわち，重複度nでない並び方は重複度1しか存在しない．

重複度1の並び方はa通りしかない．

以上より，求める場合の数は，

である．

★★★★

これで(1)は求まりました．

(1)でこのボリュームって……と萎えてしまいそうですが，引き続き(2)の解説もご覧ください．