Feladat: Gy.1982 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Beke S. ,  Bocsák B. ,  Böröczky L. ,  Csillag P. ,  Csúri Piroska ,  Engländer J. ,  Fáth G. ,  Hetyei Judit ,  Horváth 149 Z. ,  Horváth 290 P. ,  Kántor Cs. ,  Kocsis 164 Csilla ,  Kollár P. ,  Lampl Gy. ,  Lenzsér P. ,  Magyar Ákos ,  Megyesi Gábor ,  Melis Z. ,  Miszori I. ,  Mócsy M. ,  Náray M. ,  Strausz Gy. ,  Szabó 741 Z. ,  Szederkényi Edit ,  Takács G. ,  Tóth 360 G. ,  Törőcsik J. ,  Vindics I. 
Füzet: 1982/április, 157 - 160. oldal  PDF file
Témakör(ök): Egyenlőtlenségek, Legkisebb közös többszörös, Gyakorlat
Hivatkozás(ok):Feladatok: 1981/május: Gy.1982

Legyenek 1a<b<c<d<e egész számok. Bizonyítsuk be, hogy
1[a,b]+1[b,c]+1[c,d]+1[d,e]<1,
ahol [x,y] a két szám legkisebb közös többszörösét jelöli.

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. Ha 1x<y, akkor [x,y] legalább kétszer akkora, mint x, emiatt 1[x,y]12x. Ezt felhasználva a bizonyítandó egyenlőtlenség bal oldala felülről becsülhető :

1[a,b]+1[b,c]+1[c,d]+1[d,e]12a+12b+12c+12d.

Ha c4, akkor d>c miatt d5, másrészt a1 és így b2, tehát
12a+12b+12c+12d12+14+18+110,
ami valóban kisebb 1-nél.
Ha c<4, akkor a=1, b=2 és c=3, tehát d4. Ekkor
1[a,b]+1[b,c]+12c+12d12+16+16+18<1,
tehát ebben az esetben is beláttuk az állítást.
 

Magyar Ákos (Budapest, Fazekas M. Gyak. Gimn., I. o. t.)
 

II. megoldás. Egy jobb becsléssel elkerülhető az esetszétválasztás. Mivel [x,y] az x-nek is és az y-nak is többszöröse, ezért xy-nak y[x,y] és x[x,y] is többszöröse. Emiatt e két utóbbi szám különbsége is többszöröse xy-nak. Ha tehát ez a különbség nem 0, akkor az abszolút értéke legalább xy. Így ha 0<x<y, akkor
y[x,y]-x[x,y]xy,
ahonnan [x,y]xy-nal való osztás után azt kapjuk, hogy
1x-1y1[x,y].(2)
Ezt alkalmazva
1[a,b]+1[b,c]+1[c,d]+1[d,e](1a-1b)+(1b-1c)+(1c-1d)+(1d-1e)=1a-1e


adódik, ami valóban kisebb, mint 1.
 

Megyesi Gábor (Szeged, Juhász Gy. Tanárképző Főisk. I. sz. Gyak. Isk., 8. o. t.)

 

Megjegyzések. 1. A feladatra nagyon sok hibás dolgozat érkezett. Ezek legtöbbjében egy, a kitűzöttnél élesebb ‐ egyébként igaz ‐ állítás "bizonyítása'' szerepelt. Eszerint a bal oldal maximuma 1-116. Gondolatmenetük lényegében a következő volt :
Mivel 1[x,y]12x, így 1[a,b]12; az első tag tehát akkor maximális, ha a=1 és b=2. Ekkor 1[b,c]=1[2,c]14 és ez is csak akkor lehetséges, ha c=4. Ha c=4, akkor 1[c,d]18 és így d=8, és ugyanígy e=16, a bal oldal maximuma tehát 12+14+18+116=1-116.
 

Ez a gondolatmenet hibás, bár az eredmény igaz. Ha valamit több lépésben kell maximalizálnunk, akkor nem feltétlenül akkor kapjuk a legjobb eredményt, ha minden lépésben az akkor lehetséges legnagyobb növekedést igyekszünk elérni. Esetünkben kimondatlanul feltételeztük, hogy a bal oldal akkor maximális, ha már az első tag is a lehető legnagyobb. Ez a és b értékét meghatározza, ha most megint "a lehető legtöbbet akarjuk'', akkor ez c-t is egyértelművé teszi, és így tovább. Lehetséges azonban, hogy ha eleinte túl mohók vagyunk, az a későbbiekben nagyon megköti a kezünket.
Egy nyilvánvaló példa a fentiek illusztrálására az alábbi. Tegyük fel, hogy két nemnegatív szám összege 1, és a szorzatukról szeretnénk elérni, hogy a lehető legnagyobb legyen. Az első tényező nyilván akkor a legnagyobb, ha 1, de így a második tényező már csak 0 lehet, és a szorzat láthatóan nem lesz maximális.
Egy másik példához jutunk, ha az eredeti feladatot kissé módosítjuk. Az idézett rossz megoldásokban azt "igazolták'', hogy a feltételek esetén
1[a,b]+1[b,c]+1[c,d]+1[d,e]
akkor maximális, ha a=1, b=2, c=4, d=8 és e=16. Ha ehelyett
1[a,b]+1[b,c]+1[c,d]+1[d,e](3)
maximumát keressük, akkor az idézett "megoldás'' szerint
12+14+18+116=1,81066
adódik, ez azonban most nem maximum, mert ha a=1, b=2, c=3, d=6, e=12, akkor (3) értéke
12+16+16+112=1,81228.

Jól látható, hogy az összeg második tagja csökkent, de ennek révén a harmadik és a negyedik tagot növelhettük, úgy, hogy az összeg meghaladja az előző értékét.
2. Említettük, hogy igaz egy élesebb állítás is. Ezt be is látjuk n számra (n2), n-re vonatkozó teljes indukcióval.
Legyen tehát 1a1<a2<...<an,ai egész. Ekkor azt állítjuk, hogy
1[a1,a2]+1[a2,a3]+...+1[an-1,an]1-12n.(4)

Ha n=2, akkor ez az 1[a1,a2]12a112 becslés miatt igaz. Tegyük fel, hogy az állítás igaz n számra, és lássuk be, hogy ekkor (n+1) számra is igaz. Két esetet különböztetünk meg. 1. eset: an+1<2n+1. Ekkor a II. megoldás becslése szerint
1[a1,a2]+1[a2,a3]+...+1[an,an+1]1a1-1an+1<1a1-12n+11-12n+1.

2. eset: an+12n+1. Nyilván [an,an+1]an+1, így most 1[an,an+1]12n+1. Az indukciós feltevést felhasználva
(1[a1,a2]+1[a2,a3]+...+1[an-1,an])+1[an,an+1](1-12n)+12n+1=1-12n+1.


Ezzel az állítást beláttuk. A bizonyításból az is látszik, hogy (4)-ben pontosan akkor van egyenlőség, ha ai=2i-1, i=1, 2, ..., n.