Skrytki i klucze

antek_k · Post autor: **antek_k** » 17 lis 2016, o 20:08

Witam, bardzo bym prosił o wyjaśnienie poniższego zadania związanego z cyklami.

Na ile różnych sposobów można rozmieścić w \(\displaystyle{ n}\) skrytkach zapasowe klucze do nich tak, aby w każdej był jeden klucz i tak by istniało \(\displaystyle{ k}\) takich skrytek do których włamanie się pozwoli otworzyć wszystkie pozostałe.

Pozdrawiam

Mruczek · Post autor: **Mruczek** » 17 lis 2016, o 22:40

Ponumerujmy skrytki od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\). Kluczom przydzielamy numery z tego samego zbioru tak, że numer klucza określa jaki numer skrytki on otwiera. Skoro w każdej skrytce jest jeden klucz to znaczy, że numery kluczy znajdujących się w skrytkach o numerach od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\) tworzą permutację.
Wiadomo, że permutację można rozłożyć na cykle - numer skrytki prowadzi do klucza o pewnym numerze, a on do skrytki o tym numerze, ta skrytka do kolejnej skrytki, następna skrytka do następnej itd. Jeżeli otworzymy jedną skrytkę, to jesteśmy w stanie otworzyć wszystkie skrytki o numerach znajdujących się na tym samym cyklu co skrytka którą otworzyliśmy jako pierwszą. To oznacza, że możemy otworzyć wszystkie skrytki wtedy i tylko wtedy, gdy liczba cykli permutacji jest nie większa niż \(\displaystyle{ k}\) - po prostu otwieramy po co najmniej jednej skrytce z każdego cyklu.
Liczba \(\displaystyle{ n}\)-permutacji o \(\displaystyle{ i}\) cyklach to liczba Stirlinga pierwszego rodzaju: \(\displaystyle{ S\left( n,i\right)}\). Wtedy szukamy wartości \(\displaystyle{ \sum_{i=1}^{k} S\left( n,i\right)}\).

antek_k · Post autor: **antek_k** » 17 lis 2016, o 22:56

Dziękuję

arek1357 · Post autor: **arek1357** » 18 lis 2016, o 11:59

Tak tylko te k kluczy musi przynależeć do k utworzonych cykli co zmniejszy nam ilość możliwości.
Bo jak się zdarzy, że dwa klucze, które mamy przynależą do jednego cyklu wtedy jak?

Mruczek · Post autor: **Mruczek** » 18 lis 2016, o 15:45

arek1357 pisze:Bo jak się zdarzy, że dwa klucze, które mamy przynależą do jednego cyklu wtedy jak?

W zadaniu jest mowa o istnieniu zbioru skrytek, a nie o tym, że ustalamy jakiś zbiór i dla niego obliczamy wynik. Tak więc dla danej permutacji mogę sobie przyjąć dowolne \(\displaystyle{ k}\) skrytek, więc w szczególności mogę zrobić tak, że z każdego cyklu biorę po co najmniej jednej skrytce.

arek1357 · Post autor: **arek1357** » 18 lis 2016, o 17:37

A szkoda ładniej by było ułożyć zadanie dla ustalonego wcześniej zbioru kluczy dla którego liczymy wynik ja bym właśnie tak ułożył zadanie.

Mruczek · Post autor: **Mruczek** » 18 lis 2016, o 20:17

Ok, czyli mam ustalony zbiór \(\displaystyle{ k}\) skrytek (raczej skrytek a nie kluczy), które otwieram i pytam się o liczbę takich ułożeń kluczy w skrytkach, że można wszystkie otworzyć (i w każdej skrytce jest jeden klucz).

To znaczy, że w tej permutacji nie może istnieć cykl, na którym nie ma żadnej wybranej skrytki.
No to najpierw rozmieszczamy te \(\displaystyle{ k}\) skrytek na co najwyżej \(\displaystyle{ k}\) cyklach na \(\displaystyle{ k!}\) sposobów. Potem dokładamy do tych cykli pozostałe \(\displaystyle{ n - k}\) liczby w pewnej ustalonej kolejności. Każdą z tych liczb możemy umieścić za dowolną z liczb znajdujących się w tej chwili na cyklach, tworząc inną permutację - czyli na tyle sposobów jaka jest do tej pory łączna długość cykli. Przy ustalonym początkowym zbiorze cykli będzie to łącznie: \(\displaystyle{ k \cdot (k + 1) \cdot ... \cdot (n-1)=\frac{(n - 1)!}{(k-1)!}}\) sposobów. Ostateczny wynik to \(\displaystyle{ \frac{(n - 1)!}{(k-1)!} \cdot k! = k \cdot (n - 1)!}\).
Mam nadzieję, że jest ok.

arek1357 · Post autor: **arek1357** » 19 lis 2016, o 01:24

No dokładnie, powiem szczerze zadanie mi się spodobało jest fajne.

kinia7 · Post autor: **kinia7** » 21 lis 2016, o 20:31

Mruczek pisze: Ostateczny wynik to \(\displaystyle{ \frac{(n - 1)!}{(k-1)!} \cdot k! = k \cdot (n - 1)!}\).
Mam nadzieję, że jest ok.

Cóś mnie nie pasi.
Założyłam, że w żadnej skrytce nie ma kluczyka od niej samej. Rozpisałam wszystkie możliwości i policzyłam przypadki:
dla \(\displaystyle{ n=4}\) jest \(\displaystyle{ 9}\) wszystkich możliwości,
- - - dla \(\displaystyle{ k=1}\) możliwości jest \(\displaystyle{ 6}\)
- - - dla \(\displaystyle{ k>1}\) możliwości jest \(\displaystyle{ 9}\)
dla \(\displaystyle{ n=5}\) jest \(\displaystyle{ 44}\) wszystkich możliwości,
- - - dla \(\displaystyle{ k=1}\) możliwości jest \(\displaystyle{ 24}\)
- - - dla \(\displaystyle{ k>1}\) możliwości jest \(\displaystyle{ 44}\)

Mruczek · Post autor: **Mruczek** » 22 lis 2016, o 00:55

Wytłumacz się skąd wzięłaś dla \(\displaystyle{ n = 4}\), \(\displaystyle{ k > 1}\) te \(\displaystyle{ 9}\) możliwości.
Po co założyłaś, że permutacja nie ma punktów stałych?

kinia7 · Post autor: **kinia7** » 22 lis 2016, o 18:05

Mruczek pisze: Po co założyłaś, że permutacja nie ma punktów stałych?

Bo wydaje mi się nielogiczne umieszczanie kluczyka zapasowego w skrytce, do której ten kluczyk pasuje.

Mruczek pisze:Wytłumacz się skąd wzięłaś dla \(\displaystyle{ n = 4}\), \(\displaystyle{ k > 1}\) te \(\displaystyle{ 9}\) możliwości.

Bo wszystkich możliwości rozmieszczenia 4 kluczyków zapasowych w 4 skrytkach jest 9.
Z tego trzy przypadki są takie, że nie wystarczy włamać się do jednej skrytki, żeby otworzyć wszystkie.