Matematické Fórum

slender

Zdravím,
narazil jsem na zajímavý problém, který však neumím řešit:

Mějme čtvercovou tabulku o rozměrech $n\times n$ . V tabulce jsou vystříhány otvory tak, že pro každé $x,y\leq n$ je do tabulky vystřihnutý právě jeden z otvorů s těmito souřadnicemi (souřadnice počítáme od 1 do $n$ ): $[x,y]$ , $[y,n-y+1]$ , $[n-x+1,n-y+1]$ nebo $[n-y+1,x]$ .

Kolik různých tabulek o šířce $n$ existuje, pokud bereme v potaz pouze tabulky, které se dají vystřihnout z papíru?
Vystřihnutelost z papíru se pozná tak, že žádné políčko není izolované od ostatních (viz obrázek).

//forum.matweb.cz/upload3/img/2016-02/01797_tabulky_ukazka.png

Je mi jasné, že množství všech (vystřihnutelných i nevystřihnutelných) tabulek je $4^{\frac{n^2}{4}}$ pro sudá a $4^{\frac{n^2-1}{4}}$ pro lichá $n$ (kvůli políčku uprostřed). Ale jak zmatematizovat tu souvislost tabulky, už nevím. Neměl by někdo, prosím, nějaký nápad?

(Edit: Díky za přesunutí pod jiné téma, nevěděl jsem o něm. :) )

check_drummer · 21. 02. 2016 10:24

↑ slender:
Ahoj, každou tabulku rozdělíš na čtveřice tvaru: $[x,y]$ , $[y,n-y+1]$ , $[n-x+1,n-y+1]$ , $[n-y+1,x]$ (je nutno ukázat, že ty čtveřice jsou disjunktní). Tedy těch čtveřic je $n^2/4$ a z každé čtveřice můžeš vybrat jedno pole právě čtyřmi způsoby - z toho už plyne Tvůj vzorec.

slender · 21. 02. 2016 18:41

↑ check_drummer: Ahoj, díky, jen jsem asi špatně popsal otázku (nebo špatně čtu odpověď). Snažím se zjistit, kolik existuje "vystřihnutelných" čtverců velikosti nxn, tedy mě zajímá, kolik z těch $4^{\frac{n^2}{4}}$ (resp. $4^{\frac{n^2-1}{4}}$ ) se dá skutečně "vystřihnout".

check_drummer · 22. 02. 2016 23:51

↑ slender:
A co znamená vystřihnutelných? Že se nesmí útvar rozpadnout na více částí?A když se části dotýkají jen rohem, jsou vystřihnutelné?

slender · 23. 02. 2016 07:38

↑ check_drummer: No, snažím se to popsat v původním příspěvku. Za vystřihnutelnou považuji tabulku, když se všechny části dotýkají hranou (rohem nestačí).

check_drummer · 23. 02. 2016 16:16

↑ slender:
Jestli to dobře chápu, tak vystřihneš právě jedno pole ze čtyř, které získáš, když tu tabulku postupně otáčíš o 90 stupňů dokola, že? Pokud ano, tak místo druhého pole $[y,n-y+1]$ musíš mít $[y,n-x+1]$ . Připomíná mi to ty šifry jak se do prázdných polí napsalo písmeno a pak se ta tabulka otočila, není to ono?

Matematické Fórum

#1 19. 02. 2016 18:19 — Editoval slender (20. 02. 2016 00:48)

Počet souvislých tabulek nxn

#2 21. 02. 2016 10:24

Re: Počet souvislých tabulek nxn

#3 21. 02. 2016 18:41

Re: Počet souvislých tabulek nxn

#4 22. 02. 2016 23:51

Re: Počet souvislých tabulek nxn

#5 23. 02. 2016 07:38

Re: Počet souvislých tabulek nxn

#6 23. 02. 2016 16:16

Re: Počet souvislých tabulek nxn

Zápatí