Problem B. 5212. (December 2021)

B. 5212. Prove that there exists a positive integer which can be represented in at least 2021 different ways by taking an appropriate positive integer (in decimal notation), and adding the sum of its digits to it.

Proposed by Cs. Sándor, Budapest

(6 pont)

Deadline expired on January 10, 2022.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Az \(\displaystyle n\) számra vonatkozó teljes indukcióval bizonyítjuk, hogy van olyan pozitív egész szám, ami legalább \(\displaystyle n\)-féleképpen áll elő egy pozitív egész szám és annak számjegyeinek összegeként. A \(\displaystyle k\) szám számjegyeinek összegét jelölje \(\displaystyle S(k)\).

Az \(\displaystyle n=1\) eset triviális, \(\displaystyle n=2\)-re a 101 megfelelő, hiszen \(\displaystyle k=91\) és \(\displaystyle k=100\) esetén egyaránt \(\displaystyle k+S(k)=101\).

Az indukciós lépést először \(\displaystyle 2\to 3\)-ra mutatjuk meg (ugyanez a módszer működni fog nagyobb \(\displaystyle n\)-re is). Mivel

\(\displaystyle 91+S(91)=100+S(100)=101,\)

ezért világos, hogy az

\(\displaystyle a:=\overline{1\underbrace{00\dots0}_{t}100}\)

és

\(\displaystyle b:=\overline{1\underbrace{00\dots0}_{t}091}\)

számokra

\(\displaystyle a+S(a)=b+S(b)=\overline{1\underbrace{00\dots0}_{t}102},\)

bárhogyan is választjuk meg \(\displaystyle t\) értékét. Keressünk egy

\(\displaystyle c:=\overline{\underbrace{99\dots9}_{t}99r}\)

alakú számot (itt \(\displaystyle r\) a \(\displaystyle c\) szám utolsó jegyét jelöli), melyre szintén

\(\displaystyle c+S(c)=\overline{1\underbrace{00\dots0}_{t}102}.\)

Ahhoz, hogy ez teljesüljön az kell, hogy \(\displaystyle 9(t+2)+r=(10-r)+102\), vagyis

\(\displaystyle 9(t+2)=112-2r\)

legyen. Az \(\displaystyle r\) számjegyet úgy kell megválasztani, hogy \(\displaystyle 9\mid 112-2r\) teljesüljön, \(\displaystyle r=2\) a megfelelő választás. Ekkor \(\displaystyle 9(t+2)=108\)-ból \(\displaystyle t=10\). Tehát a \(\displaystyle \overline{1\underbrace{00\dots0}_{10}102}=10\,000\,000\,000\,102\) szám háromféleképpen is előáll:

\(\displaystyle a=10\,000\,000\,000\,100,\)

\(\displaystyle b=10\,000\,000\,000\,091,\)

\(\displaystyle c=9\,999\,999\,999\,992\)

mellett

\(\displaystyle a+S(a)=b+S(b)=c+S(c)=10\,000\,000\,000\,102.\)

Most az általános indukciós lépést igazoljuk. Tegyük fel, hogy az \(\displaystyle a_1,a_2,\dots,a_n\) különböző számokra

\(\displaystyle s=a_1+S(a_1)=a_2+S(a_2)=\dots=a_n+S(a_n).\)

Az \(\displaystyle s\) szám jegyeinek száma legyen \(\displaystyle N\). Világos, hogy ha \(\displaystyle M>N\), akkor az \(\displaystyle a_i'=10^M+a_i\) számra

\(\displaystyle a_i'+S(a_i')=10^M+a_i+S(a_i)+1=10^M+s+1=:s'.\)

Az \(\displaystyle s'\) számnak tehát van \(\displaystyle n\) különböző előállítása \(\displaystyle a_i'+S(a_i')\) alakban, az összes \(\displaystyle a_i'\) szám 1-essel kezdődik. Megfelelő \(\displaystyle M\) mellett \(\displaystyle c=10^M-(10-r)\) alakban keresünk olyan számot, melyre szintén \(\displaystyle c+S(c)=s'\), ez egy \(\displaystyle (n+1)\)-edik előállítást szolgáltat majd, hiszen a \(\displaystyle c\) szám 9-essel kezdődik. Itt \(\displaystyle 1\leq r\leq 9\), és \(\displaystyle c\) az a szám, melynek utolsó jegye \(\displaystyle r\), a többi \(\displaystyle M-1\) jegye pedig 9-es, azaz \(\displaystyle S(c)=9(M-1)+r\). Tehát az

\(\displaystyle s'=10^M-(10-r)+9(M-1)+r\)

feltételnek kell teljesülnie, ami ekvivalens az

\(\displaystyle s=9(M-2)+2r-2\)

feltétellel. Válasszuk meg \(\displaystyle 1\leq r\leq 9\) értékét úgy, hogy \(\displaystyle 9\mid s-2r+2\) legyen, és legyen

\(\displaystyle M:=\frac{s-2r+2}{9}+2.\)

Mivel a \(\displaystyle 2,4,6,8,10,12,14,16,18\) számok 9-es maradéka páronként különböző, ezért \(\displaystyle r\)-re pontosan egy megfelelő választás van.

Ezzel az indukciós lépést igazoltuk.

Ebből tehát következik, hogy olyan szám is van, melynek legalább 2021-féle előállítása is van.

Megjegyzés. Az indukciós lépés valójában \(\displaystyle n=1\)-ről \(\displaystyle n=2\)-re is működik. \(\displaystyle a_1=1\) mellett \(\displaystyle s=a_1+S(a_1)=2\), vagyis \(\displaystyle N=1\). Ekkor \(\displaystyle 1<M\)-re \(\displaystyle s'=10^M+1+S(10^M+1)=10^M+3\), és \(\displaystyle c\)-t \(\displaystyle c=10^M-(10-r)\) alakban keressük. \(\displaystyle 9\mid s-2r+2=4-2r\) akkor teljesül, ha \(\displaystyle r=2\). Ekkor \(\displaystyle M=\frac{s-2r+2}{9}+2=2\), vagyis \(\displaystyle c=100-8=92\). Ekkor \(\displaystyle 101+S(101)=92+S(92)=103\).

Statistics:

42 students sent a solution.
6 points:	Bálint Béla, Baski Bence, Ben Gillott, Bencsik Dávid, Bencz Benedek, Bényei Borisz, Bognár 171 András Károly, Chrobák Gergő, Csonka Illés, Diaconescu Tashi, Duchon Márton, Foris Dávid, Fülöp Csilla, Han Ziying, Jánosik Máté, Kalocsai Zoltán, Lovas Márton, Melján Dávid Gergő, Molnár István Ádám, Móricz Benjámin, Németh Márton, Nguyen Kim Dorka, Rareș Polenciuc, Sági Mihály, Sebestyén József Tas, Simon László Bence, Szabó 810 Levente, Szanyi Attila, Tarján Bernát, Tran Dávid, Varga Boldizsár, Virág Rudolf, Wiener Anna, Zömbik Barnabás.
5 points:	Juhász-Molnár Erik.
4 points:	3 students.
3 points:	2 students.
0 point:	1 student.
Unfair, not evaluated:	1 solutions.

Problems in Mathematics of KöMaL, December 2021