Feladat: B.3996 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Cséke Balázs ,  Éles András ,  Farkas Ádám László ,  Grósz Dániel ,  Kunos Ádám ,  Kunovszki Péter ,  Szalóki Dávid ,  Szőke Nóra ,  Szűcs Gergely ,  Varga László ,  Wolosz János 
Füzet: 2007/december, 541 - 542. oldal  PDF file
Témakör(ök): Konstruktív megoldási módszer, Egyéb sokszögek geometriája, Feladat
Hivatkozás(ok):Feladatok: 2007/április: B.3996

Van egy téglalap alakú papírlapunk. Ebből húszszögeket szeretnénk előállítani a következő eljárással. Minden lépésben kiválasztunk egy darab papírt (ez kezdetben csak a kiinduló papírlap lehet), és azt egy egyenes vonal mentén kettévágjuk. Ezt az eljárást folytatva, legalább hány vágásra van szükség, hogy legalább száz darab húszszöget kapjunk?

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. A téglalapot először oldalával párhuzamosan két téglalapra vágjuk szét. Ezután az egyik darabot hasonlóan két téglalapra vágjuk szét. Ezt addig folytatjuk, amíg 100 darab téglalap lesz. Mivel minden vágással 1 újabb téglalap keletkezik, és kezdetben egy téglalapunk volt, így ehhez összesen 99 vágás szükséges.
Ha a téglalap egy csúcsát levágjuk úgy, hogy egy háromszög jöjjön létre, akkor a megmaradó darab egy ötszög lesz. Ennek újabb csúcsait levágva, a csúcsok száma mindig eggyel nő. Így egy négyszögből húszszöget 16 vágással készíthetünk, vagyis 100 négyszög húszszöggé alakításához 10016=1600 vágás kell. Tehát összesen 99+1600=1699 vágással a 100 db húszszög létrehozható.
Most megmutatjuk, hogy 1699 vágásnál kevesebb nem elegendő. Egy, a feltételnek megfelelő általános felvágás után legyen a vágások száma: v, a létrejött sokszögek összes csúcsainak száma: c, és a 100 db húszszögön kívül létrejövő sokszögek száma: m. Mivel minden vágással egy új sokszög jön létre, kezdetben volt egy téglalapunk és összesen 100+m sokszög van, így 100+m=v+1, azaz 99=v-m. 100 db húszszögnek összesen 20100=2000 csúcsa van, a többi sokszög mindegyike legalább háromszög, tehát azoknak összesen legalább 3m csúcsa van. Tehát az összes sokszög összes csúcsainak száma c2000+3m.
Amikor egy sokszöget elvágunk, új csúcsok keletkeznek. Ahol egy vágás csúcson halad át, ott eggyel nő a csúcsok száma, ahol egy oldal belső pontján halad át, ott két új csúcs keletkezik. Mivel egy vágás két helyen metszi egy sokszög kerületét, ezért legfeljebb 4-gyel nőhet a csúcsok száma minden vágással.
Kezdetben 4 csúcsa volt a téglalapnak. Ez v vágás után legfeljebb 4v-vel nőhet, azaz c4+4v.
A fenti két egyenlőtlenségből: 2000+3mc4+4v, vagyis

2000+3m4+4v,amiből1996v+3(v-m).
De v-m=99, így 1996v+399, azaz 1699v. Tehát legalább 1699 vágás szükséges 100 db húszszög előállításához.