JMO予選2019問11

答え\(\cdots\)25

【分析】

かなりの難問です。なかなか時間内でできた人は少ないのではないでしょうか?\(2019^3\)で実験するのは大変なので小さい数(例えば\(3^3\)など)でいくつか計算して規則性が見抜けるかがポイントです。

\(3^3\)のときの始め3つだけを表で示しましたが反対称性(?)を見つけることができたでしょうか?

実はよーく眺めると図のように真ん中の13と14の間でほぼ反対称になっていることが分かります。この性質がこの問題を解く大きな鍵になります。まずは、なぜこのような性質が成り立つのかの証明から始めましょう。

【略解】

まず、\(2019^3\)で上で述べた性質を示す。簡単のために整数\(a\)に対して\([a]\)で\(a\)を\(2019^3\)で割った余りとします。また、めんどうなので\(k=1\)のときは途中まで議論しないことにする。

\((i)[km]=0\)のとき

このとき\((mod\ 2019^3)\)を考えると\([k(2019^3-m)]=0\)が成り立つ。

\((ii)[km]>m\)のとき

$$[km]+[k(2019^3-m)]=2019^3$$だから

$$[k(2019^3-m)]=2019^3-[km]<2019^3-m$$が成り立つ。

\((iii)[km]<m\)かつ\([km]\not=0\)のとき

同様に

$$[k(2019^3-m)]=2019^3-[km]>2019^3-m$$が成り立つ。

\((iv)[km]=m\)のとき

$$[k(2019^3-m)]=2019^3-[km]=2019^3-m$$

これより、\([km]\not=0,m\)のときは\(m,2019^3-m\)の片方が条件を満たすとわかる。つまり、実は各\(k\)に対して\([km]=0,m\)を満たす\(m\)の数のみを数えればよいことがわかる。

よって、\([km]=m\)が

\begin{eqnarray}km&\equiv& m\ (mod\ 2019^3)\\ (k-1)m&\equiv& 0\ (mod\ 2019^3)\end{eqnarray}

に注意すると\(k\)と\(2019^3\)の最大公約数、\(k-1\)と\(2019^3\)の最大公約数の合計を考えればよい。

結局、\(2019^3=3^3\times 673^3\)と\(GCD(k,2019^3),GCD(k-1,2019^3)\)は互いに素であることに注意すると次の表の場合のみ考えればよく、

\(k=1\)のときも合わせて\(24+1=25\)通り

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です