Zadanie:
Ile różnych kształtów można uzyskać, zestawiając sześć identycznych kwadratów tak, że każdy następny przylega całym bokiem do któregoś z poprzednich?
________________________
Na początku chciałam to sobie rozrysować na grafach (krawędź = przyleganie), ale to chyba nienajlepszy pomysł bo nierozróżnialne grafy mogły reprezentować dwa inne kształty...
Potem pomyślałam że może trzeba ułożyć równanie rekurencyjne, ale szybko pojawił się kłopot:
Czy w takich zadaniach rozpatruję "kształt" z dokładnością co do obrotu? Czy może trzy kwadraty poziomo
eq \(\displaystyle{ =}\) trzy kwadraty pionowo?
No bo tak
\(\displaystyle{ f(n)}\) - liczba kształtów, \(\displaystyle{ n}\) - liczba kwadratów
\(\displaystyle{ f(1) = 1}\)
\(\displaystyle{ f(2) = 1}\)? Czy \(\displaystyle{ 2}\)?
Sześć kwadratów (kombinatoryka)
-
- Użytkownik
- Posty: 207
- Rejestracja: 23 paź 2015, o 12:31
- Płeć: Kobieta
- Lokalizacja: Mielec
- Podziękował: 14 razy
- Janusz Tracz
- Użytkownik
- Posty: 4074
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Re: Sześć kwadratów (kombinatoryka)
Od razu mówię że jestem denko z kombinatoryki ale w tym zadaniu bardzo ważne jest to by precyzyjnie sformułować to jakie ustawiania są dla nas rozróżnialne bo inaczej kłopot ten będzie ogólną przeszkodą uniemożliwiającą jakiekolwiek rozwiązanie, nie tylko rekurencje. Na to pytanie powinna być odpowiedź w treści zadania, jeśli nie ma to trzeba przyjąć jakąś konwencie i to napisać. Wiem że na podobne pytania odpowiada więc podejrzewam że sprytne utożsamienie kolorowania ze składaniem może dać jakiś efekt.
Kod: Zaznacz cały
http://www.deltami.edu.pl/temat/matematyka/kombinatoryka/2016/07/30/Teoria_grup_w_kombinatoryce/
Re: Sześć kwadratów (kombinatoryka)
Z rekurencją to może nie wyjść tak łatwo. Jest to szczególny przypadek problemu zliczania tzw. polyomin (czyli \(\displaystyle{ f(n)}\)).
Poniższy artykulik oraz nieco nowsza prezentacja mogą okazać się tutaj interesujące:
... 5X81800155
... ilkins.pdf
Poniższy artykulik oraz nieco nowsza prezentacja mogą okazać się tutaj interesujące:
... 5X81800155
... ilkins.pdf