KombinatorykaWyzwanieZadanie nr 3877

Liczby od 1 do 11 na okręgu i iloczyny liczb stojących co drugie miejsce

Zliczanie modulo kwadrat liczby pierwszej Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

Jedenaście miejsc rozmieszczonych na okręgu ponumerowano kolejno \(0, 1, \ldots, 10\) zgodnie z ruchem wskazówek zegara. W miejscach tych wpisujemy liczby \(1, 2, \ldots, 11\), każdą dokładnie raz; rozmieszczenia różniące się obrotem uznajemy za różne. Jeśli w miejscu \(i\) stoi liczba \(a_i\), to obliczamy sumę \(S\) jedenastu iloczynów liczb stojących w miejscach odległych o dwa (wzór poniżej).

Niech \(K\) oznacza liczbę rozmieszczeń, dla których \(S\) jest podzielna przez \(11\). Wyznacz resztę z dzielenia \(K\) przez \(121\).

\[S=a_0a_2+a_1a_3+a_2a_4+\ldots+a_8a_{10}+a_9a_0+a_{10}a_1\]

+18 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

Jak rozwiązać to zadanie?

Potrzebujesz pomocy? Pokaż wskazówkę

Rozważ jednocześnie obroty okręgu i dodawanie tej samej stałej do wszystkich liczb modulo 11. Obie operacje zachowują podzielność \(S\) przez 11. Które rozmieszczenia mają „za małą” orbitę?

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Liczby traktujemy jako reszty modulo 11 (liczba 11 to reszta 0). Rozważmy dwie operacje: obrót \(a_i\mapsto a_{i+r}\) oraz przesunięcie wartości \(a_i\mapsto a_i+c \pmod{11}\). Obie przeprowadzają rozmieszczenia na rozmieszczenia. Obrót nie zmienia \(S\), a przesunięcie daje \(S'=\sum (a_i+c)(a_{i+2}+c)=S+2c\sum a_i+11c^2\equiv S\), bo \(\sum a_i=1+2+\ldots+11=66\equiv 0 \pmod{11}\). Zatem warunek \(11\mid S\) jest stały na orbitach.
  2. Pary \((r,c)\in\mathbb{Z}_{11}^2\) tworzą grupę rzędu \(121\), więc każda orbita ma \(1\), \(11\) albo \(121\) elementów. Orbita jest mniejsza niż \(121\) tylko wtedy, gdy pewna para \((r,c)\neq(0,0)\) nie zmienia rozmieszczenia: \(a_{i+r}\equiv a_i+c\) dla wszystkich \(i\). Przy \(r=0\) musi być \(c=0\), a przy \(c=0\) liczby nie byłyby różne, więc \(r\neq 0\neq c\). Wtedy \(a_{i+kr}\equiv a_i+kc\), a ponieważ \(kr\) przebiega wszystkie reszty, \(a_j\equiv a_0+jd\) z \(d\equiv c\,r^{-1}\neq 0\).
  3. Takich „postępów arytmetycznych modulo 11” jest \(11\cdot 10=110\) (wybór \(a_0\) i \(d\neq0\)). Dla nich \(S\equiv\sum_{i=0}^{10}(u+id)(u+(i+2)d)=11u^2+ud\sum(2i+2)+d^2\sum(i^2+2i)\equiv 0\), bo \(\sum_{i=0}^{10} i=55\) i \(\sum_{i=0}^{10} i^2=385=11\cdot 35\). Wszystkie te rozmieszczenia są więc liczone w \(K\).
  4. Pozostałe rozmieszczenia rozpadają się na orbity po \(121\) elementów, na których warunek \(11\mid S\) zachodzi dla wszystkich albo dla żadnego. Zatem \(K=110+121t\) dla pewnego całkowitego \(t\).
  5. Reszta z dzielenia \(K\) przez \(121\) wynosi \(110\). (Dla kontroli: \(K=3\,553\,880=121\cdot 29\,370+110\).)

Odpowiedź: \(110\)

Czego warto się nauczyć?

Kombinatoryka to sztuka liczenia bez wypisywania wszystkiego. Najważniejsze jest rozbicie problemu na etapy.

Więcej zadań z kombinatoryki →

Podobne zadania