Feladat: Gy.2633 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Imreh Csanád ,  Matolcsi Máté 
Füzet: 1991/április, 157 - 158. oldal  PDF file
Témakör(ök): Konstruktív megoldási módszer, Gyakorlat
Hivatkozás(ok):Feladatok: 1990/május: Gy.2633

Egy levélre n forint értékű bélyeget kell ragasztani (n pozitív egész szám). Van k darab egész értékű bélyegünk, összértékük 2k forintnál kevesebb, de legalább n. Bizonyítsuk be, hogy kiválasztható néhány bélyeg, amelynek összértéke pontosan n.

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.

Megoldás. Nyilván elég az olyan esetekkel foglalkozni, ha bélyegeink között van 1-nél nagyobb értékű. Legyen egy ilyen címlet d. Osszuk két csoportra a bélyegeket, egyikbe kerüljön ez a d értékű bélyeg és az 1 értékű bélyegek, a másikba pedig az összes többi. Mivel a második csoportban minden bélyeg értéke legalább 2, ebben a csoportban a bélyegek átlagos értéke is legalább 2. Ez azt jelenti, hogy az első csoportban a bélyegek átlagos értéke kisebb kell legyen 2-nél, és így legalább d-1 darab 1-es címletű bélyegnek kell lennie. Különben mivel d2, legfeljebb d-2 darab 1-essel az első csoport átlaga legalább

d+(d-2)1d-1=2.

 

Legyen ezután n egy megadott szám, amely tehát legfeljebb akkora, mint a bélyegek együttes értéke. Rendezzük bélyegeinket érték szerint csökkenő sorba, és ragasszunk fel sorban a borítékra közülük annyit, hogy még éppen ne lépjük túl az előírt n értéket. Ha valamennyi bélyeget felragasztottuk, akkor nyilván készen vagyunk, és akkor is, ha éppen elértük n -et. Ha nem ez a helyzet ‐ vagyis a felragasztott bélyegek összértéke n-nél kisebb, másfelől a soron következő d1 értékű bélyeg fölragasztásával már túllépnénk ezt az értéket ‐ akkor a d1 nyilván nagyobb 1-nél, egyébként ugyanis még ezt is fel tudnánk ragasztani. Mivel ezt a bélyeget felragasztva már n- nél nagyobb értéket kapunk, így a hiány kisebb d1 nél. Láttuk viszont, hogy van legalább d1-1 darab 1-es címletű bélyegünk, és ezekből eddig egyet sem használtunk el, ezért közülük alkalmas számút ‐ legfeljebb (d1-1)-et ‐ felragasztva megkapjuk a kívánt n értéket.
 

Megjegyzés. Az átlagra vonatkozó előírás nyilván nem enyhíthető, hiszen ha a bélyegek átlagos értéke elérheti a 2 Ft-ot, akkor ez lehetséges úgy, hogy minden egyes bélyeg értéke pontosan 2 Ft, és így a páratlan portódíjak közül egy sem rakható ki.