Może się wydawać, że byłoby bardzo trudno wskazać jakieś wspólne elementy tych problemów. Okazuje się jednak, że rozwiązania wszystkich czterech opierają się na tym samym spostrzeżeniu – fundamentalnej własności pewnych obiektów algebraicznych, o których opowiemy dalej. Spróbujemy odkryć tę własność, rozwiązując ostatnie zadanie.

Tablica świetlna składa się ze zbioru  żarówek  Konfigurację tablicy utożsamimy z podzbiorem  zawierającym dokładnie te żarówki, które są w tej konfiguracji zapalone. Przełącznikowi natomiast przyporządkujemy podzbiór  będący obszarem jego działania. W wyniku naciśnięcia przełącznika  przy wyświetlonej konfiguracji  otrzymamy konfigurację odpowiadającą różnicy symetrycznej

zbiorów  i   Liczba konfiguracji, które możemy wyświetlić, jest więc równa liczbie różnych podzbiorów zbioru  które możemy otrzymać ze zbiorów odpowiadających przełącznikom, stosując operację „  ”.

Przyjrzyjmy się kilku własnościom tej operacji. Wprost z własności różnicy symetrycznej zbiorów wynika, że dla dowolnych konfiguracji:

i

ii

iii

 (dzięki temu możemy pomijać nawiasy).

Zamiast pojedynczych konfiguracji rozpatrzymy teraz pewne ich zbiory. Niech  będzie zbiorem przełączników, a   – zbiorem wszystkich konfiguracji możliwych do otrzymania za ich pomocą z konfiguracji pustej  (wszystkie żarówki początkowo zgaszone). Oczywiście, jeśli dwie konfiguracje  i   należą do zbioru  to również konfiguracja  należy do

Załóżmy teraz, że naszą konfiguracją początkową jest pewna niepusta konfiguracja  Wtedy zbiór

opisuje wszystkie konfiguracje możliwe do uzyskania za pomocą przełączników ze zbioru  zaczynając od konfiguracji początkowej  Zastanówmy się nad związkiem między zbiorami  i   dla różnych konfiguracji początkowych  i   Naturalnym pytaniem jest, czy za pomocą przełączników ze zbioru  można uzyskać tę samą konfigurację, zaczynając od dwóch różnych konfiguracji początkowych. Załóżmy więc, że zbiory  i   mają niepustą część wspólną, to znaczy pewna konfiguracja możliwa jest do uzyskania zarówno z konfiguracji początkowej  jak i z   Innymi słowy,  dla pewnych konfiguracji  Wtedy na mocy własności dodawania konfiguracji

Mamy więc  a zatem konfigurację  można uzyskać z konfiguracji  za pomocą przełączników z   Analogicznie dowodzimy, że  a stąd

Okazuje się więc, że dla różnych stanów początkowych tablicy zbiory konfiguracji możliwych do uzyskania za pomocą przełączników ze zbioru  są takie same lub rozłączne. Zbiór wszystkich możliwych konfiguracji tablicy dzieli się zatem na sumę rozłącznych zbiorów  dla pewnych konfiguracji początkowych  Wykorzystamy jeszcze prostą obserwację, że każdy ze zbiorów  ma tyle samo elementów co  Stąd liczba wszystkich możliwych konfiguracji tablicy jest wielokrotnością liczby zbiorów w   Oczywiście, liczba wszystkich konfiguracji tablicy jest równa  (każda z   żarówek może być zgaszona lub zapalona), a więc liczba elementów zbioru  musi być potęgą dwójki.

Decydującą rolę w powyższym rozumowaniu odegrały własności (i)–(iii) operacji  oraz to, że dla dowolnych  z   również  jest w   Okazuje się, że podobne rozumowanie można zastosować w wielu innych sytuacjach – w szczególności w rozwiązaniach pozostałych zadań. Podobnie bowiem dowodzi się twierdzenia Lagrange’a dotyczącego grup, które stanowi tutaj kluczowy element rozumowań.

Rozpatrzmy zbiór  w którym określone jest działanie „  ”. Zbiór ten nazwiemy grupą, jeśli działanie „  ” spełnia następujące warunki:

(1)

jest łączne, czyli

(2)

ma element neutralny, oznaczany jako  spełniający  dla dowolnego elementu  z 

(3)

dla każdego elementu  z   istnieje element (oznaczany przez  ) odwrotny do niego, czyli taki, że

Podgrupą grupy  nazywamy podzbiór  zamknięty na działanie „  ” oraz na branie elementu odwrotnego względem tego działania. To znaczy, że jeśli elementy  i   należą do zbioru  to należą do niego również elementy  i   Liczbę elementów grupy  nazywamy jej rzędem i oznaczamy

Zauważmy, że określony powyżej zbiór konfiguracji tablicy świetlnej wraz z operacją „  ” jest grupą. Konfiguracja pusta  jest tu elementem neutralnym, a każda konfiguracja  jest swoją odwrotnością, gdyż  Łatwo również sprawdzić, że zbiór konfiguracji możliwych do uzyskania za pomocą danego zbioru przełączników (gdy startuje się z konfiguracji  ) jest podgrupą tej grupy.

Wspomniane wyżej twierdzenie Lagrange’a brzmi następująco:

Idea dowodu tego twierdzenia opiera się na pomyśle przedstawionym w rozwiązaniu zadania: zbiór elementów  można podzielić na rozłączne podzbiory postaci  równoliczne z 

Zastosowanie tego twierdzenia do grupy konfiguracji tablicy świetlnej i jej podgrupy konfiguracji, otrzymywanych za pomocą podanego zbioru przełączników, daje natychmiastowe rozwiązanie zadania 4.

W dalszych rozważaniach będzie użyteczny pewien szczególny przypadek twierdzenia Lagrange’a. Niech  będzie grupą skończoną, a   jej dowolnym elementem. Wtedy istnieje taka liczba naturalna  że element

(co zapisujemy w skrócie  ) jest równy elementowi neutralnemu grupy  Istotnie, ponieważ grupa  jest skończona, to dla pewnych liczb naturalnych  musi zachodzić  Ale wtedy

Najmniejszą liczbę  taką że  nazywamy rzędem elementu  i oznaczamy  Jest jasne, że elementy  są parami różne oraz  jest podgrupą grupy  Nazywa się ją podgrupą generowaną przez  i oznacza  Zatem  i na mocy twierdzenia Lagrange’a   jest dzielnikiem  Zauważmy jeszcze, że jeśli dla pewnej liczby całkowitej  zachodzi równość  to  dzieli  oraz że

Przyjrzymy się teraz przykładowi – grupie, którą wykorzystamy w rozwiązaniach zadań 1 i 2.

Niech  będzie liczbą pierwszą. Rozpatrzmy zbiór  z działaniem „ ” określonym dla dowolnych  za pomocą wzoru

Nietrudno sprawdzić, że jest to grupa. Łączność działania „  ” wynika z łączności mnożenia, a elementem neutralnym jest 1. Istnienie elementu odwrotnego do danego elementu  można uzasadnić następująco. Dla różnych liczb  reszty z dzielenia  i   przez  są różne i niezerowe. W przeciwnym razie mielibyśmy, że  a stąd  lub  co jest niemożliwe. Dla pewnego  reszta z dzielenia  przez  jest więc równa 1, czyli

Grupę tę nazywamy grupą multiplikatywną reszt modulo  i oznaczamy ją przez  Rząd  jest, oczywiście, równy  a więc z tego, co wiemy o własności rzędów elementów, wynika, że w   dla dowolnego  mamy  Mamy stąd natychmiast Małe Twierdzenie Fermata, które mówi, że dla dowolnej liczby całkowitej  i dowolnej liczby pierwszej  liczba  jest podzielna przez

Teraz możemy już rozwiązać pozostałe zadania.