問題

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

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

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]