問題

２０１７年日本数学オリンピック予選（公財）数学オリンピック財団

問題７、激ムズ。いったいどんな人がこの問題できるのだろう。まず、問題の意味を理解するだけで１０分はかかる。どんな問題なのかというと、

1,2,…,1000の並べ替えa_1,a_2,…,a_{1000}
が良い並べ方とは,次を満たすこととする：
１０００以下の正の整数m,nに対し,nがmの倍数ならばa_nはa_mの倍数である。
このとき、次の条件をみたす最小の整数kを求めよ.
条件：b_k \ne kを満たすよい並べ替えb_1,b_2,…,b_{1000}が存在する.

問題のコメント

まず、1000以下の整数と範囲がめちゃくちゃ広いです。もう、1000ぐらいまでは素因数分解を余裕でできなければ解けないです。計算量も半端ないです。100以下の整数だったとしてもかなりの計算量です。計算機持ち込み可能でも太刀打ちできません（私には)。

問題文には、倍数を使って書かれていますが、約数と読み替えたほうがわかりやすいと思います。つまり、「nがmの倍数ならばa_nはa_mの倍数である。」は、
「mがnの約数ならばa_mはa_nの約数である。」。
読み替えたところで、そんなに簡単になるわけじゃないですが、数字の絞り込みがしやすいかと。

さて、問題の主役となる、「よい並べ替え」について。「そんなよい並べ替えは存在するのか？」そこからして疑問ですが、小さな数で試してみます。つまり、よい並べ替えの例を作ってみます。この時に、倍数を約数に置き換えたほうが数字が発散しにくいかな？と思うのですが、そこは個人差でしょうか。

小さい順に並べた場合もよい並べ替えの一例です。この並べ方を自明なよい並べ方と呼ぶことにします。問題は自明でないよい並べ方を見つけよということになります。

一番な簡単な例は、3以下の整数で並べ替え(1,3,2)
の場合です。約数がないのでよい並べ方であることの確認も簡単です。
k=2でb_k \ne k
も満たしています。

もうちょっと数字が多い例では、(1,2,3,4,7,6,5)
こういうのが、7以下の整数でのよい並べ方の例となります。

逆によい並べ替えで<ない>例は7以下の整数の並べ替えで示すと、
7,6,5,4,3,2,1
や1,4,3,2,7,6,5
など、たくさんあります。

念のために上記がよい並べ替えでないことを確認してみます。
まず、a_1=7,a_2=6,a_3=5,a_4=4,a_5=3,a_6=2,a_7=1
について、4は２の倍数ですが、a_4=4
はa_2=6の倍数でありません。

次の例、a_1=1,a_2=4,a_3=3,a_4=2,a_5=7,a_6=6,a_7=5
について、6は2の倍数ですが、a_6=6
はa_2=4の倍数でありません。

ここまで、問題の意味を解きほぐすだけでも、かなりの時間を要しました。

考え方

さて、いよいよ問題にとりかかります。

1000までの自然数を並べ替えるパターンは、1000!もあり膨大です。

そこで、よい並べ替えがあったとして、ある適当に選んだ数(例えば素数)がどこに入れるかを考えます。

（１）まず、1がどこに入るかです。

これば、1番目以外には入りようがないです。それは、1の約数が1しかないからです。a_1=1はよい並べ方で確定なのです。

（２）次に、素数がどこにくるか考えます。

素数は約数が２個しなく、１番目は１が鎮座していますから、素数が入れるのは素数番目しかありません。

（３）合成数について考えます。

約数の条件から次の関係がわかります。

a_{st}=a_{s}a_{t}

そうです、よい並べ替えとは乗法的であるです。このことにすぐ気がついた人は、天才的なひらめきの持ち主だと思います。問題文の並べ替えに引きづられてしまうと、この事実に気が付きにくいでしょう。私も、かなり遠回りをしてこの事に気が付きました。

乗法的であるので、素数pに対して、a_pが決まっていれば、合成数はそれを素因数分解すれば、どの位置に入るか自動的にわかります。

（４）並べ替えの条件を言い換える。

例えば、10以下の整数でよい並べ替えを調べるとわかりますが、素数と素数を交換しただけでは、並べ替えができないことがわかります。

例えば、5以下の整数でよい並べ替えを作ろうとおもって、素数2と3を入れ替えると、
(1,3,2,9,5)
となってしまい、4が9に変わってこれは5以下の数の並べ替えではなくなってしまいます。

並べ替えが成立するための条件として、並べ替えた数をすべて掛けた数を考えます。この場合1000以下の数の並べ替えを考えていますから、\{a_i\})がよい並べ替えだとすると

\prod_{i=1}^{1000}a_i=1000!

でなければなりません。

なんと、この問題は、1000!の素因数分解が必要です。気絶しそうです。

（５）１０００！の素因数分解からよい並べ替えを考える。

もう書くのもくたびれるぐらい考えました。他にやり方があるんだろうか、こんなにも計算しないといけないのだろうか？

ここで、EXCELの登場です。すみません。素因数分解にEXCELを使わせていただきます。ギブアップです。

1000!=2^{φ(2)}3^{φ(3)}5^{φ(5)}\cdots 997^{φ(997)}

と素因数分解した素数pの指数をφ(p)で表すことにして、それぞれのφ(p)
を(EXCELを使って)求めます。

結論からいうと、よい並べ替えとは、φ(p)=φ(q),p \ne q
となる素数p,qを入れ替えればできるのです。このようなp,qが存在することはすぐにわかります。

たとえば、p=991,q=997。

φ(p)=φ(q),p \ne qとなる最小の素数pをなんとか求めます。

EXCEL使いました。しかも、500 \lt pの場合は、φ(p)=1
なので省略。

p φ(p) p φ(p) p φ(p) p φ(p)
2 994 101 9 233 4 383 2
3 498 103 9 239 4 389 2
5 249 107 9 241 4 397 2
7 164 109 9 251 3 401 2
11 98 113 8 257 3 409 2
13 81 127 7 263 3 419 2
17 61 131 7 269 3 421 2
19 54 137 7 271 3 431 2
23 44 139 7 277 3 433 2
29 35 149 6 281 3 439 2
31 33 151 6 283 3 443 2
37 27 157 6 293 3 449 2
41 24 163 6 307 3 457 2
43 23 167 5 311 3 461 2
47 21 173 5 313 3 463 2
53 18 179 5 317 3 467 2
59 16 181 5 331 3 479 2
61 16 191 5 337 2 487 2
67 14 193 5 347 2 491 2
71 14 197 5 349 2 499 2
73 13 199 5 353 2
79 12 211 4 359 2
83 12 223 4 367 2
89 11 227 4 373 2
97 10 229 4 379 2

φ(p)=φ(q),p \ne q
となる最小の素数p=59
が(Excelの助けをかりて)求まりました。

（６）求める解がk=59であること。

求めた59の最小性から、59より小さい素数pでは、φ(p)=φ(q),p \ne q
となる素数qがありません。つまり、9より小さい素数pは、入れ替えの候補になれません。

59より小さい合成数に対しては、59未満の素数pに対してa_p=p
であることから、やはり、

k \lt 59の場合、a_k=k
となってます。

したがって、求める答えは、59。

答え

k=59とすると、素数59と61の入れ替えでできるよい並べ替え

b_1,b_2,…,b_{1000}
は、b_{59}=61 \ne 59
となって題意を満たす。

コメント

考え方も難しいですが、計算に相当の時間を要する問題だと思います。

もっと、効率的なやり方があるのかもしれませんが、一般人に対しては、30以下の整数の並べ替えぐらいにして欲しいです。

ちなみに、３０以下の整数でのよい並べ方で非自明なもとして、11,13を入れ替えて作ったよい並べ替え、

(1,2,3,4,5,6,7,8,9,10,13,12,11,14,15,16,17,18,19,20,21,26,23,24,25,22,27,28,29,30)

があります。

[ad#foot]