Zoznam úloh

3. Katapult Monštruóznej Sily (κ ≤ 3)

Zadanie

Zakiaľ, čo sa uhorský princ Ákos zabával Jakubovými slávnymi číslami, potajme vyvíjal jeho úhlavný nepriateľ Kazisvet Matúš Strašný všemohúci trebuchet. Takýto katapult by navždy rozmetal kráľovské mestské steny a vyhnal Kiku z Uhorského kráľovstva. Problém však nastal, keď sa zistilo, že takýto mocný katapult možno postaviť iba na špeciálnej $n$-uholníkovej podstave.

Nájdite všetky celé čísla $n \ge 3$, pre ktoré existuje $n$-uholník, ktorý:

  • má celočíselné dĺžky strán;

  • každé jeho dve susedné strany sú na seba kolmé;

  • nedá sa celý pokryť neprekrývajúcimi sa dlaždicami rozmeru $1 \times 2$, ktorých strany sú rovnobežné so stranami $n$-uholníka (otáčať ich možno).

Najprv sa zamyslime koľko-uholníky spĺňajú prvé dve vlastnosti. Pre súčet vnútorných uhlov $n$-uholníka platí, že je rovný $(n-2) \cdot 180^\circ$. 1 Strany $n$-uholníkovej podstavy katapultu majú byť na seba kolmé. Teda každý vnútorný uhol podstavy katapultu musí byť buď $90^\circ$ alebo $270^\circ$. Majme $k$ vnútorných uhlov s veľkosťou $270^\circ$ a $(n-k)$ vnútorných uhlov s veľkosťou $90^\circ$ (pretože spolu máme $n$ vnútorných uhlov). Ak takýto $n$-uholník existuje, tak musí platiť rovnosť: $(n-2) \cdot 180^\circ = k\cdot 270^\circ + (n-k)\cdot90^\circ$. To vieme jednoducho upraviť na tvar $2n - 4 = n + 2k$. Môžeme si všimnúť, že výraz na ľavej strane je vždy párny. Výraz na pravej strane je párny práve vtedy, keď $n$ je párne. Teda táto rovnosť môže platiť len pre párne $n$, čo znamená, že podstava katapultu môže mať len párny počet strán.

Teraz skúsme hľadať konkrétne $n$-uholníkové podstavy, ktoré spĺňajú aj tretiu vlastnosť. Ak $n=4$, tak si môžeme zobrať štvorec veľkosti $1 \times 1$ a ten rozhodne nejde pokryť dlaždicami s rozmermi $1 \times 2$. Ďalej môžeme hľadať $6$, $8$, $10$ a viac uholníky a podarí sa nám nájsť napr. takéto „schodíkové podstavy“:

image

Po troške skúšania a ukladania dlaždičiek nadobudneme dojem, že keď je najmenšia strana dĺžky $1$, tak to naozaj nepôjde vydláždiť. Už to len treba dokázať. Pri úlohách s dláždením sa nám mnohokrát oplatí vyfarbiť si políčka. Bude tomu tak aj v tejto úlohe. Vyfarbime štvorčeky ako políčka šachovnice, teda striedavo na bielo a na čierno. Môžeme to vidieť aj na obrázku.

image

Dlaždica rozmerov $1 \times 2$ zakryje dva susedné štvorce, teda jeden biely a jeden čierny. Vidíme, že všetky pravé horné štvorčeky (štvorčeky, ktoré tvoria najdlhšiu diagonálu) sú biele. Štvorčeky, ktoré s nimi susedia (štvorčeky pod nimi) sú všetky čierne. Každá dlaždička, ktorá nám zakryje horný biely štvorček musí zakryť, ešte susediaci čierny štvorček. Tých je však o $1$ menej. Z toho vyplýva, že takéto schodíky sa nedajú pokryť dlaždicami $1 \times 2$. Takéto podstavy spĺňajú všetky tri vlastnosti. Hľadané $n$ sú všetky párne čísla, až na číslo $2$. Mohli by sme aj zamyslieť nad počtom bielych a čiernych štvorčekov. Čiernych je vždy menej. (Rozmyslite si.) Z toho znova vyplýva, že takéto schodíky sa nedajú pokryť dlaždicami $1 \times 2$ a hľadanými $n$ sú všetky párne čísla okrem čísla $2$.


  1. Skúste si rozmyslieť, že toto naozaj platí aj pre nekonvexné mnohouholníky. 

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný matematický seminár zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty