レピュニット数と剰余 (2022年JJMO予選 第9問)


 問題文の言い回しは少々回りくどいですが、要は2022や220など2のゾロ目に対してその1つが0に置き換わった正の整数全体に対し、その約数となり得る2022以下の正の整数の総数を求めれば良い事になります(例えば2022の正の約数である1, 2, 3, 6, 337, 674, 1011, 2022は全て条件を満たします)。

 とはいえ条件を満たす正の整数を1から順番に吟味することは時間的に不可能であり、何か効率的なアプローチが必要となります。 

解答

 ちょうど1つの位が0であり、その他の位は全て2であるような正の整数全体から成る集合をAと置く。Aの要素の約数となりうる正の整数nについて、以下の手順に従って考える。

① Aの要素は8の倍数でも25の倍数でもない

 正の整数が8の倍数となる為の必要十分条件は下3桁が8の倍数となる事である。ところがAの要素が取り得る下3桁は「222」「202」「220」「022」のいずれかであり、いずれも8では割り切れない。従ってAの要素で8の倍数となるものは存在しない。

 同様に正の整数が25の倍数である事の必要十分条件は下2桁が25の倍数となる事である。ところがAの要素が取り得る下2桁は「22」「20」「02」のいずれかであり、いずれも25では割り切れない。従ってAの要素で25の倍数となるものは存在しない。

 従ってnが8の倍数または25の倍数であるときnで割り切れるAの要素は存在しない。

② ①以外のnを割り切るAの要素が必ず存在する

 k = 1, 2, 3…に対して上k桁の数字が全て2であり1の位が0であるようなk+1桁の正の整数をAkとおくと(A1 = 20, A2 = 220, A3 = 2220, …)、各kに対してAkは集合Aの要素である。ここで各桁の数字が全て1であるk桁の自然数をBkとおくと(B1 = 1, B2 = 11, B3 = 111, …)、Ak及びBkの間には以下の関係式(1)が成立する。

Ak = 20 × Bk (1)

 式(1)よりAkは常に20の倍数であるので、4及び5で割り切ることが出来る。次に自然数Bkに対して以下の補題Xを示す。

(補題X)
 2及び5と互いに素であるような任意の自然数mに対して、Bkがmの倍数となるようなkが必ず存在する。

(補題Xの証明)
 m+1個の自然数B1, B2, B3, …, Bm, Bm+1をmで割った余りは高々m通りである。従ってB1, B2, B3, …, Bm, Bm+1の中にはmで割った余りが互いに等しいペアが必ず存在し、これをBi, Bjと定める(1≦i<j≦m+1)。この時Bj – Bi = 10i×Bj-iである事に注意すると、以下の合同式(2)が成立する。

Bi ≡ Bj ⇔ Bj – Bi ≡ 0 ⇔ 10i×Bj-i ≡ 0 (mod m) (2)

 仮定よりmは2及び5と互いに素であるので、式(2)からBj-iはmの倍数である。従って任意の2及び5と互いに素であるmに対して、Bkがmの倍数となるような自然数kが確かに存在するので補題Xは示された。

 従って自然数nが2以下の非負整数a, 1以下の非負整数b、2及び5と互いに素である自然数mを用いて「n = 2a×5b×m」の形で与えられた場合、式(1)及び補題XからAkがnの倍数となるような自然数kが必ず存在する。

 以上より条件を満たすnは「8の倍数または25の倍数」を除いた自然数全体である。2022以下の自然数について8の倍数、25の倍数、200の倍数(8かつ25の倍数)の総数はそれぞれ252, 80, 10個であるので、求めるべき2022以下のnの総数は

2022-(252+80-10) = 1700個

コメント

 集合Aの要素は無数に存在しますが、下2桁及び下3桁に関してはこの限りではありません。そこで2や5の累乗に関する倍数判定法は自然数の下数桁に依存する事を利用して、8の倍数や25の倍数が条件を満たさない事を示すことが出来ます。

 ここまでは試験場でも何とかなる可能性はありますが、後半部分のレピュニット(各桁が1である自然数)に関する議論は非常に難易度が高く、時間内に論証できる人はごく一握りでしょう。ちなみに「m+1個のレピュニットの中にmで割った余りが等しいペアが存在する」の部分は鳩の巣原理と呼ばれており、数オリや難関大入試などではごく稀に登場します。

 本問は「合否を分ける1問」より一段階上の難易度と思われます。とはいえ後半部分の議論が不十分であっても前半部分の議論から答えを推測する事は可能であり、仮に正答を得られれば他の受験生に差をつける事が出来たでしょう。

 

 

投稿者: matsubushi

趣味で数学など

コメントを残す

%d人のブロガーが「いいね」をつけました。