Definicje
Możesz pominąć tę część, jeśli znasz już definicje grup , grup skończonych i podgrup .
Grupy
W algebrze abstrakcyjnej grupa jest krotką (G, ∗) , gdzie G jest zbiorem, a ∗ jest funkcją G × G → G, tak że następujące:
Zamknięcie: dla wszystkich x, y w G , x ∗ y jest również w G (implikowane przez fakt, że ∗ jest funkcją G × G → G ).
Asocjatywność: dla wszystkich x, y, z w G , (x ∗ y) ∗ z = x ∗ (y ∗ z) .
Tożsamość: istnieje element e w G taki, że dla wszystkich x w G , x ∗ e = x = e ∗ x .
Odwrotnie: dla każdego x w G istnieje element y w G, taki że x ∗ y = e = y ∗ x , gdzie e jest elementem tożsamości wspomnianym w poprzednim punkcie.
Grupy skończone
Grupa skończona to grupa (G, ∗), w której G jest skończone, tzn. Ma skończoną liczbę elementów.
Podgrupy
Podgrupa (H *) z grupy (G *) jest taka, że H jest podzbiorem G (niekoniecznie podzbiorem) i (h, *) jest grupa (tj spełnia kryteria 4 powyżej).
Przykłady
Rozważ dwuścienną grupę D 3 (G, ∗), w której G = {1, A, B, C, D, E} i ∗ jest zdefiniowany poniżej (tabela taka jak ta nazywana jest tabelą Cayleya ):
∗ | 1 ABCDE - + ---------------------- 1 | 1 ABCDE A | AB 1 DEC B | B 1 AECD C | CED 1 BA D | DCEA 1 B E | EDCBA 1
W tej grupie tożsamość wynosi 1 . Również A i B są odwrotnościami siebie, podczas gdy 1 , C , D i E są odpowiednio odwrotnościami samych siebie (odwrotność 1 to 1 , odwrotność C to C , odwrotność D to D , a odwrotność E oznacza E ).
Teraz możemy sprawdzić, czy (H, ∗) gdzie H = {1, A, B} jest podgrupą (G, ∗) . Informacje na temat zamknięcia znajdują się w poniższej tabeli:
∗ | 1 AB - + ---------- 1 | 1 AB A | AB 1 B | B 1 A
w którym wszystkie możliwe pary elementów H pod * otrzymując człon w H .
Zespolenie nie wymaga kontroli, ponieważ elementy H są elementy G .
Tożsamość to 1 . To samo musi być z tożsamością grupy. Ponadto tożsamość w grupie musi być unikalna. (Czy możesz to udowodnić?)
Dla odwrotności sprawdź, czy odwrotnością A jest B , która jest członkiem H . Odwrotność B jest , który jest również członkiem H . Odwrotność 1 jest wciąż sama, co nie wymaga sprawdzania.
Zadanie
Opis
Biorąc pod uwagę skończoną grupę (G, ∗) , znajdź liczbę jej podgrup.
Wejście
Dla grupy (G, ∗) otrzymasz tablicę 2D o rozmiarze n × n , gdzie n jest liczbą elementów w G . Załóżmy, że indeks 0
jest elementem tożsamości. Tablica 2D będzie reprezentować tabliczkę mnożenia. Na przykład dla powyższej grupy otrzymasz następującą tablicę 2D:
[[0, 1, 2, 3, 4, 5],
[1, 2, 0, 4, 5, 3],
[2, 0, 1, 5, 3, 4],
[3, 5, 4, 0, 2, 1],
[4, 3, 5, 1, 0, 2],
[5, 4, 3, 2, 1, 0]]
Na przykład możesz to zobaczyć 3 ∗ 1 = 5, ponieważ a[3][1] = 5
gdzie a
jest powyższa tablica 2D.
Uwagi:
- Możesz użyć 1-indeksowanej tablicy 2D.
- Wiersz i kolumnę tożsamości można pominąć.
- Możesz używać innych formatów według własnego uznania, ale muszą one być spójne.(tzn. możesz chcieć, aby ostatni indeks był identyczny itp.)
Wynik
Liczba dodatnia reprezentująca liczbę podgrup w grupie.
Na przykład dla powyższej grupy (H, ∗) jest podgrupą (G, ∗), ilekroć H =
- {1}
- {1, A, B}
- {1, C}
- {1, D}
- {1, E}
- {1, A, B, C, D, E}
Dlatego istnieje 6 podgrup, a twoje wyniki dla tego przykładu powinny być 6
.
Poradnik
Możesz przeczytać artykuły, z którymi się łączyłem. Artykuły te zawierają twierdzenia o grupach i podgrupach, które mogą być dla Ciebie przydatne.
Punktacja
To jest golf golfowy . Odpowiedz z najniższą wygraną w liczbie bajtów.
0
element tożsamości, to mylące jest, gdy operator jest opisywany jako mnożenie ...