Problem B. 5258. (September 2022)
B. 5258. Is it true that every positive integer has a positive multiple in which the sum of the digits in decimal notation is at most 2022?
Proposed by Cs. Sándor, Budapest
(5 pont)
Deadline expired on October 10, 2022.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Azt fogjuk belátni, hogy nem igaz: van olyan pozitív egész szám, melynek minden pozitív többszörösében több, mint 2022 a számjegyek összege.
Nevezetesen, igazolni fogjuk, hogy az \(\displaystyle n=\underbrace{99\dots 9}_k=10^k-1\) szám minden pozitív többszörösében legalább \(\displaystyle 9k\) a számjegyek összege. Így például a \(\displaystyle k=225\) választással kapott \(\displaystyle 10^{225}-1\) szám minden pozitív többszörösében legalább \(\displaystyle 9\cdot 225=2025>2022\) a számjegyek összege, vagyis a feladat kérdésére valóban az a válasz, hogy nem igaz.
Jelölje az \(\displaystyle m\) szám számjegyeinek összegét \(\displaystyle S(m)\). Azt látjuk be \(\displaystyle t\)-re vonatkozó teljes indukcióval, hogy bármely \(\displaystyle t\geq 1\) egészre \(\displaystyle S(tn)\geq 9k\) (ahol továbbra is \(\displaystyle n=\underbrace{99\dots 9}_k=10^k-1\)). Az állítás \(\displaystyle t=1\)-re nyilvánvalóan teljesül, hiszen \(\displaystyle S(n)=9k\).
Tegyük fel most, hogy \(\displaystyle t>1\) és a \(\displaystyle t\)-nél kisebb pozitív egészekre már igazoltuk az állítást, célunk megmutatni, hogy \(\displaystyle t\)-re is teljesül: \(\displaystyle S(tn)\geq 9k\). Jelölje a \(\displaystyle tn\) szám utolsó \(\displaystyle k\) jegye által alkotott számot \(\displaystyle a_0\), a következő \(\displaystyle k\) jegye által alkotott számot \(\displaystyle a_1\), és így tovább, amíg el nem fogynak a jegyek. Ezzel a jelöléssel
\(\displaystyle tn=a_0+10^k a_1+10^{2k}a_2+\dots +10^{a_\ell}a_{\ell},\)
ahol \(\displaystyle \ell = \left \lceil \frac{tn\text{ jegyeinek száma}}{k} \right\rceil-1\).
Mivel \(\displaystyle t>1\), ezért \(\displaystyle tn\geq 2n>10^k\), így \(\displaystyle \ell \geq 1\). Az \(\displaystyle r:=a_0+a_1+\dots+a_{\ell}\) szám osztható \(\displaystyle n\)-nel, hiszen a \(\displaystyle 10^k\) szám (és így hatványai is) 1 maradékot adnak \(\displaystyle n\)-nel osztva, így a \(\displaystyle tn\) és \(\displaystyle r\) számok \(\displaystyle n\)-es maradéka ugyanaz. Mivel \(\displaystyle \ell \geq 1\) és \(\displaystyle a_{\ell}>0\), ezért
\(\displaystyle r=a_0+a_1+\dots+a_{\ell}<a_0+10^k a_1+10^{2k}a_2+\dots +10^{a_\ell}a_{\ell}=tn,\)
így az indukciós feltevés alapján \(\displaystyle S(r)\geq 9k\). Világos, hogy
| \(\displaystyle S(tn)=S(a_0)+S(a_1)+\dots+S(a_\ell). \) | \(\displaystyle {(1)}\) |
Azonban
| \(\displaystyle S(a_0+a_1+\dots+a_{\ell})\leq S(a_0)+S(a_1)+\dots+S(a_\ell), \) | \(\displaystyle {(2)}\) |
hiszen az \(\displaystyle a_0+a_1+\dots+a_\ell\) összeget írásbeli összeadással számolva, ha nem keletkezne maradék, akkor épp egyenlőség lenne, különben pedig minden egyes 10-es átvitelnél 10-es összeget 1-re cserélünk, és így végül kisebb számjegyösszeget kapunk.
Tehát (1) és (2) alapján valóban \(\displaystyle S(tn)\geq S(r)\geq 9k\). Ezzel az állítást indukcióval igazoltuk.
Statistics:
75 students sent a solution. 5 points: Archit Manas, Bényei Borisz, Christ Miranda Anna, Csilling Dániel, Czirják Márton Pál, Elekes Dorottya, Farkas 005 Bendegúz, Fülöp Csilla, Guthy Gábor, Kosztolányi Karina, Kovács Benedek Noel, Melján Dávid Gergő, Nguyen Kim Dorka, Seres-Szabó Márton, Simon László Bence, Slézia Dávid, Szakács Ábel, Szanyi Attila, Tarján Bernát, Varga Boldizsár, Virág Lénárd Dániel, Virág Rudolf, Wiener Anna, Zömbik Barnabás. 4 points: Balaskó Imola, Bencz Benedek, Bodor Mátyás, Chrobák Gergő, Csonka Illés, Lincoln Liu, Lőw László, Orbán Gyula János, Sipos Botond Örs, Szatmáry Benedek, TN. 3 points: 7 students. 2 points: 10 students. 1 point: 13 students. 0 point: 6 students. Unfair, not evaluated: 1 solutions. Not shown because of missing birth date or parental permission: 2 solutions.
Problems in Mathematics of KöMaL, September 2022