Feladat: Gy.2273 Korcsoport: 14-15 Nehézségi fok: átlagos
Füzet: 1986/január, 23 - 24. oldal  PDF file
Témakör(ök): Algebrai átalakítások, Oszthatósági feladatok, Számsorozatok, Tizes alapú számrendszer, Számjegyekkel kapcsolatos feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1985/május: Gy.2273

Egy háromjegyű számból kivonjuk a jegyeinek az összegét. A kapott különbségre megismételjük az előbbi eljárást, és így tovább, összesen százszor. Bizonyítsuk be, hogy az eredményül kapott szám a 0.

I. Megoldás. Legyen A=10a+b legalább kétjegyű szám, azaz 0b9 és a>0. Ha A-ból kivonjuk a jegyeinek az összegét, akkor a kapott A'=10a'+b' számban egyrészt a'<a, másrészt A' nem negatív.
Ez azt jelenti, hogy az eljárás egy lépése után kapott A' számban a' legalább 1-gyel kisebb, mint A-ban az a. Mivel kezdetben háromjegyű számunkra a legfeljebb 99, így eljárásunk legfeljebb 99 lépés után egyjegyű számhoz vezet, a következő lépésben pedig ebből nulla lesz. Ha még nem tartanánk a századik lépésnél, akkor ezután már minden további lépésben nulla lesz az eredmény.
 

II. megoldás. Ha a háromjegyű abc¯ számból kivonjuk a jegyeinek az összegét, (a+b+c)-t, akkor eredményül
100a+10b+c-(a+b+c)=99a+9b=9(11a+b)-t,(1)
tehát 9-cel osztható számot kapunk. Így az első lépés után kapott szám osztható 9-cel, értéke pedig legfeljebb 9(119+9)=972.
Elegendő most már azt igazolnunk, hogy egy 972-nél nem nagyobb, 9-cel osztható számból kiindulva, a 99. lépésben 0-t kapunk eredményül. Mivel abc¯>0 esetén abc¯-(a+b+c)0, így minden lépésben vagy a korábbinál kisebb pozitív számot kapunk, vagy pedig 0-t.
Mivel 9-cel osztható szám jegyeinek összege is osztható 9-cel, az első lépés után a szóban forgó szám mindig a 9 többszörösével csökken (9-cel vagy 18-cal), így továbbra is osztható marad 9-cel.
Ha most A jelöli az első lépés után kapott számot és A999=891, akkor legfeljebb 99 lépésben valóban eljutunk a 0-hoz.
Ha A900, akkor legfeljebb négy lépésben ‐ ugyanis 99-nél nagyobb számokra lépésenként 18-at vonunk le ‐ 900, vagy pedig 909 adódik, a következő lépésben pedig 891. Elegendő tehát megmutatnunk, hogy 891-re 94-szer alkalmazva eljárásunkat, eljutunk a nulláig.
A 891873855837819801 sorozat mutatja, hogy további 5 lépés után a 801-hez jutunk, ahonnan pedig legfeljebb 8919=89 lépéssel valóban elérjük a 0-t.
Ezzel az állítást igazoltuk.
 

Megjegyzés. A második megoldásból kiderül, hogy az első lépés után a szám lépésenként 9-cel vagy 18-cal csökken, így várhatóan már 100-nál kevesebb lépésben is elérjük a nullát. Valóban megmutatható, hogy ehhez már 80 lépés is elegendő.