2022 日本数学オリンピック予選 第９問 ヒント

問題

$${1, 2, . . . , 1000}$$ の並べ替え $${(p_1, p_2, . . . , p_{1000})}$$ であって, 任意の $${1}$$ 以上 $${999}$$ 以下の整数 $${i}$$ に対して, $${p_i}$$ が $${i}$$ の倍数であるようなものはいくつあるか.
公益財団法人　数学オリンピック財団

ヒント

1000 の移動先を考える。
移動できるのは、1000 の約数の位置である。

$$
\begin{array}{|c||c|c|c|c|}
\hline
       & 2^0 & 2^1 & 2^2 & 2^3 \\
\hline\hline
5^0 & 1 & 2 & 4 & 8 \\
\hline
5^1 & 5 & 10 & 20 & 40 \\
\hline
5^2 & 25 & 50 & 100 & 200 \\
\hline
5^3 & 125 & 250 & 500 & 1000 \\
\hline
\end{array}
$$

例えば、$${1000}$$ が $${50}$$ の位置に移動すると、追い出された $${50}$$ は $${1000}$$ または $${50}$$ の約数($${50}$$ を除く)の $${1, 2, 5, 10, 25}$$ の位置に移動する。よって、この場合の数は、
　　　1 + ($${1, 2, 5, 10, 25}$$ の場合の数の合計)
となる。

解説

$$
\begin{array}{|c||c|c|c|c|}
\hline
       & 2^0 & 2^1 & 2^2 & 2^3 \\
\hline\hline
5^0 & ① & ② & ③ & ④ \\
\hline
5^1 & ② & ⑤ & ⑥ & ⑦ \\
\hline
5^2 & ③ & ⑥ & ⑧ & ⑨ \\
\hline
5^3 & ④ & ⑦ & ⑨ & ⑩ \\
\hline
\end{array}
$$

上の表の ①, ②, ③, …… , ⑩ の順で場合の数を計算していく。

$${①=1}$$
$${②=1+①}$$
$${③=1+①+②}$$
$${④=1+①+②+③}$$
$${⑤=1+①+②×2}$$
$${⑥=1+①+②×2+③+⑤}$$
$${⑦=1+①+②×2+③+④+⑤+⑥}$$
$${⑧=1+①+⑤+(②+③+⑥)×2}$$
$${⑨=1+①+④+⑤+⑦+⑧+(②+③+⑥)×2}$$
$${⑩=1+①+⑤+⑧+(②+③+④+⑥+⑦+⑨)×2}$$

この計算結果は、次の表のようになる。

$$
\begin{array}{|c||c|c|c|c|}
\hline
       & 2^0 & 2^1 & 2^2 & 2^3 \\
\hline\hline
5^0 & 1 & 2 & 4 & 8 \\
\hline
5^1 & 2 & 6 & 16 & 40 \\
\hline
5^2 & 4 & 16 & 52 & 152 \\
\hline
5^3 & 8 & 40 & 152 & 504 \\
\hline
\end{array}
$$

よって、答えは $${504}$$ 個となる。