JMO1990問1

\(N\)を\(1990\)桁の\(9\)の倍数とする.\(N\)の各桁の和を\(N_1,N_1\)の各桁の和を\(N_2,N_2\)の各桁の和を\(N_3\)とする.\(N_3\)を求めよ.

【思考・方針】

整数問題において,

  • \(\ mod\ \)を考える
  • 不等式的に範囲を考える

といったことは基本中の基本ですが今回は両方とも使います.まず,各桁の和といえば\(\ mod\ 9\ \)を考えるのは定石ですし,各桁の和をとる時点でだいぶ数が小さくなりますから,答えはそう大きくはない\(\ \)(というか,大きすぎると困る)\(\ \)と考えられますね.どちらも発想としては出やすいのではないのでしょうか.

STEP1\( \ \ mod\ 9\ \)で考える

各桁の和を取る操作は\(mod\ 9\)の世界では不変(つまり,元の数を\(9\)で割った余りと各桁の和を\(9\)で割った余りは等しい)なので,\(N\)が\(9\)の倍数であるから\(N_1\)も\(N_2\)も\(N_3\)も全て\(9\)の倍数です.

STEP2\( \ \ \)範囲を上から押さえる

\(N\)の各桁の和が最大となるのは\(9\)が\(1990\)個続くときでその時の各桁の和は

$$9\times 1990=17910\ \ \ \ \ ∴\ N_1\le17910$$

です.ということは,\(N_2\)はどんなに大きくても\(\ \)(\(N_1=9999\)のときを考えて)\(9\times4=36\)\(\ \)以下

さらに\(N_2\)は\(9\)の倍数でしたから,\(N_2=9,18,27,36\)にしぼりこめますが,いずれにしろ\(N_3=9\)となりますね!

IMO(国際数学オリンピック)にも類題が昔に出ておりますから,そちらでもう一度確認してみましょう.少し先程よりも手間はかかるもののすぐに解けるのではないでしょうか.

Q.\(\ N=4444^{4444}\)の各桁の和を\(A\),\(A\)の各桁の和を\(B\),\(B\)の各桁の和を\(C\)とする.\(C\)を求めよ.

(IMO1975年問4)

(注)\(4\)が並んだ不吉な問題だなと思いましたが,冷静に考えたら,開催国のブルガリアには\(4\)が不吉という文化はないのではということに気が付きました.

【略解】

まずは\(\ mod\ 9\ \)を調べましょう.先ほどの議論同様,\(N,A,B,C\)の\(9\)でわった余りは全て等しいです.

$$4444\equiv16\equiv-2\ \ (mod\ 9)$$

より,

$$4444^3\equiv(-2)^3\equiv-8\equiv1\ \ (mod\ 9)$$

ですから,

$$N\equiv4444^{1481\times3+1}\equiv(4444^3)^{1481}\times4444\equiv1^{1481}\times{(-2)}\equiv7\ \ (mod\ 9)$$

より,\(N,A,B,C\)を\(9\)でわった余りは\(7\)ですね.

次に不等式評価です.結構大雑把にしてしまいましょう.

\(N<10000^{4444}\)より,\(N\)は\(4444\times4=17776\)桁以下ですから,\(A\le9\times17776<180000\)ですから,\(8B\le45\)(\(←99999\)の各桁の和)

\(∴\ C\le12\)(←\(39\)の各桁の和)となり,\(C\)の\(9\)で割った余りは\(7\)ですから,\(C=7\)と確定します!

ここまで似た問題が出題されることは稀ですが,似たような考え方の問題というのはいろいろあったりするので,大昔のIMOの問題は比較的解きやすいものも多いですし,挑んでみるのも良いかもしれませんね.

コメントを残す

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