grupa permutacji

[Przybyl]

Dzień dobry. Mógłby mi ktoś pomóc jak ugryźć zadanie takie:
Dla podanej liczby k podać najmniejszą liczbę \(\displaystyle{ n\in\mathbb{N}}\), że w grupie permutacji \(\displaystyle{ S_n}\) istnieje element rzędu k.
Dla k = 56 powiedzmy i k = 53. Znam wyniki i dla tych wartości różnią się one mocno. Wiem, że rząd elementu g to najmniejsza liczba dodatnia n naturalna, \(\displaystyle{ g^n=id}\), jednak nie wiele mi to mówi

[Gosda]

Wskazówka: rozpatrz najpierw przypadek, kiedy \(\displaystyle{ k}\) jest liczby pierwszą. Następnie, kiedy jest potęgą pewnej liczby pierwszej.Wreszcie kiedy jest dowolną liczbą złożoną.

[Przybyl]

Kiedy k jest liczbą pierwszą to n = k. Dalej nie wiem, już całkiem się pogubiłem. Myślalem, że to chodzi o rozkład 56 na czynniki potem dodanie tych czynników... Jeszcze nad tym posiedzę

[arek1357]

tak na szybko:

niech:

\(\displaystyle{ k=p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \cdot ... \cdot p_{s}^{\alpha_{s}}}\)

To wtedy:

\(\displaystyle{ n=p_{1}^{\alpha_{1}} + p_{2}^{\alpha_{2}} + ... + p_{s}^{\alpha_{s}} }\)

Oczywiście:

\(\displaystyle{ p_{i}^{\alpha_{i}}}\) - to długość cyklu w rozbiciu na n...

[Przybyl]

To czy przy \(\displaystyle{ k=56}\), nie będzie rozbicie na \(\displaystyle{ 2\cdot 2\cdot 2\cdot 7}\) ? Wtedy \(\displaystyle{ n = 13}\) ?

[arek1357]

raczej n=15

[Gosda]

Kolejna podpowiedź: jeśli permutacja rozbita jest na rozłączne cykle, to jej rząd jest najmniejszą wspólną wielokrotnością długości cykli.

[Przybyl]

Nadal nie rozumiem tego zadania.
Przykadowo dla k=53 jest to liczba pierwsza, więc jest jeden cykl wobec tego \(\displaystyle{ n=53}\)
Dla \(\displaystyle{ k=55}\) mogę rozbić \(\displaystyle{ 55}\) na \(\displaystyle{ 55=5*11}\) zatem \(\displaystyle{ n=11+5=16}\)
Jednak dla \(\displaystyle{ k=56}\) oraz \(\displaystyle{ k=54}\) już to nie działa.
Tak jak pisałem rozbijam \(\displaystyle{ 56=2*2*2*7}\) i wychodziłoby mi \(\displaystyle{ n=2+2+2+7=13}\) jednak odpowiedź to \(\displaystyle{ 15}\).
Dla \(\displaystyle{ k=54=2*3*3*3}\) \(\displaystyle{ ,n=2+3+3+3=11}\) a odpowiedź to \(\displaystyle{ 29}\). Jak mam do tego podejść ?
Również \(\displaystyle{ NWW(2,3,3,3)=6}\) Zatem to też nie to

Rozbiłem w słupku \(\displaystyle{ 56}\) na \(\displaystyle{ 56=2*2*2*7}\) i jeśli zrobię \(\displaystyle{ 2*2*2+7}\) to wyjdzie \(\displaystyle{ 15}\).
Gdy rozbiję \(\displaystyle{ 54=2*3*3*3}\) i zrobie \(\displaystyle{ 3*3*3+2}\) to wyjdzie \(\displaystyle{ 29}\) tak jak trzeba.
Czy jeśli rozbiję liczbę na czynniki to żeby policzyć n muszę powtarzające się czynniki pomnożyć przez siebie a niepowtarzające się tylko dodać ?

[Gosda]

Tak, ale czy potrafisz uzasadnić czemu tak jest?

1. Rzędem permutacji cyklicznej jest długość cyklu.

2. Rząd permutacji rozbitej na rozłączne cykle jest najmniejszą wielokrotnością rzędów każdego z nich. To wymaga krótkiego uzasadnienia, może było już podane na wykładzie.

3. Dla \(\displaystyle{ k = 55}\) potrzebujemy znaleźć takie długości cykli, żeby w rozkładzie na czynniki pierwsze pojawiła się raz piątka, raz jedenastka (czemu?). Dążymy oczywiście do jak najkrótszych permutacji, więc albo jeden długi cykl, albo dwa krótsze, rozłączne. Drugi wariant daje \(\displaystyle{ 5 + 11 = 16}\).

4. Ogólnie, jeśli mamy rozkład na czynniki pierwsze \(\displaystyle{ k = \prod p_i^{\alpha_i}}\), możemy spróbować rozbicia na cykle długości \(\displaystyle{ p_i^{\alpha_i}}\). Dla \(\displaystyle{ k = 56}\) odpowiada to cyklom długości \(\displaystyle{ 8, 7}\), tak zaproponowałeś wyżej.

5. Pozostaje pokazać dwie rzeczy, jeśli chcemy być formalni. Po pierwsze, że w optymalnej permutacji (której szukamy w zadaniu), długości cykli muszą być parami względnie pierwsze. Po drugie, że jeśli mamy już dwa rozłączne cykle długości \(\displaystyle{ m, n}\), nie opłaca się ich zastąpić cyklem długości \(\displaystyle{ mn}\). To akurat proste, załóżmy bez straty ogólności, że \(\displaystyle{ 2 \le m < n}\), wtedy

\(\displaystyle{ m + n < 2n \le mn}\).

[arek1357]

n=2+2+2+7=13

Czy ja albo ktokolwiek napisał taką bzdurę?

czy raczej powinno być:

\(\displaystyle{ 2^3+7=15}\)

albo nie czyta co jest napisane albo jest ignorantem...

[a4karo]

n=2+2+2+7=13

Czy ja albo ktokolwiek napisał taką bzdurę?

czy raczej powinno być:

\(\displaystyle{ 2^3+7=15}\)

albo nie czyta co jest napisane albo jest ignorantem...

Może czyta i nie rozumie? Zbyt łatwo szafujesz obrazliwymi określeniami.