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 darab szám növekvő sorrendben legyen itt 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 . Legyen , ha , illetve legyen . A 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 -es, amelyhez ugyanazok az értékek tartoznának. Tegyük fel, ezzel ellentétben, hogy létezik két ilyen -es, és ; mint láttuk, ezek egymástól eltérő tagjai csupán előjelükben különböznek. Legyen az ilyen elemeknek a száma. Jelölje az darab eltérő, -beli elem közül a negatívak összegét , a -beli megfelelő negatívak összegét . Mivel -ban az néhány ottani számnak az összege, azért , így ; legyen pl. . Hagyjuk el -ból azt az darab elemét, amely (előjelében) eltér megfelelő elemeitől, jelöljük a megmaradó darab (nem feltétlenül különböző) szám együttesét -vel. Az -beli számokból képezhető legnagyobb összeg (az összes benne szereplő pozitív szám összege) . Hasonlóan kapjuk, hogy -ből elhagyva az darab eltérő számot, a megmaradt ,,halmaz'' elemeiből képezhető legnagyobb összeg . Ellentmondást kaptunk, hiszen nyilvánvalóan azonos -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 -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 . 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 , a másikban pedig nincs. (Az üres halmazhoz az egyelemű 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 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 abszolút értéke. Mivel az üres halmazhoz a részhalmaz tartozott, a 0 párja lesz. Tehát ezzel a módszerrel nem csupán abszolút értékét, hanem magát a -t (az előjelével együtt!) is meg tudjuk határozni. Minden összegnek egyértelműen megkapjuk a párját: a legnagyobb összeg párja , a csökkenő sorrendben ezután következő párja , és így tovább. Ha , akkor pontosan az , , összegek tartoznak a -t nem tartalmazó részhalmazokhoz, míg esetén az összegek. Ezután már mindkét esetben csak azokat az összegeket vizsgáljuk, amelyek azoknak a részhalmazoknak felelnek meg, amelyekben nincs benne . Ezzel visszajutottunk az eredeti feladathoz, de a gondolt számok száma eggyel csökkent. |