A B. 3985. feladat (2007. március)

B. 3985. Kertünkben a gyep n fűszálból áll. Úgy szeretnénk lenyírni a füvet, hogy minden fűszál egyenlő hosszú legyen, de a fűszálak összhossza ne változzék. Összesen a fűszálakon n-1 vágást végezhetünk, és a levágott darabokat egymáshoz, illetve a megmaradt részekhez ragaszthatjuk. Megoldható-e mindig a kívánalmaknak megfelelően a fűnyírás?

(4 pont)

A beküldési határidő 2007. április 16-án LEJÁRT.

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 ez mindig megtehető a feladatban leírt módon, azt n szerinti teljes indukcióval igazoljuk. Ha n=1, akkor az állítás nyilvánvaló. Ha n2, é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 egység hosszú, vagyis egyetlen vágásra sincs szükség. Ellenkező esetben vágjuk le a fűszálat 1 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.

Statisztika:

124 dolgozat érkezett.
4 pontot kapott:	76 versenyző.
3 pontot kapott:	34 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.
Nem versenyszerű:	6 dolgozat.

A KöMaL 2007. márciusi matematika feladatai