Feladat: 1982. évi Kürschák matematikaverseny 2. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Csillag Péter ,  Hetyei Gábor ,  Károlyi Gyula ,  Magyar Ákos ,  Szabó Endre ,  Tardos Gábor ,  Tóth Gábor 
Füzet: 1983/február, 53 - 56. oldal  PDF file
Témakör(ök): Természetes számok, Legkisebb közös többszörös, Oszthatósági feladatok, Prímtényezős felbontás, Oszthatóság, Egyenlőtlenségek, Sorozat határértéke, Prímszámok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1983/február: 1982. évi Kürschák matematikaverseny 2. feladata

Bizonyítsuk be, hogy minden k>2 egész számhoz létezik végtelen sok olyan n természetes szám, hogy az n,n+1,...,n+k-1 számok legkisebb közös többszöröse nagyobb, mint az n+1,n+2,...,n+k számok legkisebb közös többszöröse.

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.

(A legkisebb közös többszörös annyiszor fordul elő az alábbi szövegben, hogy röviden lkkt-t írunk helyette.)

 

I. megoldás. Az a1, a2, ..., am számok lkkt-ét ‐ amit így szokás jelölni: [a1,a2,...,am], ‐ úgy határozhatjuk meg, hogy minden prímszámot, amelyik a számok valamelyikének osztója, vesszük azon a legmagasabb hatványon, amelyiken osztója valamelyik ai-nek, és ezeket a prímszámhatványokat összeszorozzuk. Eszerint
Tn=[n,n+1,...,n+k-1] és Tn+1=[n+1,n+2,...,n+k-1,n+k]
prímhatványokra történő felbontásában egyenlő hatványon szerepelnek azok a prímszámok, amelyeknek a legmagasabb hatványa az n+1, n+2, ..., n+k-1 számok valamelyikének a felbontásában fordul elő. Tn-ben magasabb hatványon szerepelnek, mint Tn+1-ben azok a prímek (ha vannak), amelyeknek magasabb hatványa osztója n-nek, mint n+1, ..., n+k bármelyikének, és alacsonyabb hatványon azok az esetleges prímek, amelyeknek magasabb hatványa osztója n+k-nak, mint n, ..., n+k-1 bármelyikének.
Legyenek p1, ..., pg az előbbi tulajdonságú prímek és legyen pj a Tn-nek (s így n-nek is) a tj-edik hatványon osztója, Tn+1-nek az uj-edik hatványon osztója, ahol tj>uj (j=1,...,g); hasonlóan legyenek az utóbbi tulajdonsággal rendelkező prímek q1, ..., qh és qj Tn-nek vj-edik, Tn+1-nek wj-edik hatványon osztója, v<wj(j=1,...,h). Ekkor
Tn+1=q1w1-v1...qhwh-vhp1t1-u1...pgtg-ugTn.(1)

Végtelen sok olyan n értékre van tehát szükségünk, amelyekre a Tn a jobb oldalon 1-nél kisebb számmal van megszorozva. Ehhez legegyszerűbb n-et úgy választani, hogy n+1, ..., n+k-1 egyikével se legyen 1-nél nagyobb közös osztója, (n+k)-nak viszont legalább az egyikükkel legyen. Ekkor a tört nevezője n lesz, a számlálója pedig legfeljebb n+k2. A tört tehát nem nagyobb, mint n+k2n; ez pedig 1-nél kisebb, ha n nagyobb k-nál.
 

Ha végtelen sok n-re kielégítjük az első két feltételt, akkor közülük végtelen sok nagyobb is lesz mint k, tehát elég olyan n egészeket keresnünk, amelyekre n relatív prím az n+1, ..., n+k-1 számokhoz, n+k pedig legalább egyikhez nem relatív prím. A feladatot megoldó versenyzők mind ezt az utat választották, de az n kívánt tulajdonságait igen különböző, módokon biztosították. Bemutatjuk a lényegében legegyszerűbbnek látszót.
Ha valamilyen j-re n-nek és (n+j)-nek van 1-nél nagyobb közös osztója, akkor ez közös osztója n és (n+j)-n=j-nek is és megfordítva is: n és j közös osztói (n+j)-nek is osztói. Azt kell tehát elérnünk, hogy kiválasztandó számaink az
1,2,...,k-1(*)
számokhoz relatív prímek legyenek, tehát például a szorzatukhoz is. Ezzel a tulajdonsággal rendelkeznek az*
12...(k-1)
szorzat többszöröseinek a szomszédai, tehát a c((k-1)!)±1 számok.
 

Ahhoz, hogy a k-val nagyobb c((k-1)!)+k±1 a (*) alatti számok valamelyikéhez ne legyen relatív prím, a kettős előjelből a negatívat célszerű választani. Ez esetben a k-val növelt szám osztható (k-1)-gyel, és az (n+1)-ként adódó c((k-1)!) is osztható (k-1)-gyel.
Ha tehát az
nc=c((k-1)!)-1
számokat választjuk, az (1) egyenlőség nevezője nc lesz, számlálója pedig legfeljebb
nc+kk-1.
Így
Tnc+1nc+k(k-1)ncTnc.
Itt k-12, mert a feladat feltétele szerint k>2. Ha tehát nc>k is teljesül (ami k=3-nál c3-ra, k>3 esetén minden pozitív egész c-re igaz), akkor
nc+k(k-1)nc<1,  tehátTnc+1<Tnc.
Ezzel a feladat állítását igazoltuk.
 

Megjegyezzük, hogy k=2-re nem igaz a feladat állítása, [n,n+1]=n(n+1) és ez növekvő n-nel állandóan növekszik.
 

Megjegyzések. 1. A lkkt-nek a megoldás elején ismertetett megadásmódja ismét az első feladathoz fűzött 3. megjegyzésben említett számelmélet alaptételéből következik.
 

2. Egy versenyző (k-1)! helyett a lényegesen kisebb [1,2,...,k-1] számot használta, de elég lett volna ehelyett a k-nál kisebb prímek szorzatát venni, amint azt könnyen beláthatja az olvasó. Összehasonlításul már k=21-re (k-1)! felette van a 4700 billiónak, [1,2,...,k-1] közel 233,3 millió, a prímek szorzata pedig valamivel 9,7 millió alatt van.
 

II. Megoldás. Megkaphatjuk az [n,n+1,...,n+k-1] lkkt-t úgy is, hogy az n(n+1)...(n+k-1) szorzatot elosztjuk bizonyos számokkal, tehát
[n,n+k,...,n+k-1]=n(n+1)...(n+k-1)vn,k(2)
alakban, ahol vn,k természetes szám.
Mielőtt ennek helyességét belátnánk, nézzük meg, hogyan alakul ennek felhasználásával a feladat állításában szereplő egyenlőtlenség. A megfelelő kifejezéseket beírva, kézenfekvő átalakításokkal az
nvn+1,k>(n+k)vn,k
vagy
n(vn+1,k-vn,k)>kvn,k(3)
adódik. A bal oldalnak pozitívnak kell lennie, amihez
vn+1,k>vn,k(4)
szükséges. Ha ez fennáll, akkor az utolsó egyenlőtlenség bizonyosan teljesül, ha maga n nagyobb a jobb oldalnál, mert a szorzója legalább 1.
 

Ezek alapján a feladat állítása következik abból, ha megmutatjuk, hogy
 

a) Minden adott k-ra vn,k egy csak k-tól függő korlátnál nem nagyobb, és
b) ha k3, adott, akkor vn,k értéke végtelen sokszor változik.
 

Valóban a b) szerinti változás nem lehet valamilyen határon túl mindig csökkenés, hiszen vn,k-nak mindig pozitív egésznek kell lennie, de nem lehet valamilyen értéken túl mindig növekedés sem, hiszen akkor vn,k minden korláton túlnőne, ami a) miatt nem lehet. Van tehát végtelen sok olyan n, amelyre (4) teljesül.
Legyen V egy olyan érték, aminél vn,k sohasem nagyobb, akkor mindazokra az n-ekre, amikre (4) teljesül és amelyek kV-nél nagyobbak, igaz, hogy
n(vn+k-1-vn,k)>kVkvn,k,
tehát teljesül (3), abból pedig a feladat állításában szereplő egyenlőtlenség ekvivalens átalakításokkal következik.
A feladat állításának bizonyításához tehát elég a (2) alakú előállítás létezését bizonyítani (egész nevezővel) és a nevező a) és b) tulajdonságát.
A (2) felbontáshoz eljuthatunk úgy, hogy leírjuk egyenként a számláló tényezőit és n+j leírása után (1jk-1) nézzük annak prímszámhatványok szorzatára bontott alakját. Ha van a prím alapok közül valamelyiknek korábban is többszöröse, akkor veszünk egy olyan n+i(0i<j) tényezőt, amelyik az illető prím legnagyobb hatványával osztható, és ha ez a hatvány nem nagyobb az (n+j)-ben szereplő hatványnál, akkor a nevezőbe írjuk, különben az (n+j)-ben fellépő hatványt írjuk a nevezőbe. Világos, hogy így a k-adik lépésben megkapjuk a keresett lkkt-t. vn,k a nevezőbe került prímhatványok szorzata.
A nevezőbe írt prímszámhatvány osztója (n+i)-nek is, (n+j)-nek is, tehát a különbségüknek j-i-nek is, ami pozitív és nem nagyobb j-nél. Az n+j sorravételénél tehát a j, j-1, ..., 2 bizonyos prímszámhatvány osztóival osztunk, tehát összességében nem nagyobb számmal, mint j! Ezt j=1,2,...,(k-1)-re alkalmazva kapjuk, hogy
vn,k2!3!...(k-1)!,
vn,k csak véges sok értéket vesz fel.* Ezzel beláttuk a (2) alakú felbontás létezését és az a) állítást. Igazoljuk még b)-t.
Világos, hogy vn,2=1 minden n-re.
Legyen p egy k-nál kisebb prímszám, amelyik nem osztója k-nak. ‐ Ilyenek pl. a k-1(2) prímosztói. ‐ Válasszuk n-et úgy, hogy n+k többszöröse legyen p-nek, és vizsgáljuk p kitevőjét vn,k és vn+1,k prímhatványok szorzatára bontott alakjában.
Nem lehet n is többszöröse p-nek, mert különben az (n+k)-n=k is osztható volna p-vel, ellentétben p választásával.
Mivel p<k, van többszöröse az n+1, n+2, ..., n+k-1 számok közt. Ha áttérünk [n,n+1,...,n+k-1]-ről [n+1,...,n+k-1,n+k]-ra, akkor a (2) jobb oldalának számlálójából elmarad a p-vel nem osztható n tényező és megjelenik a p-vel osztható n+k. Világos, hogy n elhagyása a p kitevőjét nem befolyásolja, viszont n+k hozzávétele után az előállításra vonatkozó gondolatmenetet követve látható, hogy a nevezőbe kell írnunk p-nek valamilyen hatványát. vn+1,k tehát p-nek magasabb hatványával osztható, mint vn,k, s így (függetlenül esetleges egyéb különbségektől) különböző számok, mivel a számok prímhatványokra történő felbontása lényegében egyértelmű.
 

Megjegyzések. 1. Az I. megoldás során több módon is megadtunk adott k-hoz végtelen sok olyan n értéket, amire teljesül a Tn<Tn+1 egyenlőtlenség, de távolról sem adtuk meg az összes ilyen n-et. Ez reménytelenül nehéz feladatnak is látszik. * Belátható, hogy a legkisebb n is, ami ott adódik, sokkal nagyobb k-nál.
Jelöljük nk-val adott k-hoz a legkisebb olyan n-et, amire teljesül a Tn<Tn+1 egyenlőtlenség. Néhány értéket a következő táblázat mutat:
 


|k234567891011121314151629303132210nk-5579811111113131716171731473237237
 

Láthatólag ezek az értékek alig nagyobbak k-nál. Az világos, hogy nk-nak k-nál nagyobbnak kell lennie, mert ha nk, akkor az n+1,...,n+k között van n-nel osztható, hiszen 2nn+k. Így [n+1,...,n+k] osztható n-nel, és természetesen n+1,...,n+k-1-gyel is, tehát [n,...,n+k-1] osztója [n+1,...,n+k]-nak, amiből következik, hogy nem lehet az előbbi nagyobb.
A prímszámok eloszlására vonatkozó mély tételek segítségével belátható, hogy nk/k tetszés szerinti 1-nél nagyobb h számnál kisebb lesz, amint k egy alkalmas (h-tól függő) korlátnál nagyobb.
2. Számolás közben sok olyan n-re találunk, amelyre [n,...,n+k-1]=[n+1,...,n+k]. Ez n=k-ra pl. csak akkor nem teljesül, ha k a 2-nek egy hatványa. De k=19-re pl. n=19-től n=22-ig négy egymás utáni értékre teljesül az egyenlőség, k=210-re, pedig n=213-tól n=220-ig nyolc egymás utáni esetben. Ezek után első pillanatra talán meglepően hat, hogy minden k-hoz legfeljebb véges sok esetben lehet két szomszédos lkkt egyenlő, pedig a (2) formula alapján ez legfeljebb az
n=kvn,kvn+1,k-vn,k
értékekre teljesül (és közülük az egész értékekre teljesül is). Mivel pedig vn,k csak véges számú különböző értéket vehet fel, így csak véges számú megfelelő n létezik.

*Ezt a szorzatot "k-1 faktoriális"-nak nevezik és így jelölik: (k-1)!

*Belátható, hogy az is igaz, hogy vn(k-1)! pontosabban vn,k|(k-1)!, és az egyenlőtlenségben végtelen sokszor az "='' jel érvényes.

* Figyeljük meg, hogy a II. megoldás csak végtelen sok ilyen n létezését bizonyítja, anélkül, hogy megadna ilyen n-eket. Annak a gondolatmenetnek az alapján csak a vn,k nevezők szerkezetének sokkal pontosabb ismerete tenné lehetővé ilyen n-ek megadását.