Feladat: B.3985 Korcsoport: 14-15 Nehézségi fok: átlagos
Füzet: 2008/január, 28 - 29. oldal  PDF  |  MathML 
Témakör(ök): Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 2007/március: B.3985

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. Igen, megoldható. Mutatunk erre egy módszert.
Először válasszuk ki azokat a fűszálakat, amelyek magasabbak az átlagnál, és vágjuk le őket átlag hosszúra. A levágott feleslegeket ragasszuk össze egyetlen szállá, majd daraboljuk föl akkora részekre, amekkorák az átlagnál rövidebb fűszálakhoz hiányoznak. Ez megtehető, mert a hosszabbak feleslegeinek összege egyenlő a rövidebbek hiányainak összegével az átlag tulajdonsága miatt. Végül ragasszuk ezeket a megfelelő rövid fűszálakra. Így minden fűszál átlag hosszú lesz, és először annyi vágást végzünk, amennyi hosszú fűszál van, majd eggyel kevesebbet, mint amennyi rövid van. Ez összesen legfeljebb n-1 vágást jelent.

 
II. megoldás. Az általánosság megszorítása nélkül feltehetjük, hogy a fűszálak összhossza n, vagyis minden fűszálat egységesen egység hosszúra szeretnénk nyírni. Hogy a fűnyírás mindig megtehető a feladatban leírt módon, n szerinti teljes indukcióval igazoljuk. Ha n=1, akkor az állítás nyilvánvaló. Ha n≥2, és n-1 esetén már igazoltuk az állítást, akkor eljárásunk legyen a következő. Válasszuk ki a(z egyik) leghosszabb fűszálat. Ha ez pontosan 1 hosszú, akkor minden fűszál 1 hosszú, vagyis egyetlen vágásra sincs szükség. Ellenkező esetben vágjuk le a fűszálat átlag hosszúra, a levágott részt pedig ragasszuk hozzá képzeletben bármelyik másik fűszálra. Így a már levágott fűszálon kívül megmaradt n-1 fűszál összhossza n-1, tehát azokat legfeljebb n-2 vágással mind egység hosszúra nyírhatjuk.