Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

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

slender
Příspěvky: 133
Pozice: student
Reputace:   
 

Počet souvislých tabulek nxn

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).

http://forum.matematika.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. :) )

Offline

 

#2 21. 02. 2016 10:24

check_drummer
Příspěvky: 2446
Reputace:   65 
 

Re: Počet souvislých tabulek nxn

↑ 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.


"Mami, co je to ta rekurze?"
"Vysvětlím ti to lépe až zítra."

Offline

 

#3 21. 02. 2016 18:41

slender
Příspěvky: 133
Pozice: student
Reputace:   
 

Re: Počet souvislých tabulek nxn

↑ 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".

Offline

 

#4 22. 02. 2016 23:51

check_drummer
Příspěvky: 2446
Reputace:   65 
 

Re: Počet souvislých tabulek nxn

↑ 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é?


"Mami, co je to ta rekurze?"
"Vysvětlím ti to lépe až zítra."

Offline

 

#5 23. 02. 2016 07:38

slender
Příspěvky: 133
Pozice: student
Reputace:   
 

Re: Počet souvislých tabulek nxn

↑ 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čí).

Offline

 

#6 23. 02. 2016 16:16

check_drummer
Příspěvky: 2446
Reputace:   65 
 

Re: Počet souvislých tabulek nxn

↑ 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?


"Mami, co je to ta rekurze?"
"Vysvětlím ti to lépe až zítra."

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson