ゴールデンな数学に挑戦（新年特別編）
2022年1月16日
当塾では，毎年生徒さん宛ての年賀状に数学のパズルや問題を載せていて，解けた生徒さんにはささやかながらお年玉を差し上げています^^
出題するのは，オリジナルのパズルだったり，その年に私が解いた問題で面白かったものをアレンジした問題などです。
今年は次の問題を出題しました：
例えば，$1234$ の場合
(1) $91\to 91+9+1=101$，$100\to 100+1=101$ のように「計算」の結果が同じ値になる２つの自然数の組があります。このような２つの自然数の組を他にも見つけましょう。
(2) 「計算」の結果が同じ値になる３つの自然数の組を見つけましょう。
(3) (2) の「３つ」の部分を４つ，５つ，…とどれだけ大きな数にしても，そのような自然数の組を見つけることができることを証明しなさい。
この問題は、2021年に私が解いた次の問題が元になっています：
出題するのは，オリジナルのパズルだったり，その年に私が解いた問題で面白かったものをアレンジした問題などです。
今年は次の問題を出題しました：
問題１
自然数に対し，その数にその数の各桁に現れる数をすべて加えるという「計算」をすることを考えます。例えば，$1234$ の場合
\begin{align*}
1234\,\,\to\,\, 1234+1+2+3+4=1244
\end{align*}
なので「計算」の結果は $1244$ です。(1) $91\to 91+9+1=101$，$100\to 100+1=101$ のように「計算」の結果が同じ値になる２つの自然数の組があります。このような２つの自然数の組を他にも見つけましょう。
(2) 「計算」の結果が同じ値になる３つの自然数の組を見つけましょう。
(3) (2) の「３つ」の部分を４つ，５つ，…とどれだけ大きな数にしても，そのような自然数の組を見つけることができることを証明しなさい。
問題２
自然数 $n$ を十進法で表したときの各桁の数の和を $S(n)$ とおく．このとき，
\begin{align*}
n_1+S(n_1)=n_2+S(n_2)=\cdots =n_{2002}+S(n_{2002})
\end{align*}
となる相異なる2002個の自然数 $n_1$，$n_2$，$\cdots$，$n_{2002}$ が存在することを示せ．
原題では「2002個」ですが，これはいくらでも大きくすることができます。
今にして思うのは，これは2022年の年賀状なので，(3)は次のような問題にすればよかったですね：
(3) 「計算」の結果が同じ値になる2022個の自然数の組を見つけましょう。
ちょっと後悔^^;原題は「JMO本選中盤レベル」らしいので，全学年向けの懸賞問題として出題するには難しすぎます^^; そこで(1)，(2)の小問を設けました。
小学生は，問題の意味が理解できるだけで十分スゴイと思うので(1)のみ正解でお年玉ゲットとしました^^
本問は「２つ」から「３つ」に上げるだけでかなり数の検索範囲を広げる必要があって，証明の本質に迫る考え方ができないと「３つ」ですら見つけることは困難です。なので中高生は(2)まで正解でお年玉ゲットとしました。もちろん，プログラムを書いて見つける方法などもOKです^^！
(3)はチャレンジ問題ということで…^^;
この記事では，問題１を詳しく解説していきたいと思います。
(1)の解説
問題の「感じ」をつかむためにもとりあえず実験してみましょう。その前に記号と用語を定義します。
非負整数 $n$ に対し，問題２と同様に $n$ を十進法で表したときの各位の数の和を $S(n)$ とします。そして「計算」の結果を
\begin{align*}f(n)=n+S(n)\end{align*}
と書くことにします。さらに，次の用語を定義します：
定義
$m$ を $2$ 以上の整数とする。$m$ 個の自然数の組 $n_1$，$n_2$，$\cdots$，$n_m$ が，互いに仲間であるとは，
\begin{align*}
f(n_1)=f(n_2)=\cdots =f(n_m)
\end{align*}
をみたすことと定義する。また，互いに仲間である $m$ 個の数の組 $n_1$，$n_2$，$\cdots$，$n_m$ を大きさ $\boldsymbol{m}$ のパーティと呼ぶことにする。
このように定義すると，$91$ と $100$ は仲間で，大きさ $2$ のパーティをなしています。
(1)の目標は「大きさ $2$ のパーティを他にも見つける」ということになります！
とりあえず，$n$ に小さい値を順に代入してみて様子を見ましょう：
\begin{align*}
f(0)&=0+0=0\\
f(1)&=1+1=2\\
f(2)&=2+2=4\\
f(3)&=3+3=6\\
f(4)&=4+4=8\\
f(5)&=5+5=10\\
f(6)&=6+6=12\\
f(7)&=7+7=14\\
f(8)&=8+8=16\\
f(9)&=9+9=18\\
f(10)&=10+1+0=11\\
f(11)&=11+1+1=13\\
f(12)&=12+1+2=15\\
f(13)&=13+1+3=17\\
f(14)&=14+1+4=19\\
f(15)&=15+1+5=21\\
f(16)&=16+1+6=23\\
f(17)&=17+1+7=25\\
f(18)&=18+1+8=27\\
f(19)&=19+1+9=29\\
f(20)&=20+2+0=22\\
f(21)&=21+2+1=24\\
f(22)&=22+2+2=26\\
f(23)&=23+2+3=28\\
& \qquad\vdots
\end{align*}
定義を考えれば分かることですが，$n$ の値が $1$ 増加するとき，$n$ の $1$ の位が $9$ 以外のときには，$n$ と $S(n)$ が $1$ ずつ増加して $f(n)$ の値は $2$ 増加します。そして $1$ の位が $9$ から $0$ になるときだけ $S(n)$ の値が減少し，$f(n)$ の値も減少します。
単調増加な数列では値が一致することはないので，$f(n)$ の値が減少したタイミングで値が「かぶる」のだろうと予想されます。
それでは次に，$f(n)$ の値が減少するときの減少幅を考えてみましょう。
$k$ を自然数として，$n$ が $1$ の位から $10^{k-1}$ の位まで $9$ が並んでいる数であるときを考えます。$a$ を $10^k$ の位の数とすると，
\begin{align*}
n=\ast\cdots\ast a\underbrace{99\cdots 99}_{\text{$k$ 個}}
\end{align*}
と表されます。このとき，
\begin{align*}
n+1=\ast\cdots\ast (a+1)\underbrace{00\cdots 00}_{\text{$k$ 個}}
\end{align*}
となるので，$f(n)$ から $f(n+1)$ になるときその値は，$k$ 個の $9$ が $0$ になるので $9k$ 減少し，$n$ と $a$ の値が $1$ ずつ増えることで $2$ 増加するので，$9k-2$ 減少すると分かります。上の「実験」で，$n$ の $1$ の位の数が $9$ から $0$ になるとき，$f(n)$ の値は確かに $7$ 減少しています。
$f(n)$ の値は，増加するときは $2$ ずつ増加するので，減少幅が $7$ だと奇偶がずれてしまい，その直後で値が一致することはありません。
それでは，下 $2$ 桁が $99$ のときはどうでしょう？
試しに，$n=99$ の周辺で実験してみましょう：
\begin{align*}
f(90)&=90+9+0=99\\
f(91)&=91+9+1=101\\
f(92)&=92+9+2=103\\
f(93)&=93+9+3=105\\
f(94)&=94+9+4=107\\
f(95)&=95+9+5=109\\
f(96)&=96+9+6=111\\
f(97)&=97+9+7=113\\
f(98)&=98+9+8=115\\
f(99)&=99+9+9=117\\
f(100)&=100+1+0+0=101=f(91)\\
f(101)&=101+1+0+1=103=f(92)\\
f(102)&=102+1+0+2=105=f(93)\\
f(103)&=103+1+0+3=107=f(94)\\
f(104)&=104+1+0+4=109=f(95)\\
f(105)&=105+1+0+5=111=f(96)\\
f(106)&=106+1+0+6=113=f(97)\\
f(107)&=107+1+0+7=115=f(98)\\
f(108)&=108+1+0+8=117=f(99)\\
f(109)&=109+1+0+9=119\\
f(110)&=110+1+1+0=112
\end{align*}
$f(99)\to f(100)$ のときは減少幅は $16$ であり偶数となるので，上の実験結果のように互いに仲間となる数の組が（複数）存在します。これで(1)は解決です！ $91$ と $100$ の他にも $92$ と $101$ など，９組の大きさ $2$ のパーティを見つけることができました！！
この節では，$f(n)$ の値の増減に注目し，具体的な解を見つけることに成功しました^^！
次の節では，$f(n)$ のグラフの様子に注目し，$f(n)$ の値の分布がもつある種の周期性のような性質を見出していきます。
(2)の解説
まず，$0\leqq n\leqq 110$ の範囲での $f(n)$ のグラフを見てみましょう：
グラフを見ると分かる通り，$0\leqq n\leqq 9$ の範囲で増加し，$n=10$ で値を下げて $10\leqq n\leqq 19$ の範囲で同様に増加しています。
式で書くと，
\begin{align*}
f(n+10)=n+10+S(n)+1=f(n)+11\quad (0\leqq n\leqq 89)
\end{align*}
です。このように $f(n)$ は「一定の値のずれがある周期性」をもっています。同様に，
\begin{align*}
f(n+100)=n+100+S(n)+1=f(n)+101\quad (0\leqq n\leqq 899)
\end{align*}
が成り立ちます。この性質を利用すると，$0\leqq n\leqq 100$ の範囲のグラフをずらしながら貼り合わせていって $n\geqq 100$ の範囲のグラフを書くことができます。$0\leqq n\leqq 1100$ のグラフは下の図のようになります：
$f(999)\to f(1000)$ のときは減少幅は $25$ ですが，この周辺で仲間となる２数（赤線で結んでいる）がたくさん存在します（見難いですが^^;）。
値を確認しておくと：
\begin{align*}
f(982)&=1001=f(1000)\\
f(983)&=1003=f(1001)\\
f(984)&=1005=f(1002)\\
f(985)&=1007=f(1003)\\
f(986)&=1009=f(1004)\\
f(987)&=1011=f(1005)\\
f(988)&=1013=f(1006)\\
f(989)&=1015=f(1007)\\
f(990)&=1008\\
f(991)&=1010\\
f(992)&=1012=f(1010)\\
f(993)&=1014=f(1011)\\
f(994)&=1016=f(1012)\\
f(995)&=1018=f(1013)\\
f(996)&=1020=f(1014)\\
f(997)&=1022=f(1015)\\
f(998)&=1024=f(1016)\\
f(999)&=1026=f(1017)
\end{align*}
ですが，残念ながらこの中には大きさ $3$ のパーティはありません。でも，$n$ が３桁から４桁に上がるときに減少幅 $25$ が登場したことで，これまでになかった $f(n)$ の値が一致するパターンが生じたと言えます。
そこで，私は次のように考えました：前節でみたように，$n$ の桁を大きくすれば位が上がったときの減少幅はいくらでも大きくできるので，２点での値が一致している $f(n)$ に第３の点での $f(n)$ の値が一致するように減少幅を調節してはどうか？
それを実行するために，大きな桁の数を扱いやすくするための記号を導入します。
自然数 $k$ と 非負整数 $j$ に対し，
\begin{align*}
M_{k,j}=\{(n+j\times 10^k,f(n+j\times 10^k))\mid 0\leqq n\leqq 10^k-1\}
\end{align*}
と定義します。例えば，
\begin{align*}
M_{1,0}=\{(0,\,0),\,(1,\,2),\,(2,\,4),\,(3,\,6),\,(4,\,8),\,(5,\,10),\,(6,\,12),\,(7,\,14),\,(8,\,16),\,(9,\,18)\}
\end{align*}
であり，これはグラフ１の左から10個の点に対応します。
\begin{align*}
M_{1,1}=\{(10,\,11),\,(11,\,13),\,(12,\,15),\,(13,\,17),\,(14,\,19),\,(15,\,21),\,(16,\,23),\,(17,\,25),\,(18,\,27),\,(19,\,29)\}
\end{align*}
であり，これは $M_{1,0}$ の次の10個の点に対応していますが，これは $M_{1,0}$ を右へ $10$，上へ $11$ 平行移動したものになっています。同様に，$M_{1,2}$，$M_{1,3}$，$\cdots$ も $M_{1,0}$ を平行移動したものになっていて，それらが斜めに10個積みあがって グラフ１の $0\leqq n\leqq 99$ の部分すなわち $M_{2,0}$ はできています。
グラフ２においても同様に，水色の長方形で示した部分の左から10個が順に $M_{2,0}$，$M_{2,1}$，$\cdots$，$M_{2,9}$ であり，各 $M_{2,1}$，$\cdots$，$M_{2,9}$ は $M_{2,0}$ を平行移動したものになっています。そしてそれら10個が斜めに積みあがって $M_{3,0}$ ができています。
このように，小さいブロックが積みあがって大きなブロックができるような，ある種の自己相似性のような性質は，桁がもっと大きくなっても成立します。
定義により，
\begin{align*}
M_{k+1,0}=M_{k,0}\cup M_{k,1}\cup \cdots \cup M_{k,9}=\textstyle\bigcup\limits_{j=0}^{9}M_{k,j}
\end{align*}
が成り立ちますが，さらに関数 $f(n)$ の性質として，
\begin{align*}
f(n+j\times 10^k)&=n+j\times 10^k+S(n)+j\\
&=f(n)+j(10^k+1)\quad (0\leqq n\leqq 10^k-1,\,j=1,\,2,\,\cdots,\,9)
\end{align*}
が成り立つので，各 $M_{k,j}\,(j=1,\,2,\,\ldots,\,9)$ は $M_{k,0}$ を平行移動したものであり，それらが斜めに10個積みあがって $M_{k+1,0}$ ができていることが分かります。これらの記号のもとで，大きさ $3$ のパーティを探して行きましょう。
$k\geqq 3$ とすると，$M_{k,0}$ の右から1000個の点の配置は $M_{3,0}$ を平行移動したものになっていて，例えば，
\begin{align*}
f(891)=f(900)=909
\end{align*}
の２点に対応する点
\begin{align*}
&(\underbrace{99\cdots 99}_{\text{$k-3$ 個}}891,\underbrace{99\cdots 99}_{\text{$k-3$ 個}}882+9k),\\
&(\underbrace{99\cdots 99}_{\text{$k-3$ 個}}900,\underbrace{99\cdots 99}_{\text{$k-3$ 個}}882+9k)
\end{align*}
を含みます。$M_{k,0}$ の右隣りにある $M_{k,1}$ の点の小さい方から９個は，
\begin{align*}
&(10\cdots 000,\,10\cdots 001),\\
&(10\cdots 001,\,10\cdots 003),\\
&(10\cdots 002,\,10\cdots 005),\\
&(10\cdots 003,\,10\cdots 007),\\
&(10\cdots 004,\,10\cdots 009),\\
&(10\cdots 005,\,10\cdots 011),\\
&(10\cdots 006,\,10\cdots 013),\\
&(10\cdots 007,\,10\cdots 015),\\
&(10\cdots 008,\,10\cdots 017)
\end{align*}
です（ただし，$0\cdots 0$ の部分には $0$ が $k-2$ 個並んでいます）。ここで，９個の点を考えたのは，減少幅は $9$ で割ったときの余りが $7$ になるので，それが一致する点を選ぶ必要があるからです。
この９個の点の中に $y$ 座標が
\begin{align*}
\underbrace{99\cdots 99}_{\text{$k-3$ 個}}882+9k=10^k+9k-118
\end{align*}
に一致している点が存在するように $k$ を選びます。図で説明すると以下のような感じです：
\begin{align*}
(10^k+j,\,10^k+2j+1)\quad (j=0,\,1,\,\cdots,\,8)
\end{align*}
と表し，$y$ 座標の差を考えると，
\begin{align*}
10^k+9k-118-10^k-2j-1=9k-2j-119=0
\end{align*}
となればよく，これをみたすのは $k=15$，$j=8$ となります。$k=15$ のとき，
\begin{align*}
\underbrace{99\cdots 99}_{\text{$k-3$ 個}}882+9k&=999,999,999,999,882+135\\
&=1,000,000,000,000,017
\end{align*}
なので，$f(1,000,000,000,000,008)$ と確かに一致します。こうして，大きさ $3$ のパーティ
\begin{align*}
&f(999,999,999,999,891)=f(999,999,999,999,900)\\
=\,\,&f(1,000,000,000,000,008)=1,000,000,000,000,017
\end{align*}
が得られました。(2)解決です！！以上のようにして，大きさ $2$ のパーティから出発して３つ目の仲間を探し出すことができました。
上の３つの数は，題意をみたす最小の数の組ではありませんが，とにかく「２つ」から「３つ目」を得る具体的な構成法が得られています。
次節ではこの構成法を駆使し，(3)および問題２を解決しましょう！
(3)の解説
前節で，大きさ $3$ のパーティを具体的に見つけました。以下，同様の構成法を一般の場合に適用し，いくらでも大きなパーティを見つけることができることを示します。
数学的帰納法で示します。
自然数 $m$ に対し，相異なる $m$ 個の自然数
\begin{align*}
n_1\lt n_2\lt \cdots\lt n_m
\end{align*}
について，これらが仲間である，すなわち，
\begin{align*}
f(n_1)=f(n_2)=\cdots =f(n_m)(=F\text{とおく})
\end{align*}
が成り立っていると仮定します。この大きさ $m$ のパーティから出発して，大きさ $(m+1)$ のパーティを構成することができれば，同じことをくり返せばいくらでも大きなパーティを構成することができるので証明終了です！
$n_m<10^k$ となるような最小の自然数 $k$ をとります。
整数 $l\geqq 0$ を任意にとり，
\begin{align*}
n_i^\prime =n_i+10^{k+l}-10^k\quad (i=1,\,2,\,\cdots,\, m)
\end{align*}
とすると，
\begin{align*}
(n_i^\prime,\,f(n_i^\prime))\in M_{k+l,0}\quad (i=1,\,2,\,\cdots,\, m)
\end{align*}
となります。
\begin{align*}
10^{k+l}-10^k&=10^k(10^l-1)\\
&=\underbrace{99\cdots 99}_{\text{$l$ 個}}\underbrace{00\cdots 00}_{\text{$k$ 個}}
\end{align*}
であることに注意して $f(n_i^\prime)$ を計算すると，
\begin{align*}
f(n_i^\prime)&=f(n_i+10^{k+l}-10^k)=n_i+10^{k+l}-10^k+9l+S(n_i)\\
&=f(n_i)+10^{k+l}-10^k+9l=F+10^{k+l}-10^k+9l
\end{align*}
なので，各 $f(n_i^\prime)$ の値も一致します。$M_{k+l,1}$ の小さい方から９個の点
\begin{align*}
(10^{k+l}+j,\,f(10^{k+l}+j))\quad (j=0,\,1,\,\cdots,\,8)
\end{align*}
を考えると，
\begin{align*}
f(10^{k+l}+j)=10^{k+l}+2j+1
\end{align*}
なので，これらの値の１つが $f(n_l^\prime)$ と一致するには，
\begin{align*}
F+10^{k+l}-10^k+9l-10^{k+l}-2j-1=F-10^k+9l-2j-1=0
\end{align*}
すなわち，
\begin{align*}
9l=10^k-F+2j+1
\end{align*}
が成り立てばOKです。$j=0,\,1,\,\cdots,\,8$ を適当にとれば右辺を $9$ の倍数にすることができるので，これをみたす $l$，$j$ は存在します。そのような $l$，$j$ の１つを $l_0$，$j_0$ とすると，
\begin{align*}
f(n_i+10^{k+l_0}-10^k)=f(10^{k+l_0}+j_0)\quad (i=1,\,2,\,\cdots,\,m)
\end{align*}
が成り立ち，大きさ $(m+1)$ のパーティを構成することができました。これで証明終了です！！
おわりに
以上，私が2022年の年賀状に載せた問題の解説でした^^問題の意味は小学生でも理解できるけど，実際に見つけるのは３つの場合でもかなり骨の折れる問題でした^^;
私は「お年玉ゲット」の締め切りを
「１月１１日１１時１１分１１秒」
に定めています（笑）
これを書いているのは１月１６日なのですが，残念ながら今年の正解者はゼロでした^^;
今回ご紹介した証明は，私が初めて解いたときの証明がベースになっています。
少しでも解説が分かりやすいものになるように，証明を整理しグラフや図なども用意しました。
証明の大筋は，下の図の左側のように，仲間となる数から上に向かって新しい仲間を探しにいくことです：
計算はしていませんが，こっち方法の方が楽かもしれません。
でも今回は私が最初に証明した方法を採用しました。興味のある方は下に向かって探しにいく方法でもやってみてください^^
今回の問題の元ネタになった問題は，漫画『数学ゴールデン』に登場したものでした。
作品中では，この問題の他にも面白い問題・難しい問題がたくさん扱われています。
ストーリーも面白いので，まだ読んだことがないよ～という方はぜひぜひ読んでみてください^^
コメントを残す