Cím: A 2008. évi Kürschák József Matematikai Tanulóverseny feladatainak megoldása
Szerző(k):  Fleiner Tamás 
Füzet: 2009/február, 67 - 72. oldal  PDF  |  MathML 
Témakör(ök): Kürschák József (korábban Eötvös Loránd), Matematika, Szakmai cikkek

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.

1. feladat. Jelölje az n pozitív egész szám pozitív osztóinak számát d(n). Melyik az a legkisebb valós c érték, amellyel d(n)≤c⋅n teljesül minden pozitív egész n számra?

 
Megoldás. Azt a legkisebb c-t keressük, amire c≥d(n)n teljesül minden pozitív egész n-re. Tudjuk, hogy ha az n kanonikus alakja n=p1α1⋅p2α2⋅...⋅pkαk, akkor n osztóinak száma
d(n)=(α1+1)(α2+1)...(αk+1). Eszerint
c2≥d(n)2n=(α1+1)2(α2+1)2...(αk+1)2p1α1⋅p2α2⋅...⋅pkαk=(α1+1)2p1α1⋅...⋅(αk+1)2pkαk.(1)
Ahhoz, hogy a feladatban leírt, lehető legkisebb c-t megkeressük, az szükséges, hogy (1) jobb oldalát maximalizáljuk. (Pontosabban az, hogy megtaláljuk a szuprémumát, de mint látni fogjuk, ez itt maximalizálást jelent.) Az (1) formula jobb oldala pedig akkor lesz a lehető legnagyobb, ha minden pi prímhez olyan αi∈{0,1,2,...} kitevőt választunk, ami maximalizálja az
(αi+1)2piαi=(2/1)2pi⋅(3/2)2pi⋅(4/3)2pi⋅...⋅((αi+1)/αi)2pi(2)
egyenlőség bal oldalát. A (2) jobb oldalán álló törtek számlálója szigorúan monoton csökken, nevezőjük azonos, tehát a szorzatuk akkor lesz maximális, ha αi-t úgy választjuk, hogy a szorzatba pontosan az
1-nél nagyobb ((s+1)/s)2pi alakú tényezők kerüljenek. Ha pi>4, akkor már a szorzat első tényezője is egynél kisebb. Ezért ha egy szám kanonikus alakjából elhagyjuk a 4-nél nagyobb prímosztókat, akkor ettől a d(n)/n hányados növekszik. Tehát elegendő csak azokkal a számokkal foglalkoznunk, amiknek a prímosztói csak a 2 és a 3 lehetnek. A 2 és 3 prímosztók maximumot meghatározó kitevőit szintén a fentiek figyelembe vételével kaphatjuk meg; vegyük ugyanis észre, hogy
(3/2)22>1>(4/3)22,illetve(2/1)23>1>(3/2)23.
Ez azt jelenti, hogy a d(n)n kifejezés n=22⋅3=12-re maximális. Tehát a keresett legkisebb c érték nem más, mint
c=d(12)n=3⋅24⋅3=3⋅223=33=3.□

 
Megjegyzés. A megoldás módszerével megmutatható, hogy tetszőleges pozitív ε kitevőre létezik egy olyan cε szám, amire d(n)≤cε⋅nε teljesül minden pozitív egész n számra úgy, hogy van olyan pozitív egész nε, amire egyenlőség áll. Ebből az is következik, hogy tetszőleges ε>0 esetén
limn→∞d(n)nε=0.
Ez úgy is kimondható, hogy logd(n)/logn→0, ha n→∞. (Itt feltehető, hogy pl. e alapú logaritmusról beszélünk, hisz az (1-nél nagyobb) alap sem a konvergencia tényét, sem a határértéket nem befolyásolja.) Megjegyezzük, hogy az az erősebb állítás is igaz, hogy alkalmas C konstanssal minden pozitív egész n-re:
logd(n)logn<Cloglogn.
Ez a felső becslés pedig már konstans szorzótól eltekintve pontos és nem javítható tovább. Mindez az n=p1p2...pk alakú számokat vizsgálva látható be, ahol p1<p2<...<pk<... az egymást követő prímek sorozata. Vagyis a fenti egyenlőtlenség lényegében éles, ha n az első k prím szorzata.
 
2. feladat. Legyenek n≥1 és a1<a2<...<an egészek. Bizonyítsuk be, hogy azoknak az 1≤i<j≤n pároknak a száma, amelyekre aj-ai kettőhatvány, legfeljebb akkora, mint azoknak az 1≤i<j≤n pároknak a száma, amelyekre j-i kettőhatvány. (A 2 nemnegatív egész kitevős hatványait nevezzük kettőhatványnak.)
 
Megoldás. Jelölje f(n) az 1,2,...,n számok között fellépő kettőhatvány különbségek számát, F(n) pedig legyen az n különböző egész között fellépő kettőhatvány különbségek maximális száma. Ezzel a feladat állítása F(n)=f(n) alakot ölt, amit n szerinti teljes indukcióval bizonyítunk. Az n=1 eset triviális, hisz F(1)=f(1)=0.
Tegyük fel tehát, hogy n<N esetén már igazoltuk az F(n)=f(n) egyenlőséget. Célunk az F(N)=f(N) bizonyítása. Legyenek tehát az a1<a2<...<aN egészek olyanok, hogy a belőlük képezhető kettőhatvány különbségek száma F(N), és az ilyen tulajdonságú sorozatok közül olyat válasszunk, amire az aN-a1 különbség a lehető legkisebb.
Feltehető, hogy az ai számaink között van páros. Ha ugyanis minden ai páratlan, akkor az {ai+1:1≤i≤N} halmazból a képezhető kettőhatvány különbségek száma F(N), és a legnagyobb és legkisebb szám különbsége sem változott. Ha netán minden ai páros, akkor az egész számokból álló {ai/2:1≤i≤N} halmazból is F(N) kettőhatvány különbség képezhető, ráadásul a legnagyobb és legkisebb szám különbsége csökkent. Mivel az a1,a2,...,aN sorozatot úgy választottuk, hogy ez a különbség minimális legyen, az a1,a2,...,aN számok között bizonyosan van páros és páratlan is. Legyen tehát k a páros és N-k a páratlan ai-k száma, ahol 1≤k<N. Az is feltehető, hogy k≤N2, ha ugyanis ez nem így volna, akkor minden ai-t eggyel megnövelve olyan sorozatot kapnánk, amiben kevesebb a páros szám mint a páratlan, a kettőhatvány különbségek száma F(N) és a legnagyobb és legkisebb szám különbsége sem változik ettől.
A sorozatunkban fellépő kettőhatvány különbségek háromfélék lehetnek. Két páros szám között fellépő kettőhatvány különbségből az indukciós feltevés szerint legfeljebb f(k) lehet, ami megegyezik a 2,4,...,2k számok között fellépő kettőhatvány különbségek számával. Hasonlóan, a páratlan ai-k szintén az indukciós feltevés szerint legfeljebb f(N-k) kettőhatvány különbséget határoznak meg, és ez éppen az 1,3,5,...,2(N-k)-1 számok között fellépő kettőhatvány különbségek száma. Végül a páros és páratlan ai-k között fellépő kettőhatvány különbségek páratlanok, így 1-gyel egyenlők. Minden páros ai legfeljebb két ilyen különbségben szerepelhet, ezért legfeljebb 2k lehet ezekből, de az is igaz, hogy minden ilyen különbség ai+1-ai alakú, amiből összesen N-1 van. Figyeljük meg, hogy a {2,4,...,2k} és {1,3,5,...,2(N-k)-1} halmazokból egy-egy elemet kiválasztva pontosan 2k-féleképpen választhatunk szomszédos számokat, kivéve, ha k=N2, amikor csak N-1 ilyen választás lehetséges.
Azt kaptuk, hogy az általunk vizsgált {a1,a2,...,aN} halmazban legfeljebb annyi kettőhatvány különbség lép fel, mint a H={1,2,3,...,2k,2k+1,2k+3,2k+5,...,2(N-k)-1} halmazban. Ezért az indukciós lépés befejezéséhez azt kell megmutatnunk, hogy a H halmaz legfeljebb annyi kettőhatvány különbséget határoz meg, mint az [N]:={1,2,...,N} halmaz. Ha k=N2, akkor H=[N], és nincs mit bizonyítanunk. A továbbiakban feltesszük tehát, hogy k<N2.
Vegyük észre, hogy [2k+1]:={1,2,...,2k+1} részhalmaza H-nak és [N]-nek is, ezért a [2k+1] halmazon belül fellépő kettőhatvány különbségek nem okoznak eltérést.
A H∖[2k+1]={2k+3,2k+5,...,2(N-k)-1}, illetve [N]∖[2k+1]={2k+2,2k+3,...,N} halmazok egyaránt f(N-2k-1) kettőhatvány különbséget határoznak meg. Annyit kell tehát bizonyítanunk, hogy a [2k+1] halmaz és a H∖[2k+1] halmaz elemei között fellépő kettőhatvány különbségek száma nem lehet több, mint a [2k+1] halmaz és az [N]∖[2k+1] halmaz elemei között fellépő kettőhatvány különbségek száma. Ha azonban az x∈[2k+1] és az y∈H∖[2k+1] számok különbsége kettőhatvány, akkor mivel e különbség legalább 2 és y páratlan, ezért x-nek is annak kell lennie. Így a (2k+1)-ből ,,felére kicsinyített''
x':=2k+1-12(2k+1-x)ésy':=2k+1+12(y-(2k+1))
számok a [2k+1], illetve [N]∖[2k+1] halmazok olyan elemei, amik különbsége
y'-x'=2k+1-(2k+1)+12(y-(2k+1)+2k+1-x)=12(y-x)
szintén kettőhatvány.
Azt kaptuk, hogy minden H-beli kettőhatvány különbséghez találtunk egy-egy különböző kettőhatvány különbséget [N]-ben, és ezzel az indukciós lépést igazoltuk, a feladat állítását pedig bebizonyítottuk.  □
 
Megjegyzés. 1. Nem igaz, hogy ha az a1<a2<...<an sorozat maximális számú kettőhatvány különbséget határoz meg, akkor számtani sorozatról van szó: az 1, 2, 3, 4 és az 1, 2, 3, 5 sorozatok mindegyikéből ötféleképp lehet kettőhatvány különbséget képezni.
2. A feladat állítása 2 helyett más pozitív egész szám hatványaira is igaz, de ennek bizonyítása a feladatbeli állításnál valamivel bonyolultabb.
 
3. feladat. Egy országban a városok közötti közlekedés vonaton és busszal lehetséges. A vasúttársaság és a buszvállalat is bizonyos várospárok között közlekedtet járatokat, ám két város között nem feltétlenül jár mindkét irányba járat. Tudjuk, hogy bárhogyan is választunk ki két várost, el lehet jutni egy fajta közlekedési eszközön (esetleges átszállásokkal) az egyikből a másikba (de a másikból az egyikbe már nem feltétlenül). Bizonyítsuk be, hogy van olyan város, amelyből bármely másik város elérhető egyféle közlekedési eszközzel úgy, hogy a különböző városokba jutás eszköze más-más lehet.
 
I. megoldás. Azt mondjuk, hogy az a városból elérhető a b város, ha csak vonaton vagy csak buszon el lehet jutni (esetleg átszállásokkal) a-ból b-be. A feladatot az országban található városok n száma szerinti indukcióval oldjuk meg. A feladat állítása n=1 esetén világos. Tegyük fel tehát, hogy n-nél kevesebb városra már igazoltuk az állítást, és tekintsünk egy n városból álló országot a leírt feltételekkel.
Legyen v az ország egy tetszőleges városa, és tekintsük a v-től különböző n-1 várost. Ezen n-1 város közül bármely kettőre igaz, hogy valamelyikükből (esetleg v-n is átutazva) elérhető a másik. Módosítsuk az n-1 városból álló hálózatot (gondolatban) úgy, hogy a létező járatok mellett odaképzeljük azokat is, amelyek csak v-n átutazva valósíthatóak meg. Az így kibővített, n-1 városból álló hálózatra alkalmazhatjuk az indukciós feltevést, tehát van egy olyan f(v) város az n-1 között, amelyből minden v-től különböző város elérhető. Ha v is elérhető f(v)-ből, akkor készen vagyunk, hiszen
f(v) megfelel a kívánalmaknak.
Ha tehát v nem érhető el f(v)-ből, akkor a feltétel szerint f(v) elérhető v-ből, és az általánosság megszorítása nélkül az is feltehető, hogy ez busszal lehetséges. Legyen B, illetve V az f(v)-ből busszal, illetve vasúton elérhető, f(v)-től különböző városok halmaza. Tekintsük a városok V':=V∪{v} halmazát. Mivel f(v) nincs V'-ben, azért V' legfeljebb n-1 várost tartalmaz. Az is igaz, hogy V' bármely két városa közül egyikből elérhető a másik (esetleg V'-n kívüli városok érintésével). A korábban látott módon alkalmazhatjuk az indukciós feltevést V'-re, így van benne olyan v' város, amelyből minden V'-beli város elérhető.
Ha v'=v ez a város, akkor v megfelel a feladat kívánalmainak, hiszen v-ből minden V-beli város elérhető v' választása miatt, és azt is láttuk, hogy busszal v-ből f(v) és az összes B-beli város is elérhető.
Ha pedig v'≠v, akkor v'∈V, és ekkor v'-ből V minden városa és v is elérhető. Ha v vonattal érhető el v'-ból, akkor v elérhető lenne vonattal v'-n keresztül f(v)-ből is, amiről korábban feltettük, hogy lehetetlen. Ezek szerint v busszal érhető el v'-ből. Azonban ekkor v-n keresztül f(v) és így B minden városa is elérhető v'-ből busszal, ami éppen azt jelenti, hogy v' rendelkezik a feladatban megkövetelt tulajdonsággal.  □
A fenti bizonyításban az indukciós lépés ,,ravasz''. Az indukciót azonban a fenti megoldás első két bekezdése után máshogyan is befejezhetjük.
 
II. megoldás. Ha az ország valamelyik v városa elérhető f(v)-ből, akkor készen vagyunk, hisz ekkor f(v)-ből minden város elérhető. Tegyük fel tehát, hogy ez egyetlen v városra sem igaz, így a feladatbeli feltétel szerint bármelyik v városból elérhető f(v).
Legyen v egy tetszőleges város, és tekintsük a városok
v,f(v),f(f(v)),f(f(f(v))),...
sorozatát. Mivel véges sok város van, ezért a sorozatban előbb-utóbb felbukkan egy már korábban felsorolt város is. Találunk tehát egymástól különböző v1,v2,...,vk városokat úgy, hogy i=1,2,...,k-ra
f(vi)=vi+1 teljesül (ahol vk+1=v1). A v2,...,vk,vk+1 városok tehát rendelkeznek azzal a tulajdonsággal, hogy tetszőleges vi-ből vi-1 kivételével minden másik vj város elérhető. Ez azt is jelenti, hogy
k≥3, hiszen v1-ből v2 elérhető, de vk nem.
Tegyük fel, hogy valamelyik vi-1-ből vi vonattal, míg vi-ből vi+1 busszal érhető el. Tudjuk, hogy vi+1-ből vi-1 elérhető. Ha ez busszal lehetséges, akkor vi-ből busszal vi+1-ben átszállva vi-1-be juthatunk, amiről feltettük, hogy nem lehetséges. Ha vi+1-ből vonattal lehet vi-1-be eljutni, akkor innen vonattal továbbutazhatunk vi-be, ami f(vi)=vi+1 miatt szintén nem lehetséges. Azt kaptuk tehát, hogy a vi-1-ből vi-be jutás eszközének azonosnak kell lennie a vi-ből vi+1-be jutás eszközével.
Ha tehát v1-ből busszal juthatunk v2-be, akkor v2-ből v3 is busszal érhető el, majd v3-ból v4-be is busszal juthatunk, és így tovább egészen vk-ig. Vagyis v1-ből vk elérhető, ami ellentmond annak a feltevésünknek, hogy egyetlen v város sem érhető el f(v)-ből. Kell lennie tehát olyan v városnak, ami f(v)-ből elérhető, ám ekkor f(v) rendelkezik a feladatban megkövetelt tulajdonsággal.  □
 
Megjegyzések. 1. Kettőnél több közlekedési eszköz esetén már nincs feltétlenül olyan város, ahonnan minden más város elérhető. Ez a helyzet, ha például A-ból B-be busz, B-ből C-be vonat és C-ből A-ba mondjuk kishajó közlekedik.
2. Ha nem tesszük fel, hogy bármely két város között van valamelyik irányba közlekedés, akkor nem mindig létezik olyan város, amelyikből minden másik elérhető. Igaz azonban, hogy található városoknak egy olyan V halmaza, hogy semelyik V-beli városból sem érhető el semelyik másik V-beli város, azonban bármelyik V-n kívüli város elérhető valamelyik V-beli városból. Nem látszik, hogy a fent közölt megoldások bármelyike kiterjeszthető-e az általánosabb állítás bizonyításává.
3. A közölt megoldások egyike sem algoritmikus, azaz egy kívánt tulajdonságú város megtalálására nem ad annál jobb módszert, mint hogy sorra ellenőrizzük az egyes városokat. Létezik olyan (n-től független) c konstans, hogy tetszőleges városról el tudjuk dönteni cn lépésben, hogy rendelkezik-e a kívánt tulajdonsággal (ahol n az ország városainak számát jelöli), így az egymás utáni ellenőrzéseket legfeljebb cn2 lépésben el tudjuk végezni. A 2. megjegyzésben jelzett V halmaz megtalálása a részhalmazok egyenkénti ellenőrzésével már sokkal több lépést igényelne. Létezik azonban olyan A algoritmus és C konstans, hogy bármely n városból álló országban az A algoritmus legfeljebb C⋅n2 lépés után megtalál egy, a 2. megjegyzésben leírt V városhalmazt.
4. A feladat bizonyos rokonságot mutat Gale és Shapley (sajnos nem eléggé) ismert ,,stabil házassági'' tételével. A részleteket egy remélhetőleg hamarosan megjelenő KöMaL cikk tartalmazza.