Zauważmy, że ciąg złożny z \(L, P, G, D\) jest spacerem wtedy i tylko wtedy, gdy \(\#L\) = \(\#P\) oraz \(\#G\) = \(\#D\). Dzieje się tak, bo żeby zacząć i skończyć w \((0, 0)\) potrzebujemy tyle samo skrętów w prawo co lewo itd.

Zliczanie: Wybierzmy połowę miejsc. W wybrane miejsca wstawmy \(L\). Ponownie wybierzmy połowę miejsc (z \(n\) - miejsca z dwóch wyborów mogą się pokrywać). W wybrane miejsca wstawiamy \(P\). Wybór miejsc rozumiemy podług tej tabelki (pierwsze miejsce reprezentuje pierwszy wybór, drugie - analogicznie):

\(\_P = P\)

\(LP = D\)

\(\_\_ = G\)

\(L\_ = L\)

Czyli na przykład: \(n = 4\), pierwszy wybór: \(L\_L\_\). Drugi wybór: \(PP\_\_\). Sumarycznie: \(DPLG\). Twierdzę, że takie wybory zliczają spacery.

Prawidłowość wyboru: \(n\) dowolne, z pierwszego wyboru mamy \(\frac{n}{2}\) \(L\), z drugiego \(\frac{n}{2}\) \(P\). Niech \(x\) to będzie liczba pokrywających się miejsc. Policzmy teraz liczbę poszczególnych kierunków:

\(\#L = \frac{n}{2} - x \) (\(\frac{n}{2}\) było na starcie, zabieramy \(x\), bo tyle się pokrywa)

\(\#P = \frac{n}{2} - x\) (Skoro po drugim wyborze \(x\) miejsc się pokrywa, a wybieraliśmy z \(\frac{n}{2}\), to na \(\frac{n}{2} - x \) stoi samo \(P\))

\(\#D = x\) (Bo \(x\) się pokrywa)

\(\#G = x \) (Bo na \(\frac{n}{2}\) coś stoi z pierwszego wyboru, wiemy, że \(x\) się pokrywa z drugim, czyli z drugiego wyboru mamy \(\frac{n}{2} - x\) nowych miejsc [niepokrywających się z pierwszym wyborem]. Czyli \(\frac{n}{2} + \frac{n}{2} - x \) to liczba miejsc, na którym coś stoi. Odejmujemy od \(n\), żeby otrzymać liczbę miejsc pustych i wychodzi \(x\)).

Czyli ten sposób zawsze wybiera prawidłowe spacery.

Zlicza każdy spacer: Niech \(S\) będzie dowolnym spacerem z zadania. \(A, B, C, D\) to odpowiednio zbiory pozycji \(L, P, G, D\) tego spaceru. Z pierwszego wyboru niech wszystkie \(L\) padną na pozycję z \(A\). To ustawia wszystkie \(L\) jak trzeba. Z drugiego, niech \(\|D\|\) \(P\) padnie na pozycję z \(D\). To ustawia wszystkie \(D\) jak trzeba. Pozostałe \(P\) z drugiego wybour \((\frac{n}{2} - \|D\|\)) niech padną na puste pozycje. To ustawia \(P\) i zarazem \(G\).

Różnowartościowość wyboru: Tabelka zdefiniowana na początku pozwala uzyskać dany skręt na dokładnie jeden sposób, więc dwa różne wybory muszą dać różne podziały.

Wzór:

Dwa razy wybieramy połowę z \(n\): \(\binom{n}{\frac{n}{2}}^2\)

Pokażemy, że każdy element w \(X_n\) ma także w tym zbiorze swoją odwrotność multiplikatywną \(\bmod n\). Korzystamy z faktu, że jeśli odwrotność multiplikatywna istnieje, to istnieje dokładnie jedna, unikalna dla każdego elementu.

Niech \(a\in X_n\). Oczywiście \(a \perp n\). Jest to warunek konieczny i wystarczający istnienia odwrotności multiplikatywnej \(a\). Pokażemy, że \(a^{-1} \in X_n\).

Czy \(a^{-1} \perp n\)?

Załóżmy, że tak nie jest. Oznacza to, że istnieje takie \(p\), że \(p \mid n \wedge p \mid a^{-1}\). Ale z definicji odwrotności mamy: \(aa^{-1} \equiv 1 \bmod n\). Ta kongruencja znaczy tyle co: \(n \mid aa^{-1}-1\). Jednak \(p \mid n\), ale \(p \nmid aa^{-1} -1\) - sprzeczność. Oznacza to, że takie \(p\) nie może istnieć.

Czy \(a^{-1}+1 \perp n\)?

Wiemy, że \(a+1 \perp n\) oraz \(a^{-1} \perp n\). Zachodzi także \((a+1)(a^{-1}) \perp n\). Ta własność to nic innego jak: \(NWD(aa^{-1}+a^{-1}, n) = 1\). Z własności \(NWD\), możemy wziąć pierwszy argument modulo drugi, nie zmieniając wyniku: \(NWD(aa^{-1}+a^{-1}, n) = NWD(1+a^{-1}, n) = 1\). Czyli \(a^{-1} + 1 \perp n\).

Pokazaliśmy, że dla dowolnego elementu z \(X_n\), jego odwrotność także należy do tego zbioru. Możemy teraz połączyć każdy element z jego odwrotnością, co daje \(1\) licząc modulo \(n\). Finalnie mamy iloczyn samych jednynek modulo \(n\), co kończy zadanie.