szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 22 wrz 2015, o 15:42 
Użytkownik

Posty: 26
Lokalizacja: Warszawa
Dzień dobry, mam problem z rozwiązaniem poniższego zadania:

Cytuj:
Na ile sposobów można pomalować szachownicę o wymiarach 2\times2, mając do dyspozycji 8 różnych kolorów, w taki sposób, aby pola o tym samym kolorze nie stykały się bokami? Dwa kolorowania uznajemy za takie same, jeżeli jedno można uzyskać z drugiego poprzez obrót szachownicy.


W moim rozwiązaniu rozpatruję trzy przypadki:


1) wszystkie pola pomalowane są na inny kolor (kolory:\left\{a, b, c, d\right\} \subset \left\{1, 2, 3, 4, 5, 6, 7, 8\right\}):

\begin{tabular}{|c|c|}
\hline
a & b\\ \hline
c & d\\ \hline
\end{tabular}

Można to zrobic na {8 \choose 4} \cdot \frac{4!}{4} = 420 sposobów (wybieram 4 spośród 8 kolorów, pola mogą być nimi pomalowane na 4! sposobów, ale z jednego kolorowania można otrzymać 3 inne poprzez obrót - dlatego dzielę tę liczbę przez 4).


2) dwa pola są pomalowane są na kolor a i dwa pola są pomalowane na kolor b:

\begin{tabular}{|c|c|}
\hline
a & b\\ \hline
b & a\\ \hline
\end{tabular}

Można to zrobic na {8 \choose 2} = 28 sposobów (wybieram 2 spośród 8 kolorów).

3) dwa pola są pomalowane na kolor a, jedno pole jest pomalowane na kolor b oraz jedno pole jest pomalowane na kolor c:

\begin{tabular}{|c|c|}
\hline
a & b\\ \hline
c & a\\ \hline
\end{tabular}

Można to zrobic na {8 \choose 1} \cdot {7 \choose 2} = 168 sposobów (wybieram 1 spośród 8 kolorów, na który będą pomalowane 2 pola, a następnie spośród pozostałych 7 kolorów wybieram 2, na które będą pomalowane pozostałe pola).

Co łącznie daje liczbę 616.

Prawidłowa odpowiedź to 532 kolorowania. Czy moje podejście jest zupełnie nieprawidłowe, czy też tylko liczę niektóre kolorowania więcej niż raz?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Kobieta Offline
PostNapisane: 22 wrz 2015, o 17:25 
Użytkownik
Avatar użytkownika

Posty: 2505
Prawidłowa liczba to 616, jeżeli nie uznajesz symetrii osiowych.

Kod:
1
2
3
f[n_] := Sort[{n, RotateLeft[n, 1], RotateLeft[n, 2], RotateLeft[n, 3]}]
Length[DeleteDuplicates[Select[Tuples[Range[8], {4}], Not[MemberQ[# - RotateLeft[#, 1], 0]] &], f[#1] == f[#2] &]]
Góra
Mężczyzna Offline
PostNapisane: 22 wrz 2015, o 22:20 
Użytkownik

Posty: 26
Lokalizacja: Warszawa
Dziękuję za odpowiedź. Tylko jak teraz przyjmę, że kolorowania symetryczne uznajemy za takie same, to otrzymuję wynik 406 kolorowań. Załączona odpowiedź jest nieprawidłowa, czy to ja popełniłem błąd?
Góra
Kobieta Offline
PostNapisane: 24 wrz 2015, o 01:56 
Użytkownik
Avatar użytkownika

Posty: 2505
Potwierdzam nowy wynik (przy założeniu, że szachownicę można przewracać na drugą stronę). Nawet w książkach zdarzają się błędy, tak było pewnie i tym razem.
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2015, o 21:47 
Użytkownik

Posty: 45
Lokalizacja: Rawa
Lekki odkop.

Czy w 3 przypadku również, podobnie jak w 1 z jednego kolorowania nie można otrzymać 3 innych poprzez obrót?

Wtedy wynik to 532.
Góra
Mężczyzna Offline
PostNapisane: 6 gru 2015, o 08:37 
Użytkownik
Avatar użytkownika

Posty: 3229
Lokalizacja: blisko
Przypadek 3 daje {8 \choose 3}=56 tylko a obroty wypełniają wszystkie możliwości!

W przypadku 3 wszystkie inne kolorowania otrzymasz przez obrót!


Powinno być:

420+28+56=?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 wieże na szachownicy - zadanie 3  Zordon  2
 Rozmiesczenie pionów na szachownicy  Ballazzo  8
 Sposoby wymiany znaczków  jackie  1
 umieszczenie k pionów na szachownicy  nowheredense_man  0
 Dwa króle na szachownicy  FaloZ  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl