Feladat: Gy.2448 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1989/február, 66 - 67. oldal  PDF  |  MathML 
Témakör(ök): Egyéb feladványok, Különleges függvények, Terület, felszín, Téglalapok, Négyzetek, Teljes indukció módszere, Gyakorlat
Hivatkozás(ok):Feladatok: 1987/december: Gy.2448

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. Megmutatjuk, hogy legalább 6 vágásra van szükség. Hogy ennyi vágás elegendő, az könnyen látható: Egészítsük ki négyzetünket 8×8-asra, ezt 3 "függőleges'' vágással ‐ minden lépésben pontosan felezve az addig kapott valamennyi részt ‐ 8 darab 8×1-es csíkra vághatjuk, majd ezeket egymásra helyezve " vízszintesen'' megismételjük az előbbi eljárást.
Be kell még látnunk, hogy 5 vágással nem érhetünk célt (annak ellenére sem, hogy így még 25=32 részre is feldarabolható a négyzet ‐ persze, nem a kívánt módon). Vegyük szemügyre a helyzetet két, tetszés szerint végrehajtott vágást követően. Ekkor összesen 3 vagy 4 rész keletkezik. Az előbbi esetben a kapott részek egyike 8-nál nagyobb területű (hiszen 38=24<25), és ezt a részt három további vágással legfeljebb 23=8 részre bonthatjuk; azok között tehát biztosan marad egy olyan, amelynek a területe nagyobb, mint 1.
Ha az első két vágás nyomán 4 részt kaptunk, akkor ezek között ismét lesz olyan, amelyiknek a területe legalább 9. Az első vágás után ugyanis a négyzet egyik oldala épen marad, a másik oldal pedig két részre esik szét, melyek közül a nagyobbiknak a hossza legalább 3. Egy 3×5-ös téglalapot pedig bármelyik oldalával párhuzamosan osztunk is fel két egész oldalú részre, e részek közül legalább az egyiknek legalább 9 egységnyi a területe. Ezzel igazoltuk, hogy 5 vágás valóban nem elegendő a négyzet kívánt tulajdonságú feldarabolásához.

 

II. megoldás. Tetszőleges pozitív egész m számra jelölje f(m) az m-nél nem kisebb 2-hatványok legkisebbikének a kitevőjét (így pl. f(5)=3). Könnyen látható, hogy ekkor
f(a1+a2)1+max(f(a1),f(a2)),(1)
bármely a1, a2 egészekre. A bizonyítandó állításnál némileg általánosabban megmutatjuk, hogy ha egy T téglalap élei a és b egész számok, akkor a téglalap egységnégyzetekre történő felosztásához szükséges vágásoknak a minimális száma
V(T)=f(a)+f(b).

Az I. megoldás első felében alkalmazott gondolatmenettel most is egyszerűen láthatjuk, hogy V(T) vágás elegendő (egészítsük ki ugyanis a téglalapot úgy, hogy az élek hosszúsága 2f(a) és 2f(b) legyen).
A V(T) értékre vonatkozó indukcióval igazoljuk, hogy V(T)-nél kevesebb vágással a feladat nem oldható meg. Ha V(T)=1, akkor téglalapunk 1×2-es, és 1 vágásra szükség is van. Legyen ezután n>1, és tegyük fel, hogy az állítás igaz minden olyan T' téglalapra, melyre V(T')<n; legyen a T téglalapra V(T)=n. Vágjuk szét ezt a téglalapot két részre, legyenek ezek T1 és T2. T éleit jelöljük a-val és b-vel, T1, ill. T2 élei legyenek a és b1, ill. a és b2. Indukciós feltevésünk alapján
V(T1)=f(a)+f(b1),V(T2)=f(a)+f(b2),
így (1) szerint
max  {V(T1),V(T2)}=max{f(a)+f(b1),f(a)+f(b2)}==f(a)+max  {f(b1),f(b2)}f(a)+f(b1+b2)-1==f(a)+f(b)-1=V(T)-1.


Feltehető tehát, hogy (például) V(T1)V(T)-1, ezért az indukciós feltevés miatt T1 feldarabolásához legalább V(T)-1 vágás szükséges, T felosztásához tehát 1-gyel több, azaz legalább V(T).