Feladat: Gy.3193 Korcsoport: 14-15 Nehézségi fok: nehéz
Megoldó(k):  Bárány Kristóf ,  Gyenes Zoltán ,  Győri Nikolett ,  Hangya Balázs ,  Harangi Viktor ,  Juhász András ,  Kunszenti-Kovács Dávid ,  Papp Dávid ,  Patakfalvi Zsolt ,  Poronyi Gábor ,  Székelyhidi Gábor ,  Terpai Tamás ,  Végh A. László 
Füzet: 1999/január, 27 - 28. oldal  PDF  |  MathML 
Témakör(ök): Szöveges feladatok, Konstruktív megoldási módszer, Gyakorlat
Hivatkozás(ok):Feladatok: 1998/március: Gy.3193

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.

Ha az eredetileg n kupac valamelyikének l eleme volt, úgy ,,írjunk rá'' mindegyik benne lévő mogyoróra 1l-et. Ezt valamennyi kupacra elvégezve minden mogyoró pozitív számot visel, egy kupacon belül ezen számok összege 1, tehát az összes ilyen szám összege n.
Tételezzük fel ‐ a feladat állításával ellentétben ‐, hogy legfeljebb k szem mogyoró került az új elosztás során az eredetivel kisebb kupacba. Mivel az új kupacok száma n+k, azért lesz legalább n olyan (új) kupac, amelyben minden mogyoróról elmondható, hogy legalább akkora kupacba került, amekkorában eredetileg volt. Így a szóban forgó n új kupac bármelyikében a mogyorószemek által viselt számok összege legalább 1, az n új kupacban levőket összegezve pedig legalább n. Ez azonban azt jelenti, hogy a fennmaradó k új kupacban a mogyorókra írt számok összege legfeljebb nulla, ami ellentmond annak, hogy itt is csupa pozitív számot összegeztünk.

 

Megjegyzés. A (k+1)-es becslés nem javítható. Osszuk el eredetileg a mogyorókat úgy, hogy az egyik kupacba pontosan k+1 szem mogyoró kerüljön. A második szétosztás pedig csupán abban különbözzék az elsőtől, hogy a korábbi kiszemelt k+1-es kupacot k+1 darab egyelemű kupacba osztjuk szét. Ekkor pontosan ez a k+1 mogyoró kerül az eredetinél kisebb kupacba.

 Poronyi Gábor (Pécs, Janus Pannonius Gimn., 11. o.t.) és
 
 Terpai Tamás (Fazekas M. Főv. Gyak. Gimn., 11. o.t.) dolgozatai alapján