KombinatorykaWyzwanieZadanie nr 3877
Liczby od 1 do 11 na okręgu i iloczyny liczb stojących co drugie miejsce
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\).
Świetnie.
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
- 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.
- 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\).
- 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\).
- 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\).
- 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.
Podobne zadania
- Permutacje liczb od 1 do 8 o naprzemiennie rosnących i malejących wyrazach
- Największa rodzina parami przecinających się 4-elementowych podzbiorów zbioru {1, …, 12}
- Niemalejące ciągi długości 10 o wyrazach z {1, …, 12}, w których aᵢ ≠ i dla każdego i
- Pary z 20-elementowego zbioru liczb o średniej nie mniejszej niż średnia całego zbioru