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: 2363
Reputace:   64 
 

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.


Cimrmanův botanický kvíz:
Co mají společného byliny kozlík a pivoňka?

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: 2363
Reputace:   64 
 

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


Cimrmanův botanický kvíz:
Co mají společného byliny kozlík a pivoňka?

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: 2363
Reputace:   64 
 

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?


Cimrmanův botanický kvíz:
Co mají společného byliny kozlík a pivoňka?

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson