Cześć : )
Proszę Was o pomoc z zadaniem:
Panowie V,W,U,X,Y,Z muszą zasiąść do wspólnego okrągłego stołu. Z uwagi na to iż panowie V i W podobnie jak U i X oraz Y i Z się nie lubią nie mogą siedzieć obok siebie. Na ile sposobów można ich posadzić przy okrągłym 6 osobowym stole?
z góry dziekuje
Okrągły Stół
-
miko03
- Użytkownik
- Posty: 16
- Rejestracja: 30 mar 2013, o 14:45
- Płeć: Mężczyzna
- Lokalizacja: Rzeszow
- Pomógł: 1 raz
Okrągły Stół
wydaje mi sie ze to bedzie tak:
od wszystkich mozliwosci posadzenia 6 panow, ktorych jest \(\displaystyle{ 6!}\)
odejmuje te gdy wszyscy nielubiacy sie siedza kolo siebie a takich mozliowsci jest \(\displaystyle{ 3!}\)
odejumuje gdy dwie nielubiace pary siedza obko siebie-\(\displaystyle{ {3 \choose 2} \cdot 2}\)
i odejumuje gdy jedna para nielubiaca sie siedzi obok siebie \(\displaystyle{ {3 \choose 1} \cdot 5}\)
od wszystkich mozliwosci posadzenia 6 panow, ktorych jest \(\displaystyle{ 6!}\)
odejmuje te gdy wszyscy nielubiacy sie siedza kolo siebie a takich mozliowsci jest \(\displaystyle{ 3!}\)
odejumuje gdy dwie nielubiace pary siedza obko siebie-\(\displaystyle{ {3 \choose 2} \cdot 2}\)
i odejumuje gdy jedna para nielubiaca sie siedzi obok siebie \(\displaystyle{ {3 \choose 1} \cdot 5}\)
-
Hassgesang
- Użytkownik
- Posty: 206
- Rejestracja: 26 mar 2012, o 20:41
- Płeć: Mężczyzna
- Lokalizacja: Gdynia
- Podziękował: 3 razy
- Pomógł: 17 razy
Okrągły Stół
Kolejnych panów będę oznaczał liczbami \(\displaystyle{ 0,1,2,3,4,5}\). Najpierw musimy się zastanowić, czy ustawienia \(\displaystyle{ (0,1,2,3,4,5)}\) i \(\displaystyle{ (1,2,3,4,5,0)}\) traktujemy jako różne (bo np. jedno krzesło jest wyróżnione), czy też nie. Jeżeli są one różne, to permutacji będzie sześć razy więcej.
Wynik podany przez miko03 (693?) zdaje się być zawyżony. Krótka sesja w Pythonie pozwala stwierdzić, że odpowiedzią jest \(\displaystyle{ 192}\) (albo \(\displaystyle{ 32}\)).
Wynik podany przez miko03 (693?) zdaje się być zawyżony. Krótka sesja w Pythonie pozwala stwierdzić, że odpowiedzią jest \(\displaystyle{ 192}\) (albo \(\displaystyle{ 32}\)).
32 permutacje:
-
Hassgesang
- Użytkownik
- Posty: 206
- Rejestracja: 26 mar 2012, o 20:41
- Płeć: Mężczyzna
- Lokalizacja: Gdynia
- Podziękował: 3 razy
- Pomógł: 17 razy
Okrągły Stół
Oczywiście, mogę. Należy jednak pamiętać, że moim celem nie była wydajność, tylko jak najszybsze napisanie tego, przy okazji - trochę uogólniłem problem (mamy \(\displaystyle{ n}\) par panów, którzy są swoimi wrogami). Ja korzystam z Fedory, więc najpierw w konsoli uruchamiam ipython, potem %run plik.py i na koniec fx(3).
Komentarz od końca: tworzymy listę wszystkich permutacji, dla każdej z nich wywoływana jest funkcja która sprawdza, czy każdy siedzi tak, jak powinien. Tzn. wrogowie nie mogą siedzieć w odległości \(\displaystyle{ 1}\) od siebie (czyli albo są kolejnymi elementami listy, albo jeden jest na początku, a drugi na jej końcu).
Po wywołaniu fx(n) dla \(\displaystyle{ n = 2, 3, 4}\) można rozpocząć poszukiwania na OEIS. zdaje się być szukanym przez nas ciągiem. Standardowo w zadaniach ze stołem rozwiązania, które powstają przez obrót traktuje się jako identyczne, jeśli nie - patrz [url=https://oeis.org/A003435]A003435 Number of Hamiltonian circuits on n-octahedron.[/url] Tam też można znaleźć wzór
\(\displaystyle{ a_n = \sum_{k=0}^{k=n}(-2)^k\cdot{n \choose k}\cdot 2n\cdot(2n-k-1)!}\)
Komentarz od końca: tworzymy listę wszystkich permutacji, dla każdej z nich wywoływana jest funkcja która sprawdza, czy każdy siedzi tak, jak powinien. Tzn. wrogowie nie mogą siedzieć w odległości \(\displaystyle{ 1}\) od siebie (czyli albo są kolejnymi elementami listy, albo jeden jest na początku, a drugi na jej końcu).
Po wywołaniu fx(n) dla \(\displaystyle{ n = 2, 3, 4}\) można rozpocząć poszukiwania na OEIS.
Kod: Zaznacz cały
https://oeis.org/A129348\(\displaystyle{ a_n = \sum_{k=0}^{k=n}(-2)^k\cdot{n \choose k}\cdot 2n\cdot(2n-k-1)!}\)