Feladat: B.3953 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Fonyó Dávid ,  Mészáros András ,  Nagy Dániel 
Füzet: 2008/március, 148 - 150. oldal  PDF  |  MathML 
Témakör(ök): Esetvizsgálat, Valós számok és tulajdonságaik, Feladat
Hivatkozás(ok):Feladatok: 2006/december: B.3953

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 100 valós szám mindegyike nem lehet negatív, mivel ekkor összegük is negatív lenne, nem pedig 0. Ha a 100 valós szám között 99 negatív szám van, akkor a 100. szám biztosan pozitív, hiszen csak így lehet a számok összege 0. Ekkor a kéttagú összegek között pontosan 99 pozitív van, mégpedig azok, amelyeknek az egyik tagja a pozitív szám.
A továbbiakban megmutatjuk, hogy a 100 szám között a negatívok számát változtatva nem kaphatunk 99-nél kevesebb kéttagú nemnegatív összeget.
Ha a 100 szám között k db nemnegatív szám van, akkor ezek páronkénti összeadásából k(k-1)2 darab (szükségképpen nemnegatív) összeg adódik. Ha k≥15 (k∈N+), akkor ez a szám legalább 15⋅142=105>99. Így elég a k≤14 esettel foglalkozni.
Jelöljük a nemnegatív számokat n1,n2,...,nk-val, a negatívokat pedig m1,m2,...,m100-k-val; k≤14 miatt kevesebb nemnegatív szám van, mint negatív. Azokat a kéttagú összegeket, amelyek egy nemnegatív és egy negatív számból állnak, rendezzük egy k×(100-k)-as táblázatba az alábbi módon:

n1+m1n1+m2...n1+m100-kn2+m2n2+m3...n2+m1⋮⋮nk+mknk+mk+1...nk+mk-1


Ha az azonos oszlopban álló kéttagú összegeket összeadjuk, akkor megkapjuk a nemnegatív és a negatív számok egy részének az összegét. Minden oszlopbeli összeg pozitív, hiszen a 100 szám összege 0, amiből 100-2k db negatív tagot elhagyva a visszamaradó összeg pozitív lesz. Így minden oszlopban van legalább egy pozitív kéttagú összeg, vagyis összesen legalább
k(k-1)2+100-k=(k-1,5)2+197,752
nemnegatív összegünk van. A 0≤k≤100, k∈N feltétel esetén a kifejezés k=1 vagy k=2 esetén veszi fel a minimumát, mindkét helyen a minimum értéke 99.
Tehát legalább 99 olyan pár választható ki a 100 számból, amelyben a számok összege nemnegatív.
 

A továbbiakban arra adunk többféle bizonyítást, hogy a nemnegatív összeget adó párok száma legalább 99.
 
II. megoldás. Jelöljük a 100 számot A0,A1,...,A99-cel. Soroljuk őket 99 féle módon 50‐50 párba úgy, hogy az egyes besorolásokban lévő párok mindegyike különböző legyen. Ha egy besorolásban az egyes párokban szereplő számok összegét összeadjuk, akkor 0-t kapunk, vagyis biztos van egy számpár ebben a besorolásban, amiben a számok összege nemnegatív. Így mind a 99 besorolásban van egy ilyen pár, és mivel minden pár különböző, azért van legalább 99 ilyen számpár.
A következőkben mutatunk egy konstrukciót a 99 különböző besorolásra, melyben minden pár csak egyszer fordul elő.
 
 

Az első besorolást az ábra mutatja, az egy oszlopban lévő számok tartoznak egy párba. A következő besorolást úgy kapjuk, hogy az egyes számokat a nyilak mentén eltoljuk eggyel. Minden besorolásból ugyanazen a módon kapjuk a következő besorolást. Egyértelmű, hogy A0-nak mind a 99 besorolásban más párja lesz (A1, A99, A98, A97, ..., A4, A3, végül A2). Igaz ez A1-re is, melynek párjai: (A0, A98, A96, ..., A4, A2, A99, A97, A95, ..., A5, A3); illetve igaz lenne akkor is, ha más elem indulna az A1 pozíciójáról. Mivel pedig a besorolások 99-es ciklusonként ismétlődnek, azért mindegy, hogy melyik besorolást tekintjük elsőnek. Tehát bármely elem indulhatna az A1 pozíciójáról. Vagyis minden elemre igaz, hogy mind a 99 besorolásban más párt kap.
Tehát legalább 99 olyan pár választható ki, amelyben a számok összege nemnegatív.
 
Megjegyzés. Néhányan a KöMaL 2006/9. számában megjelent cikkre1 hivatkoztak a 99-féle párosítás megalkotásakor. (A feladat ugyanabban a számban került kitűzésre.)
 
III. megoldás. Legyen a1,a2,...,a100 a 100 adott szám egy sorrendje úgy, hogy a1≥a2≥a3≥...≥a100.
Tekintsük az alábbi összegeket: a1+a100, a2+a99, ..., ai+a101-i, ..., a50+a51. A fenti 50 kéttagú összeg összege egyben az összes szám összege, vagyis 0. Tehát a kéttagú összegek között van nemnegatív. Legyen ax+a101-x (x∈{1,2,...,50}) egy ilyen összeg.
Azok a kéttagú összegek, melyek egyik tagjának indexe legfeljebb x, másik tagjának indexe pedig legfeljebbb 101-x, nagyobbak vagy egyenlőek, mint ax+a101-x. Így ezek az összegek szintén nemnegatívok. Számoljuk meg ezeket a számpárokat. Az első tag x-féle, a második tag (101-x)-féle lehet. Nem kell számolnunk azokat a párokat, amelyekben ugyanazt a számot választanánk kétszer, és ‐ mivel egyébként kétszer vennénk őket számításba ‐ le kell vonnunk azon pároknak a számát, amelyek mindkét tagjának indexe legfeljebb x. A megfelelő párok száma tehát
x(101-x)-x-x2-x2=x(100+12-32x).
Ennek a kifejezésnek az értéke x=1 esetén 99, x≥2 esetén pedig 100+12-32x≥50 miatt legalább 100. Ezek szerint a nemnegatív összegű számpárok száma legalább 99.
1Kiss György: Hogyan szervezzünk körmérkőzéses focibajnokságot? KöMaL, 2006/9., 514‐525.