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. Di Giovanni Márk megoldása. Lássuk be a feladat általánosítását, azaz összértékű érmékre és dobozra, teljes indukcióval (-ra a feladat állítását kapjuk). -re az állítás triviális, mert az összes érmét berakhatjuk egyetlen dobozba. Tegyük fel most, hogy -ig igaz az állítás () és lássuk be -re. Ha van néhány érme, amelyek összértéke 1, akkor azokat berakhatjuk az első dobozba, ezzel visszavezetve az -es esetre, amit már beláttunk. Tehát mostantól feltehetjük, hogy nincsenek ilyen érmék. Továbbá ha van kettő darab értékű érménk, akkor azokat lecserélhetjük egy darab értékű érmére, mivel ha így el tudjuk végezni az elhelyezést, akkor az eredeti érméket is el tudjuk helyezni. Tehát feltehetjük, hogy minden páros nevezőjű érméből legfeljebb 1 darab van. Rakjuk bele a dobozokba az érméket mohó algoritmussal, azaz vesszük a legnagyobb, addig nem elhelyezett érmét és belerakjuk az egyik dobozba (mint majd kiderül, lényegtelen, hogy melyikbe). Ha ezzel az algoritmussal sikerült elhelyezni az összes érmét, akkor készen vagyunk és az állítást beláttuk. Ha nem, akkor elakadtunk egy értékű érménél. Eddig a dobozokban csak olyan érmék szerepelhetnek, amelyek legalább értékűek (a mohó algoritmus miatt). Továbbá minden dobozban a kimaradt hely kisebb mint , különben oda be tudnánk rakni még legalább egy kimaradt érmét. Legyen az üres hely mérete az -edik dobozban . Ekkor . Továbbá | | Az utolsó egyenlőtlenség azért teljesül, mert az összes érme értékösszege legfeljebb , így a dobozokban lévő érmék értékösszege meg az -s érmének az összege is legfeljebb . Ebből adódik: azaz , de mivel egész, ezért . Rakjuk bele az eddigi dobozokban lévő érméket értékeik szerint a következő táblázatba (egy mezőre akár több érme is kerülhet):
Nyilvánvalóan mivel ezért a táblázatba kerülő legkisebb elem legalább értékű. Most nézzünk meg egy sort: az első mező kivételével minden mező nevezője páros, feltevésünk szerint tehát legfeljebb 1 érme lehet rajta. Vizsgáljuk meg az értékösszeget abban a sorban, ahol az első mező . A mezők összértéke az első mezőt leszámítva legfeljebb akkora, mint a mezőkön lévő számok összege (hiszen minden mezőn legfeljebb egy érme lehet). Ez az összeg pedig biztosan kisebb, mint annak a végtelen mértani sornak az összege, melynek első néhány eleme szerepel a mezőkön. Tehát | | Az első mezőn legfeljebb darab érme lehet, különben ki lehetne választani közülük darabot, melyek összege 1. Így az értékösszeg a sorban biztosan kisebb, mint Mivel ezt a gondolatmenetet elvégezhetjük az összes sorra, ezért minden sorösszeg kisebb, mint 1. Mivel a táblázat darab sorból áll, így a táblázatban lévő érmék összértéke kisebb, mint . Innen | | Ekkor , azaz . Adjuk össze újra az érméket a táblázatos módszerrel, viszont most csak -ig tartanak a sorok (vagy -ig, paritásától függően.) Így a táblázatban lévő érmék értékösszege kisebb, mint , azaz | | azaz 1/b nagyobb, mint . Ebből az következik, hogy , azaz egy 1 értékű érménél akadunk el. De korábban már feltettük, hogy semelyik néhány érmének az összege sem 1, így nincsen 1 értékű érménk sem, tehát ellentmondásra jutottunk. Tehát a pakolással nem tudunk elakadni, azaz működik a módszer, így beláttuk -re is. Ezzel beláttuk az indukciós lépést, így minden -re igaz az állítás, azaz speciális esetként -ra is. |