Kezdőlap


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 \| MathML
Témakör(ök):	Konstruktív megoldási módszer, Gyakorlat
Hivatkozás(ok):	Feladatok: 1990/május: Gy.2633

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 $d ≧ 2,$ legfeljebb $d - 2$ darab 1-essel az első csoport átlaga legalább

\begin{matrix} \frac{d + (d - 2) \cdot 1}{d - 1} = 2. \end{matrix}

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ő

d_{1}

értékű bélyeg fölragasztásával már túllépnénk ezt az értéket ‐ akkor a

d_{1}

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

d_{1}

nél. Láttuk viszont, hogy van legalább

d_{1} - 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

(d_{1} - 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.