Feladat: N.74 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Burcsi Péter ,  Elek Péter ,  Frenkel Péter ,  Gyarmati Katalin ,  Kutalik Zoltán ,  Terék Zsolt ,  Terpai Tamás ,  Tóth Gábor Zsolt ,  Vörös Zoltán ,  Zubcsek Péter Pál 
Füzet: 1996/május, 291 - 293. oldal  PDF file
Témakör(ök): Euler-Fermat-tételek, Skatulyaelv, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/szeptember: N.74

Hívjunk egy pozitív egészet tarkának, ha bármilyen m pozitív egésszel szorozzuk is meg, a szorzat mind a 10 számjegyet tartalmazza. Hívjuk n-tarkának, ha ez a tulajdonság az 1mn egészekre teljesül.
a) Mutassuk meg, hogy tarka szám nincs.
b) Van-e 1995-tarka szám?

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.

 
I. megoldás. a) Nyilván elegendő belátnunk, hogy minden n pozitív egésznek van olyan többszöröse, amely csak a 0 és 1 számjegyeket tartalmazza. Tekintsük ehhez az
1,11,111,...,11...1n+1db
,,csupaegy'' számokat. Ezek közül valamelyik kettő ugyanazt a maradékot adja n-nel osztva a skatulya-elv alapján, különbségük tehát n-nek többszöröse, amely természetesen csak a 0 és 1 számjegyeket tartalmazza.
b) Teljes indukcióval igazoljuk, hogy minden n pozitív egészhez található n-tarka szám, vagyis a feladatnak erre a részére igenlő a válasz. 1-tarka szám nyilvánvalóan létezik, ilyen pl. az 1234567890. Tegyük fel, hogy n-tarka számot már találtunk, jelöljük A-val: ennek segítségével konstruálni fogunk egy (n+1)-tarka számot, ami igazolja állításunkat. A kérdéses (n+1)-tarka számot keressük a C=10lA+B alakban, ahol l és B pozitív egészek. Ha 1mn+1, akkor
mC=10l(mA)+mB
tartalmazza mindazokat a számjegyeket, amiket mA és mB, feltéve, hogy mB<10l. Legyen ezért l a B-től függően olyan, hogy teljesítse az
(n+1)B<10l
egyenlőtlenséget, ekkor C mindenesetre n-tarka az indukciós feltevés és az előbbi észrevétel alapján, sőt (n+1)-tarka is, ha biztosítani tudjuk, hogy (n+1)B mind a 10 számjegyet tartalmazza, más szóval 1-tarka legyen. Most már tehát csak egy megfelelő B-t kell találnunk. Ha pl. k olyan egész, hogy n<10k, akkor az
123456789010k+j(0jn)
alakú egész számok 1-tarkák, és minden lehetséges maradékot kiadnak (n+1)-gyel osztva. Van tehát közöttük (n+1)-nek egy B többszöröse is, amely 1-tarka. Ezzel B-t, tehát C-t is előállítottuk, ami biztosítja az indukciós lépést és állításunk helytálló voltát.
 Braun Gábor (Budapest, Szent István Gimn., III. o. t.)

 
II. megoldás. a) Tegyük fel, hogy az n szám tarka. Legyen az n prímtényezős felbontásában a 2, ill. az 5 kitevője α, ill. β, azaz
n=2α5βn1,ahol(n1,10)=1.
Ekkor
n2=10max(α,β)n1
is tarka, hiszen többszöröse n-nek. Az Euler‐Fermat tétel szerint
n110φ(n1)-1,
azaz
n210max(α,β)(10φ(n1)-1).
Ez azonban azt jelenti, hogy n2-nek van olyan többszöröse, amely φ(n1) db 9-esből és max(α,β) db 0-ból áll, tehát n2 mégsem tarka. Az ellentmondás igazolja az a) állítást.
b) Megmutatjuk, hogy minden n pozitív egészhez található n-tarka szám, sőt bizonyos értelemben majdnem minden pozitív egész n-tarka. A bizonyításhoz bevezetjük a pozitív egészekből álló halmazok sűrűségének fogalmát. Ha A egy pozitív egészekből álló halmaz, akkor jelölje A(x) az A halmaz x-nél nem nagyobb elemeinek a számát, továbbá értelmezzük az A sűrűségét mint
limxA(x)x,
ha ez a határérték létezik. Azt fogjuk bizonyítani, hogy az n-tarka számok sűrűsége 1, amiből rögtön következik az is, hogy van n-tarka szám. Mindenekelőtt az 1-tarka számokról mutatjuk ki, hogy 1 sűrűségűek, más szóval 0 a sűrűsége azoknak a pozitív egészeknek, amelyek nem tartalmazzák mind a 10 számjegyet. Jelölje R ez utóbbi számok halmazát. Mivel egy x korlátot meg nem haladó pozitív egészek legfeljebb
1+[lgx] jegyűek, ezért egy adott számjegyet nem tartalmazó pozitív egészek száma x-ig legfeljebb
9+92+93++91+[lgx]=991+[lgx]-18<92+lgx.
Ebből rögtön adódik, hogy
R(x)x<1092+lgxx=1092(910)lgx,
vagyis x esetén
R(x)x0,
és ezt akartuk bizonyítani. Ezek után az n-tarka számokról mutatjuk meg, hogy 1 sűrűségűek, vagyis 0 a sűrűsége azoknak a pozitív egészeknek, amelyeknek valamilyen 1mn egésszel vett szorzata R-be esik. Ha Rn jelöli ezen utóbbi számok halmazát, akkor tehát
Rn(x)m=1nkxmkR1m=1nR(mx),
amiből
Rn(x)xm=1nmR(mx)mx.
Itt a bal oldal mindig nemnegatív, a jobb oldalon pedig egy olyan véges összeg áll, amelynek minden tagja 0-hoz tart, hiszen láttuk, hogy R sűrűsége 0. Végeredményben tehát a bal oldal is 0-hoz tart, ami éppen azt jelenti, hogy Rn sűrűsége 0. Ezzel a feladatot megoldottuk.
 Frenkel Péter (Fazekas M. Főv. Gyak. Gimn., III. o. t.)

 
Megjegyzés. A tarkaság és a feladatban felvetett probléma más s alapú számrendszerekben is megfogalmazható: mind a két módszer igazolja ebben az általános esetben is n-tarka számok létezését, továbbá hogy s3 mellett tarka számok nincsenek. A kettes számrendszerben ellenben minden páros szám tarka, hiszen a többszörösei 1-gyel kezdődnek és ‐ párosak lévén ‐ 0-ra végződnek.