szukanie zaawansowane
 [ Posty: 11 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 17 lis 2016, o 20:08 
Użytkownik

Posty: 7
Lokalizacja: Tuitam
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 n skrytkach zapasowe klucze do nich tak, aby w każdej był jeden klucz i tak by istniało k takich skrytek do których włamanie się pozwoli otworzyć wszystkie pozostałe.

Pozdrawiam
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2016, o 22:40 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Ponumerujmy skrytki od 1 do 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 1 do 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ż k - po prostu otwieramy po co najmniej jednej skrytce z każdego cyklu.
Liczba n-permutacji o i cyklach to liczba Stirlinga pierwszego rodzaju: S\left( n,i\right). Wtedy szukamy wartości \sum_{i=1}^{k} S\left( n,i\right).
Góra
Mężczyzna Offline
PostNapisane: 17 lis 2016, o 22:56 
Użytkownik

Posty: 7
Lokalizacja: Tuitam
Dziękuję :)
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2016, o 11:59 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
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?
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2016, o 15:45 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
arek1357 napisał(a):
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 k skrytek, więc w szczególności mogę zrobić tak, że z każdego cyklu biorę po co najmniej jednej skrytce.
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2016, o 17:37 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
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.
Góra
Mężczyzna Offline
PostNapisane: 18 lis 2016, o 20:17 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Ok, czyli mam ustalony zbiór 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 k skrytek na co najwyżej k cyklach na k! sposobów. Potem dokładamy do tych cykli pozostałe 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: k \cdot (k + 1) \cdot ... \cdot (n-1)=\frac{(n - 1)!}{(k-1)!} sposobów. Ostateczny wynik to \frac{(n - 1)!}{(k-1)!}   \cdot k! = k \cdot (n - 1)!.
Mam nadzieję, że jest ok.
Góra
Mężczyzna Offline
PostNapisane: 19 lis 2016, o 01:24 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
No dokładnie, powiem szczerze zadanie mi się spodobało jest fajne.
Góra
Kobieta Offline
PostNapisane: 21 lis 2016, o 20:31 
Użytkownik
Avatar użytkownika

Posty: 663
Lokalizacja: Wrocław
Mruczek napisał(a):
Ostateczny wynik to \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 n=4 jest 9 wszystkich możliwości,
- - - dla k=1 możliwości jest 6
- - - dla k>1 możliwości jest 9
dla n=5 jest 44 wszystkich możliwości,
- - - dla k=1 możliwości jest 24
- - - dla k>1 możliwości jest 44
Góra
Mężczyzna Offline
PostNapisane: 22 lis 2016, o 00:55 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Wytłumacz się skąd wzięłaś dla n = 4, k > 1 te 9 możliwości.
Po co założyłaś, że permutacja nie ma punktów stałych?
Góra
Kobieta Offline
PostNapisane: 22 lis 2016, o 18:05 
Użytkownik
Avatar użytkownika

Posty: 663
Lokalizacja: Wrocław
Mruczek napisał(a):
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 napisał(a):
Wytłumacz się skąd wzięłaś dla n = 4, k > 1 te 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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 11 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 System RSA- dwa klucze  Makiwarrior  6
 klucze  bycSOBA  1
 Skarbonki i klucze  splinter  7
 klucze pgp  nowik1991  0
 Klucze do zbiorów Pazdro 2010 P. rozszerzony  s_pecel  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl