Problem B. 5150. (February 2021)

B. 5150. Prove that there are only a finite number of positive integers that cannot be obtained by adding one of the digits of a smaller number to that number. What is the largest of these finite number of integers?

(4 pont)

Deadline expired on March 10, 2021.

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

Megoldás. A megoldás során azt fogjuk megmutatni, hogy a legnagyobb ilyen szám a 87.

Vizsgáljuk az eseteket aszerint, hogy mi az utolsó számjegy.

Ha az utolsó számjegy 0, akkor az 5-tel kisebb szám 5-re végződik, így ehhez 5-öt adva megkaphatjuk a számot.

Ha az utolsó számjegy páros, de nem 0, mondjuk \(\displaystyle 2k\) (ahol \(\displaystyle k\in\{1,2,3,4\}\)), akkor a \(\displaystyle k\)-val kisebb szám \(\displaystyle k\)-ra végződik, így ehhez \(\displaystyle k\)-t adva kapjuk a kívánt előállítást.

Az eddigiek alapján minden páros pozitív egész szám megkapható az előírt módon. Folytassuk a páratlan számok vizsgálatával.

Az utolsó jegy elhagyásával kapott számot jelölje \(\displaystyle n\).

Ha az utolsó jegy 9-es, akkor a számunk \(\displaystyle 10n+9\). Ha a szám éppen a 9, akkor nincs megfelelő előállítás, hiszen csak egyjegyű számból kaphatnánk meg, viszont egy ilyenhez mindig saját magát kell hozzáadni, amivel csak páros számokat kaphatunk. Ha a szám nem a 9, akkor legyen \(\displaystyle t\) az \(\displaystyle n\) szám egyik nemnulla jegye. A \(\displaystyle 10n+9-t\) szám az eredetiből úgy kapható, hogy az utolsó 9-es jegyet csökkentjük \(\displaystyle t\)-vel, vagyis a kapott szám egyik jegye is \(\displaystyle t\) (hiszen \(\displaystyle 10n+9-t\) utolsó jegyét törölve \(\displaystyle n\)-et kapjuk), ehhez \(\displaystyle t\)-t adva adódik a megfelelő előállítás.

Ha az utolsó jegy 7-es, akkor a számunk \(\displaystyle 10n+7\). Könnyen látható, hogy a 7 nem kapható meg a kívánt módon, a továbbiakban feltesszük, hogy a szám nem a 7, vagyis \(\displaystyle n\) pozitív egész szám.

Ha az \(\displaystyle n\) szám jegyei között szerepel az \(\displaystyle 1,2,3,4,5,6,7\) jegyek valamelyike, akkor ezt \(\displaystyle t\)-vel jelölve a \(\displaystyle 10n+7-t\) számban szintén szerepel (ugyanazon a helyiértéken), így ehhez \(\displaystyle t\)-t adva megkapjuk számunkat. Ellenkező esetben \(\displaystyle n\) minden számjegye \(\displaystyle 0,8,9\) valamelyike. Speciálisan, a legnagyobb helyiértéken álló jegye 8 vagy 9. Ha a szám értékét 8-cal vagy 9-cel csökkentjük, majd elhagyjuk az 1-esek helyén álló számot (ami 9 vagy 8), akkor az \(\displaystyle n-1\) számot kapjuk. Ha \(\displaystyle n-1\) legnagyobb helyiértéken álló jegye, amit jelöljön \(\displaystyle v\), a 8 vagy 9 valamelyike, akkor \(\displaystyle 10n+7-v\) egyik számjegye a \(\displaystyle v\), így az eredeti szám előállítható \(\displaystyle 10n+7-v\) és \(\displaystyle v\) összegeként. Az \(\displaystyle n-1\) szám legnagyobb helyiértéken lévő jegye csak úgy lehet 8-tól és 9-től is különböző, ha eredetileg 8 volt, és \(\displaystyle n=8{0\dots0}\) alakú, ahol a 0-k száma akár 0 is lehet. Ha legalább egy 0 van, akkor \(\displaystyle n-1=79\dots9\) alakú, ahol legalább egy 9-es van, így a \(\displaystyle (10n+7-9)+9\) előállítás megfelelő. Ha nincs egyetlen 0 sem, akkor \(\displaystyle n-1=7\), vagyis a számunk a 87. Ez a szám valóban nem kapható meg a 78, 79, ..., 86 egyikéből sem (márpedig egyetlen számjegy hozzáadásával legfeljebb 9-cel nőhet egy szám). Tehát a 7-re végződő számok közül pontosan a 7 és a 87 nem állnak elő.

Ha az utolsó jegy 5-ös, akkor a számunk \(\displaystyle 10n+5\). Könnyen látható, hogy az 5 nem kapható meg a kívánt módon, a továbbiakban feltesszük, hogy a szám nem az 5, vagyis \(\displaystyle n\) pozitív egész szám.

Ha az \(\displaystyle n\) szám jegyei között szerepel az \(\displaystyle 1,2,3,4,5\) jegyek valamelyike, akkor ezt \(\displaystyle t\)-vel jelölve a \(\displaystyle 10n+5-t\) számban szintén szerepel (ugyanazon a helyiértéken), így ehhez \(\displaystyle t\)-t adva megkapjuk számunkat. Ellenkező esetben \(\displaystyle n\) minden számjegye \(\displaystyle 0,6,7,8,9\) valamelyike. Speciálisan, a legnagyobb helyiértéken álló jegye a \(\displaystyle 6,7,8,9\) valamelyike. Ha a szám értékét \(\displaystyle 6,7,8,9\) valamelyikével csökkentjük, és elhagyjuk az 1-esek helyén álló számot (ami 9, 8, 7, 6 valamelyike), akkor az \(\displaystyle n-1\) számot kapjuk. Ha \(\displaystyle n-1\) legnagyobb helyiértéken álló jegye, amit jelöljön \(\displaystyle v\), a \(\displaystyle 6,7,8,9\) valamelyike, akkor \(\displaystyle 10n+5-v\) egyik számjegye a \(\displaystyle v\), így az eredeti szám előállítható \(\displaystyle 10n+5-v\) és \(\displaystyle v\) összegeként. Az \(\displaystyle n-1\) szám legnagyobb helyiértéken lévő jegye csak úgy lehet \(\displaystyle 6,7,8,9\) mindegyikétől különböző, ha eredetileg 6 volt, és \(\displaystyle n=6{0\dots0}\) alakú, ahol a 0-k száma akár 0 is lehet. Ha legalább egy 0 van, akkor \(\displaystyle n-1=59\dots9\) alakú, ahol legalább egy 9-es van, így a \(\displaystyle (10n+5-9)+9\) előállítás megfelelő. Ha nincs egyetlen 0 sem, akkor \(\displaystyle n-1=5\), vagyis a számunk a 65. Ez a szám valóban nem kapható meg az 56, 57, ..., 64 egyikéből sem (márpedig egyetlen számjegy hozzáadásával legfeljebb 9-cel nőhet egy szám). Tehát az 5-re végződő számok közül pontosan az 5 és a 65 nem állnak elő.

Az előzőekhez hasonlóan kapjuk, hogy a 3-ra végződőek közül pontosan a 3 és a 43, az 1-re végződőek közül pedig pontosan az 1 és a 21 nem állnak elő a kívánt módon.

Beláttuk, hogy pontosan a következő számok nem kaphatók meg az előírt módon: \(\displaystyle 1,3,5,7,9,21,43,65,87\). Tehát a legnagyobb olyan pozitív egész, ami nem kapható meg, a 87.

Statistics:

110 students sent a solution.
4 points:	89 students.
3 points:	5 students.
2 points:	7 students.
1 point:	1 student.
0 point:	7 students.
Unfair, not evaluated:	1 solutions.

Problems in Mathematics of KöMaL, February 2021