Feladat: B.4281 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Damásdi Gábor ,  Dudás Zsolt 
Füzet: 2011/február, 91 - 93. oldal  PDF  |  MathML 
Témakör(ök): Feladat, Egész számok összege, Teljes indukció módszere
Hivatkozás(ok):Feladatok: 2010/május: B.4281

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 gondolt számok között nem szerepelhet a nulla, hiszen az ebből képezett egytagú összeg is nulla lenne. A megadott 2n-1 darab szám növekvő sorrendben legyen

a1a2a3...a2n-1;
itt a1 a gondolt számok közül az összes negatívnak az összege ‐ ha volt köztük negatív, vagy, ellenkező esetben, a legkisebb gondolt szám, ami ilyenkor szükségképpen pozitív. Mivel az utóbbi esetben éppen a B. 4249. feladat speciális esetét kapjuk feltehető, hogy az első eset áll fenn, azaz a1<0. Legyen bi=|a1-ai|, ha i=2,3,...,2n-1, illetve legyen b1=a1. A b1,b2,...,b2n-1 számok éppen a gondolt számok abszolút értékeiből képezett összegek, ezért az említett feladat megoldása szerint azok egyértelműen meghatározhatók. Ezután megmutatjuk, hogy nem csak a gondolt számok abszolút értékei, hanem maguk a gondolt számok is egyértelműen megkaphatók, azaz nincs két olyan különböző szám n-es, amelyhez ugyanazok az ai értékek tartoznának. Tegyük fel, ezzel ellentétben, hogy létezik két ilyen n-es, A és B; mint láttuk, ezek egymástól eltérő tagjai csupán előjelükben különböznek. Legyen m az ilyen elemeknek a száma. Jelölje az m darab eltérő, A-beli elem közül a negatívak összegét α, a B-beli megfelelő negatívak összegét β. Mivel A-ban az α-β néhány ottani számnak az összege, azért α-β0, így |α||β|; legyen pl. |α|>|β|. Hagyjuk el A-ból azt az m darab elemét, amely (előjelében) eltér B megfelelő elemeitől, jelöljük a megmaradó n-m darab (nem feltétlenül különböző) szám együttesét A'-vel. Az A'-beli számokból képezhető legnagyobb összeg (az összes benne szereplő pozitív szám összege) a2n-1-β. Hasonlóan kapjuk, hogy B-ből elhagyva az m darab eltérő számot, a megmaradt B' ,,halmaz'' elemeiből képezhető legnagyobb összeg a2n-1-α>a2n-1-β. Ellentmondást kaptunk, hiszen A' nyilvánvalóan azonos B'-vel.
 

Megjegyzés. A gondolt számok egyértelműségének fenti elegáns indirekt bizonyítása nem ad közvetlen eljárást e számok meghatározására (kivéve azt a kizárt esetet, amikor a számok pozitívak). A következő megoldás viszont éppen egy ilyen eljárás megadásával oldja meg a feladatot.

 
II. megoldás. Tekintsük úgy a feladatot, hogy egy n-elemű halmaz részhalmazaiban lévő elemek összegeiből akarjuk a halmazt visszafejteni. Az üres halmaznak megfelelő összeg legyen a nulla.
A legnagyobb összeg biztosan az összes pozitív elem összege. Mi lehet a második legnagyobb összeg? Ez kétféleképpen jöhetett létre attól függően, hogy milyen szám abszolút értéke a legkisebb.
Ha egy pozitív szám abszolút értéke a legkisebb, akkor a második legnagyobb összeg úgy jött létre, hogy összeadtuk a pozitívakat a legkisebb kivételével. Ha egy negatív szám abszolút értéke a legkisebb, akkor a második legnagyobb összeget úgy kapjuk, hogy összeadjuk a pozitívakat, és még a legnagyobb negatív számot is hozzájuk adjuk. Ebből adódik, hogy a két legnagyobb összeg különbsége biztosan az egyik szám ‐ a legkisebb abszolút értékű szám ‐ abszolút értéke; legyen ez a szám p. A részhalmazok párba állíthatók úgy, hogy két, párba állított részhalmaz csupán abban kükönbözik, hogy az egyikben benne van p, a másikban pedig nincs. (Az üres halmazhoz az egyelemű {p} részhalmaz fog tartozni.) Ennek alapján az összegek is párba állíthatók úgy, hogy a párok tagjainak különbsége mindig p abszolút értéke legyen. Az összegek e megfelelő párbaállítását kezdetben nem látjuk ugyan, de ‐ mivel véges sok szám van ‐ az összes párbaállítások száma is véges. Ezért meg tudjuk találni az összes olyan párbaállítást, amelynél a párok tagjainak különbsége p abszolút értéke. Mivel az üres halmazhoz a {p} részhalmaz tartozott, a 0 párja p lesz. Tehát ezzel a módszerrel nem csupán p abszolút értékét, hanem magát a p-t (az előjelével együtt!) is meg tudjuk határozni. Minden összegnek egyértelműen megkapjuk a párját: a legnagyobb S1 összeg párja S2=S1-|p|, a csökkenő sorrendben ezután következő S3 párja S4=S3-|p|, és így tovább. Ha p>0, akkor pontosan az S2, S4, ... összegek tartoznak a p-t nem tartalmazó részhalmazokhoz, míg p<0 esetén az S1,S3,... összegek. Ezután már mindkét esetben csak azokat az összegeket vizsgáljuk, amelyek azoknak a részhalmazoknak felelnek meg, amelyekben nincs benne p. Ezzel visszajutottunk az eredeti feladathoz, de a gondolt számok száma eggyel csökkent.