Szuler

Pierwsze zadanie, które chciałbym Wam przedstawić, pochodzi z Fajnych Zawodów Informatycznych (a więc, siłą rzeczy, również jest fajne). Była to cykliczna impreza organizowana w 2006/2007 przez Instytut Informatyki Uniwersytetu Wrocławskiego. Niestety, inicjatywa umarła już po kilku iteracjach, a po jakimś czasie taki sam los spotkał stronę zawodów. Treść zadania możecie przeczytać tutaj, jest tam też podpięta sprawdzaczka odpowiedzi.

Zadanie należy, moim zdaniem, do kategorii zadań epickich, tudzież legendarnych. Choć pewnie nie należy mi w tej kwestii za bardzo wierzyć, bo jestem z nim dość mocno związany emocjonalnie 🙂 Zacznijmy od treści: rozważamy talię n \leq 52 kart i jakąś ich permutację a. Naszym celem jest znalezienie permutacji b, dzięki której jak najwięcej z permutacji c_1,c_2\ldots,c_k będzie można wyrazić jako złożenie a i b (być może wiele razy, czyli dopuszczamy złożenia typu aaabababaabbbbaaa). Mówiąc trochę krócej i mądrzej, chcemy, żeby jak najwięcej z c_i należało do podgrupy S_n generowanej przez \{a,b\}. Dość dziwne jest to, że k \leq 6, co od razu sugeruje, że pewnie możemy sobie pozwolić na złożoność, która będzie wykładnicza względem k. No, ale na pewno nie względem n.

Kluczowe w rozwiązaniu było osobne rozpatrzenie przypadku a=id i a\neq id, gdzie id to permutacja identycznościowa, czyli taka, że dla każdego i mamy id(i)=i. Zajmijmy się najpierw tym drugim, w końcu wygląda na bardziej ogólny (a więc, jak można by się spodziewać, bardziej skomplikowany).

Okazuje się, że dla a\neq id prawie zawsze da się znaleźć b, które umożliwi wygenerowanie dowolnego c. A więc, mówiąc inaczej, nie jest istotne jakie dokładnie są poszczególne c_i. Jedyny przypadek, w którym jest to jednak istotne, to n=4 i a złożone z dokładnie 2 cykli długości 2 (lub, mówiąc krócej, transpozycji), czyli na przykład a=(1,2)(3,4). Nie jest to oczywiste i warto zacząć od napisania dość brutalnego rozwiązania, które pozwoli na ręczne przetestowanie kilku niezbyt dużych permutacji.

Lemat. Dla każdej permutacji a, która nie składa się z dokładnie dwóch transpozycji, można efektywnie skonstruować permutację b, która wraz z a pozwoli na wygenerowanie dowolnej innej permutacji.

Dowód. Na dobry początek możemy sprawdzić wszystkie permutacje a na co najwyżej 4 elementach. Wbrew pozorom nie jest to takie pracochłonne, gdyż możemy śmiało skorzystać z symetrii. Od tego momentu będziemy rozważać więc tylko n \geq 5.

Zacznijmy od następującej prostej obserwacji: mając do dyspozycji przesunięcie cykliczne s=(1,2,\ldots,n) i choć jedną transpozycję typu t_i=(i,i+1), jesteśmy w stanie wygenerować dowolną inną permutację. Wynika to z obserwacji, że każdą permutację można przedstawić jako złożenie cykli, każdy cykl można przedstawić jako złożenie (być może różnych) transpozycji, dowolną transpozycję (x,y) można wyrazić jako (x,x+1)(x+1,x+2),\ldots,(y-1,y), a każde (j,j+1) to nic innego jak s^k t_i s^{k-n}, gdzie k= i-j\bmod n!

Jeśli n < 5, możemy sobie pozwolić na ręczne sprawdzenie wszystkich możliwych a, od tego momentu będziemy więc myśleć tylko o n \geq 5. Spróbujemy znaleźć b, którego (jakaś) nieparzysta potęga da nam t_i, a (jakaś) parzysta potęga s, przy czym zadowoli nas dowolne s składające się z jednego cyklu długości n, pod warunkiem, że t_i będzie transpozycją przestawiającą dwa sąsiednie elementy na tym cyklu.

Na dobry początek popatrzmy na cykle w rozkładzie b. Jeśli wszystkie z nich są nieparzyste, rozważamy następujące możliwości:

  1. Cykli jest 2k+1, czyli nieparzyście wiele. Wybieramy z każdego z nich dokładnie jeden element e_i i ustalamy b(e_i)=e_{i+1}, gdzie e_{2k+2}=e_1. Dodatkowo wybieramy dwa elementy x i y=a(x), które nie są żadnymi e_i (możemy tak zrobić, bo przynajmniej jeden z cykli jest długości przynajmniej 3), i ustalamy b(x)=y, b(y)=x. Ponieważ nasza b składa się z cyklu nieparzystej długości i jednej transpozycji, biorąc jej odpowiednie potęgi możemy otrzymać zarówno dokładnie ten cykl, jak i tylko transpozycję, która zamienia dwóch sąsiadów na jednym z oryginalnych cykli. Teraz wystarczy już tylko zauważyć, że złożenie oryginalnej a i cyklu, na którym każdy e_i przechodzi na e_{i+1}, daje nam jeden długi cykl długości n. Co więcej, x i y pozostaną sąsiadami na tym długim cyklu.
  2. Cykli jest 2k, czyli parzyście wiele, jest wśród nich przynajmniej jeden o długości przynajmniej 5 lub przynajmniej dwa o długości przynajmniej 3. Podobnie jak wcześniej, wybieramy dokładnie jeden element e_i z każdego cyklu, przy czym cykl zawierający e_1 powinien mieć długość przynajmniej 3. Tym razem będziemy jeszcze potrzebowali e'=a(e_1). Tak jak poprzednio, wybieramy x i y=b(x), które nie są żadnymi e_i ani e' (skoro mamy jakiś cykl długości przynajmniej 5 lub dwa cykle długości 3, takie dwa elementy zawsze istnieją). Teraz ustalamy b(e_1)=e_2, b(e_2)=e_3, \ldots, b(e_{2k-1})=e_{2k} oraz b(e_{2k})=e' i b(e')=e_1. Dodatkowo b(x)=y, b(y)=x. Podobnie jak wcześniej, biorąc odpowiednie potęgi b możemy otrzymać zarówno transpozycję zamieniającą x i y, jak i cykl (e_1,e_2,\ldots,e_{2k},e'). Czyli, hmmm… czy na pewno powinniśmy się z tego cieszyć? Możemy skonstruować jeden długi cykl długości n-1, ale przecież obiecywaliśmy, że zbudujemy cykl długości n. Wypada więc trochę zmodyfikować naszą obietnicę. Powiedzmy, że w drodze kompromisu wystarczy nam, że otrzymamy cykl długości przynajmniej n-1, transpozycję, która zamienia dwóch sąsiadów na tym cyklu, przy czym jeśli cykl ma długość n-1 dodatkowo wymagamy, żeby unikalny element e, który leży poza nim, można było przesłać na dowolny inny używając (być może wiele razy) a i b. W tym konkretnym przypadku e=e', który można przesłać na dowolne e_i używając b, a następnie na dowolny inny element używając a.
  3. Mamy dokładnie jeden nietrywialny cykl długości 3, a ponadto n jest parzyste. Powiedzmy, że ten cykl to (e_1,e_2,e_3). Uzupełniamy (e_1,e_2,e_3,\ldots) w jakikolwiek sposób tak, aby dostać cykl długości n, który wybieramy jako nasze b, a następnie uważnie (a nawet z pewną podejrzliwością) przypatrujemy się (abb)^{n/2-1}b. Po krótszej lub dłuższej chwili można zauważyć, że jeżeli b=(e_1,e_2,e_3,e_4,\ldots), to (abb)^{n/2-1}b=(e_3,e_4), czyli mamy naszą transpozycję.

Teraz wypada bliżej przyjrzeć się sytuacji, w której jakiś cykl z rozkładu b jest parzysty. Zastępując b przez jego umiejętnie dobraną potęgę, możemy wymusić, że b jest tak naprawdę inwolucją, czyli bb=b (lub, mówiąc inaczej, wszystkie nietrywialne cykle mają długość 2), no i dalej b\neq id. Tak jak poprzednio, wystarczy rozpatrzeć kilka przypadków. Nie jest to najciekawsza część całego rozwiązania, więc ograniczymy się tylko do ich wypisania. Rozwiązanie każdego z nich sprowadza się do kilku chwil spędzonych nad kartką i/lub napisania brutalnego rozwiązania, które zastąpi nam intuicję.

  1. Mamy dokładnie jeden nietrywialny cykl.
  2. Zarówno n jak i liczba cykli są nieparzyste.
  3. n jest nieparzyste, ale cykli jest parzyście wiele.
  4. Mamy więcej niż dwa i nieparzyście wiele nietrywialnych cykli.
  5. Mamy więcej niż dwa i parzyście wiele nietrywialnych cykli.
  6. Mamy dokładnie dwa nietrywialne cykle oraz przynajmniej jeden trywialny cykl.

No dobrze, czyli (modulo szczegóły) udało nam się pokazać, że dla dowolnego b\neq id można efektywnie skonstruować s i t. Niestety w trakcie dowodu nie obyło się bez strat i musieliśmy trochę osłabić hipotezę: może się zdarzyć, że s jest cyklem długości n-1, a nie n. Oczywiście jeśli s jest cyklem długości n, dowód możemy uznać za zakończony. Przyjrzyjmy się więc bliżej sytuacji, w której s jest cyklem długości n-1.

Bez straty ogólności możemy myśleć, że s=(1,2,\ldots,n-1)(n) i t=(1,2). Powiedzmy, że chcielibyśmy uzyskać z nich permutację p, gdzie p(n)\neq n. Widać, że bez żadnych problemów możemy uzyskać na przykład p złożone z (n,p(n)), ale nie jest to szczególnie pomocne. Z naszego założenia (chytrze ukrytego w jednym z podpunktów) wynika, że za pomocą a i b możemy skonstruować permutację c, dla której c(n)=p(n). Ponieważ cały czas pracujemy z permutacjami, równie dobrze możemy skonstruować też c^{-1}. A więc.. możemy przedstawić p c^{-1} jako złożenie s i t, a następnie dokleić do tego złożenia jeszcze c. Co daje nam koniec całego dowodu.

Powyższy lemat pozwala nam tak naprawdę poradzić sobie z każdym a\neq id: jeśli a składa się z dokładnie dwóch transpozycji, n\leq 4 możemy sobie pozwolić na wygenerowanie i wybranie najlepszej ze wszystkich możliwych b. Pozostaje więc przyjrzeć się sytuacji z a=id. Mogłoby się wydawać, że taka sytuacja jest wręcz nudna. Na szczęście wcale tak nie jest!

Chcemy wybrać b, którego kolejne potęgi pozwolą nam na uzyskanie jak najwięcej c_i. Powiedzmy, że na dobry początek skupimy się na sprawdzeniu, czy można uzyskać wszystkie z nich. Czyli chcemy wybrać b i wykładniki k_i, dla których c_i = b^{k_i}. Zauważmy, że w takiej sytuacji c_i c_j = c_j c_i dla dowolnych i i j. Lub, jak powiedzieliby to matematycy, wszystkie c_i muszą ze sobą komutować (mam nadzieję, że to słowo nie jest obraźliwe). Na dobry początek możemy sprawdzić, czy faktycznie tak jest. Co więcej, dowolne x=c_i i y=c_j należą do jakiejś podgrupy cyklicznej: istnieje pewne z (na przykład równe b), dla którego x i y są pewnymi potęgami z. Stąd możemy wywnioskować, że na pewno istnieje takie z (być może inne niż b!), które można wyrazić jako złożenie x i y: wystarczy popatrzeć na podgrupę cykliczną o najmniejszym możliwym rzędzie, która zawiera x i y. Czyli tak naprawdę moglibyśmy zapomnieć o oryginalnych x,y i pracować dalej z samym z! Jeśli bowiem to z będzie potęgą b, to samo będzie można powiedzieć o x i y. A jeśli zarówno x i y będą potęgami z, to samo będzie można powiedzieć o ich dowolnych złożeniu, czyli w szczególności o naszym starannie wybranym z. Powtarzając procedurę sklejania x i y do z prędzej lub później zostaniemy z tylko jedną permutacją, która będzie naszym wymarzonym b. Ale jak zaimplementować taką procedurę?

Skoro x i y komutują, bez straty ogólności z=x^p y^q. Moglibyśmy spróbować zgadnąć p i q, a następnie sprawdzić, czy otrzymana permutacja pozwala na wyrażenie x=z^\alpha i y=z^\beta. Czyli na dobry początek powinniśmy zastanowić się, jak duże może być \alpha, \beta, p,q. Patrząc na kolejne potęgi dowolnej permutacji prędzej lub później otrzymamy permutację identycznościową, i oczywiście nie ma sensu rozważać dalszych potęg, ale kiedy właściwie pojawi się ta identyczność? Inaczej mówiąc, interesuje nas jaki jest największy możliwy rząd permutacji na 52 elementach. Okazuje się, że jest to co najwyżej 180180 (co można sprawdzić nawet w dość brutalny sposób generując wszystkie możliwe rozkłady długości cykli), czyli moglibyśmy sobie pozwolić na zgadnięcie (na przykład) \alpha. Ale co dalej?

W tym momencie musimy niestety trochę bliżej przyjrzeć się założeniu, że x i y komutują. Weźmy dowolny cykl długości \ell z x i popatrzmy na jego obraz przez y. Nietrudno zauważyć, że ten obraz to także cykl długości \ell: być może inny niż ten oryginalny, a być może ten sam, tylko ewentualnie przesunięty cyklicznie. Powtarzając całe rozumowanie otrzymujemy, że każda spójna składowa w grafie złożonym z krawędzi i\rightarrow x(i), i\rightarrow y(i) wygląda mniej więcej tak jak na poniższym rysunku, gdzie czerwone krawędzie pochodzą z b, a czarne z a. Wszystkie elementy w tej składowej muszą należeć do tego samego cyklu w z (oraz nie ma sensu umieszczać na tym cyklu żadnych innych), ale nie wiemy jeszcze w jakiej kolejności.

szuler-skladowa

Patrząc na rysunek i pamiętając, że z=x^p y^q, można zauważyć, że na pewno r| \alpha. W przeciwnym wypadku x=z^\alpha łączyłaby elementy z różnych poziomych cykli. Podobnie, na pewno \gcd(\ell,d-1) | \beta, bo każdy z poziomych cykli zawiera elementy należące do pewnej wielokrotności \gcd(\ell,d-1) pionowych cykli. W związku z tym można podejrzewać (słusznie), że warunki, które muszą spełniać \alpha i \beta, to nic innego niż proste cechy podzielności.

Załóżmy, że znamy już \alpha=\alpha' \mathrm{lcm}(r) i zastanawiamy się nad wyborem \beta = \beta' \mathrm{lcm}(\gcd(\ell,d-1)), gdzie \mathrm{lcm} liczymy po wszystkich możliwych składowych. Taki wybór musi powodować, że długi cykl długości \ell r w z rozpadnie się na dokładnie (odpowiednio) r i \gcd(\ell,d-1) cykli po podniesieniu do potęgi \alpha i \beta. Czyli \gcd(\ell r, \alpha)=r i \gcd(\ell r, \beta) = \gcd(\ell,d-1). Ten pierwszy warunek możemy sprawdzić od razu (bo znamy już \alpha), ten drugi sprowadza się do tego, że \beta' nie może być podzielne przed pewne liczby pierwsze, czego sprawdzenie odłożymy sobie na później. Poza rozpadem na cykle odpowiednich długości musimy zadbać o ich odpowiednią synchronizację: chcemy, żeby dla dowolnego elementu z poziomego cyklu przesunięcie o x^{d-1} było tym samym co przesunięcie o y^{r}. Czyli, tak naprawdę z^{\alpha' \frac{\mathrm{lcm}(r)}{r} (d-1)} = z^{\beta' \mathrm{lcm}(\gcd(\ell,d-1))}, o ile sprawdziliśmy już, że uzyskamy rozpad na cykle odpowiednich długości (czego tak naprawdę jeszcze nie zrobiliśmy, ale zrobimy już za chwilę). Ten warunek z kolei oznacza nic innego jak \alpha' \frac{\mathrm{lcm}(r)}{r} (d-1) = \beta' \mathrm{lcm}(\gcd(\ell,d-1)) \pmod \ell. Czyli udało nam się opisać \beta' za pomocą zbioru równań liniowych modulo! Każde z nich wymusza, że \beta' daje specyficzne reszty modulo pewne potęgi liczb pierwszych. Grupując wszystkie takie warunki przy pomocy rozszerzonego algorytmu Euklidesa (lub nawet bardziej naiwnego stablicowania odwrotności wszystkich dostatecznie małych liczb) dostajemy ostateczne rozwiązanie postaci \beta' = t \pmod m. Wypada jeszcze uwzględnić to, że \beta' nie może być podzielne przez pewne zabronione liczby pierwsze. Jeśli taką liczbą jest p i p | t,m, otrzymaliśmy sprzeczność. Jeśli zaś p \nmid m, musimy dołożyć warunek \beta' = 1 \pmod p, który tak naprawdę można skleić z \beta' = t \pmod m otrzymując \beta' = t' \pmod {m'} używając (ponownie) rozszerzonego algorytmu Euklidesa. Uff.

W całym powyższym rozumowaniu skupiliśmy się tylko na wyznaczeniu \alpha' i \beta', a przecież tak naprawdę szukamy z, mogłoby się wydawać, że cała praca była lekko bez sensu. Nie jest to jednak pomyłka: wystarczy skonstruować współczynniki s i t dla których \alpha' s + \beta' t = \gcd(\alpha', \beta') (co można zrobić używając.. algorytmu Euklidesa) no i wypisać z = x^{s} y^{t}.

Jest to już właściwie całe rozwiązanie. Jak można się domyśleć, jest ono niesamowicie męczące implementacyjnie, tym niemniej dalej uważam zadanie za fajne 🙂 Właściwie tylko jeden z zawodników wysłał kod, który zdobywał nietrywialną liczbę punktów. Co ciekawe, był on oparty na zupełnie innym pomyśle: okazuje się, że dość dobrym pomysłem dla przypadku a\neq id jest.. wylosowanie a. Wymaga to jednak umiejętnego sprawdzania, czy dane c_i należy do podgrupy generowanej przez aktualne \{a,b\}. Co dość zaskakujące, można dokonać tego wyczynu w czasie wielomanowym (względem n). W (raczej bardziej odległej) przyszłości postaram się wyjaśnić jak.

Reklamy

4 myśli nt. „Szuler

  1. „Mówiąc trochę krócej i mądrzej, chcemy, żeby jak najwięcej z c_i należało do wolnej podgrupy S_n generowanej przez \{a,b\}. ”
    Muszę się przyczepić, że taka podgrupa nigdy nie jest „wolna” w zwykłym (matematycznym) sensie. To zdanie bez „wolna” brzmi o wiele lepiej ;).

  2. „Na dobry początek możemy sprawdzić, czy faktycznie tak jest. Jeśli tak, to dowolne x=c_i i y=c_j należą do podgrupy cyklicznej” – na pewno? Weźmy n=4 i taką grupę Kleina K4 = {id, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)} = {c1, c2, c3, c4}. c2 i c3 komutują, ale raczej nie są potęgą tego samego elementu S4.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s