Zadanie nr 9399626

Dana jest liczba całkowita n ≥ 2 . Niech r1,r2,r3,...,rn−1 będą odpowiednio resztami z dzielenia liczb

1,1+ 2,1+ 2+ 3,...,1+ 2+ ...+ (n − 1)

przez . Znaleźć wszystkie takie wartości , że ciąg (r1,r2,r3,...,rn− 1) jest permutacją ciągu (1,2,3 ,... ,n − 1) .

Wersja PDF

Rozwiązanie

Dla prostoty nie będziemy odróżniać ciągu

n(n − 1) rn = 1+ 2+ ...+ (n − 1) = ---------, 2

od ciągu reszt jakie dają te liczby przy dzieleniu przez ( będziemy mieli cały czas ustalone, więc nie prowadzi to do nieporozumień).

Po pierwsze wypisujemy sobie pierwszych kilka (kilkanaście) początkowych wyrazów ciągu i patrzymy dla jakich ciągi reszt są takie jak powinny być. Jak się to zrobi to narzuca się odpowiedź – będzie OK tylko dla potęg 2, czyli liczb postaci k n = 2 . Ponadto dla liczb nieparzystych ostatnia reszta rn− 1 dzieli się przez . Spróbujmy to uzasadnić.

Jeżeli n = 2k + 1 jest nieparzyste to sprawa jest prosta

(2k-+-1)2k- rn−1 = r2k = 2 = (2k + 1)k

i widać, że liczba ta jest podzielna przez (a więc nie należy do zbioru (1,2,3 ,...,n − 1) )

O zadaniu trzeba myśleć następująco: ciąg reszt będzie żądaną permutacją, jeżeli każde dwie reszty będą różne. Aby tak było wystarczy, że rb − ra nie dzieli się przez dla 1 ≤ a < b < n . Ze wzoru na sumę ciągu arytmetycznego mamy

a+-1-+-b- rb − ra = (a+ 1)+ (a + 2 )+ ⋅⋅ ⋅+ b = 2 ⋅(b − a).

Załóżmy najpierw, że ma czynnik nieparzysty, czyli jest postaci n = (2k+ 1)m i m > 1 . Spróbujmy dobrać i , żeby różnica reszt wyszła podzielna przez . Trochę kombinując, można to wymyślić:

2km (2k + 1) rkm +k − rkm−k− 1 = -------------= km (2k+ 1). 2

W powyższej równości jest jeden drobny detal, mianowicie dla m = 2 i k = 1 mamy km − k − 1 = 0 , ale przypadek n = 6 możemy rozważyć osobno (lub przyjąć, że r0 = 0 ).

Pozostało zastanowić się nad przypadkiem n = 2k . Zastanówmy się czy liczba

(a+ 1 + b )(b − a) rb − ra = ------------------, 2

gdzie 1 ≤ a < b < 2k , może dzielić się przez n = 2k . Zauważmy, że tylko jedna z liczb a + b + 1,b − a jest parzysta i w dodatku maksymalnie może dzielić się przez k 2 (bo obie liczby są mniejsze od k 2 , więc oba wyrażenia są mniejsze od 2k+1 ). Zatem liczba