Feladat: Gy.2945 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Burcsi Péter ,  Deli Tamás ,  Fazekas Zoltán ,  Formanek Csaba ,  Frenkel Péter ,  Gröller Ákos ,  Gyukics Mihály ,  Gyurkó L. Gergely ,  Havasi Ferenc ,  Jeszenszky Gyula ,  Kardos Gergely ,  Katona Zsolt ,  Király Csaba ,  Kovács András ,  Kovács Baldvin ,  Kozma Róbert ,  Kurucz Zoltán ,  Lippner Gábor ,  Lolbert Tamás ,  Madarász József ,  Makai Márton ,  Nyakas Péter ,  Nyul Gábor ,  Orbán András ,  Pap Gyula ,  Peltz Csaba ,  Puskás Péter ,  Rozmán András ,  Ruzsa Gábor ,  Szabó Gábor ,  Szőke Ervin ,  Terpai Tamás ,  Tóth Gábor Zsolt ,  Tóth Péter ,  Ugron Balázs ,  Urbancsek Tamás ,  Véber Miklós ,  Vörös Zoltán ,  Übelhart István ,  Zubcsek Péter Pál 
Füzet: 1995/április, 214 - 215. oldal  PDF  |  MathML 
Témakör(ök): Indirekt bizonyítási mód, Számsorozatok, Számjegyekkel kapcsolatos feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1994/november: Gy.2945

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Ha n természetes szám, akkor P(n)0, és így n+P(n)n. Az {ni} sorozat tehát monoton növő, vagyis az állítás pontosan akkor teljesül, ha a sorozat valahonnan kezdve konstans. Ez viszont akkor lép föl, ha a sorozat valamely elemére, mondjuk nh-ra, P(nh)=0, ami azt jelenti, hogy nh jegyei között van nulla. Azt kell tehát igazolni, hogy a sorozat elemei között előbb-utóbb előfordul egy ilyen tulajdonságú.
Tegyük föl indirekt módon, hogy nincs ilyen, így a sorozat nem lesz konstans, azaz tetszőlegesen nagy értéket felvesz. Vizsgáljuk azokat az nj elemeket, amelyekre nj+1 több jegyből áll, mint nj:

nj<10knj+1.
Ekkor nj legfeljebb k jegyből áll, ezért P(nj)9k, azaz nj+1=nj+P(nj)nj+9k<10k+9k. Ha belátjuk, hogy valamely j esetén
10knj+1<10k+10k-1,
akkor készen vagyunk, hiszen ez azt jelenti, hogy nj+1 második jegye nulla, ami ellentmondás.
Mivel 10knj+1 már a j választása miatt fennáll, továbbá nj+1<10k+9k, azért elegendő azt megmutatni, hogy
9k<10k-1,
átrendezve
9<(109)k-1
fennáll. Belátjuk, hogy ez k25 esetén teljesül. (Valójában már k22 esetén is, de ezt nehézkesebb igazolni, s a feladat szempontjából lényegtelen.) Ekkor készen leszünk, hiszen indirekt feltevésünk szerint a sorozat tetszőlegesen nagy értéket felvesz, vagyis található olyan j, amelyhez 24-nél nagyobb k tartozik.
(109)4=100006561>32,mert20000>36561=19683;
valamint
(32)6=72964>9,vagyis729>964=576.
Ezek szerint
(109)24=((109)4)6>(32)6>9.
Minthogy 109>1, ezért ha k25, akkor (109)k-1(109)24>9. Ezzel az állítást beláttuk.
 Nyul Gábor (Debrecen, Fazekas M. Gimn., I. o.t.) dolgozata alapján