Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Niech p będzie liczbą pierwszą większa od 3. Nazwijmy permutację \(\displaystyle{ x_1, x_2, ..., x_{p-1}}\) zbioru \(\displaystyle{ \{1, 2, ..., p-1\}}\) dobrą, jeżeli liczby \(\displaystyle{ x_1, x_1x_2, ..., x_1x_2...x_{p-1}}\) są różne mod p. Udowodnij, że istnieje co najmniej \(\displaystyle{ \phi(p-1)+2}\) dobrych permutacji.
Wydaje mi się, że dla \(\displaystyle{ p=5}\) są tylko \(\displaystyle{ 2=\phi(p-1)}\) dobre permutacje.
Dowód, że dobrych permutacji jest co najmniej \(\displaystyle{ \phi(p-1)}\)
Ukryta treść:
A w dodatku liczba wszystkich dobrych permutacji dzieli się przez \(\displaystyle{ \phi(p-1)}\):
Określmy po pierwsze permutację (działania modulo \(\displaystyle{ p}\)) \(\displaystyle{ x_1=1}\) i \(\displaystyle{ x_n=\frac{n}{n-1}}\) dla \(\displaystyle{ 1<n\leq p-1}\). Łatwo sprawdzić, że jest to istotnie permutacja (nie występuje w tym ciągu 0 i wyrazy są parami różne), a w dodatku iloczyn \(\displaystyle{ x_1x_2...x_n}\) przystaje do \(\displaystyle{ n}\) dla wszystkich możliwych \(\displaystyle{ n}\), czyli permutacja jest dobra.
Rozważmy teraz wszystkie ciągi reszt różnych od 0 i dla dwóch ciągów \(\displaystyle{ a=(x_1,x_2,...,x_{p-1})}\)\(\displaystyle{ b=(y_1,y_2,...,y_{p-1})}\) będziemy mówić, że zachodzi relacja \(\displaystyle{ a \approx b}\), gdy istnieje taka liczba całkowita dodatnia \(\displaystyle{ d}\) względnie pierwsza z \(\displaystyle{ p-1}\), że modulo \(\displaystyle{ p}\) zachodzi dla wszystkich \(\displaystyle{ i}\) równość\(\displaystyle{ y_i = x_i^d}\)
Relacja jest zwrotna i przechodnia a symetria wynika z istnienia \(\displaystyle{ d'}\) spełniającego \(\displaystyle{ dd'=k(p-1)+1}\) dla pewnego \(\displaystyle{ k>0}\) całkowitego i MTF. Określona relacja jest więc relacją równoważności. Zauważmy, że każdy ciąg będący w tej relacji z permutacją jest sam permutacją, gdyż z istnienia liczby \(\displaystyle{ d'}\) możemy wywnioskować implikację (mod \(\displaystyle{ p}\)) \(\displaystyle{ x^d=x'^d \Rightarrow x^{dd'}=x'^{dd'} \Rightarrow x=x'}\).
Zauważmy, że każda permutacja ma na pewnej pozycji generator, a wszystkie permutacje z danej klasy abstrakcji możemy uzyskać podnosząc do tej samej potęgi elementy pewnej ustalonej permutacji. Łatwo stąd widać, że każda klasa abstrakcji liczy sobie \(\displaystyle{ \phi(p-1)}\) elementów, gdyż generator podniesiony do różnych potęg \(\displaystyle{ 0<d<p-1}\) daje różne reszty, co daje nam \(\displaystyle{ \phi(p-1)}\) permutacji różniących się między sobą na co najmniej jednej pozycji, a z uwagi na MTF możemy się ograniczyć do \(\displaystyle{ d<p-1}\), bo dla większych \(\displaystyle{ d}\) otrzymywane ciągi będą powtórzeniem tych już otrzymanych. Łatwo też widać, że permutacja dobra może być w relacji tylko z inną permutacją dobrą, więc klasa abstrakcji zdefiniowanej na początku permutacji wyznacza nam \(\displaystyle{ \phi(p-1)}\) dobrych permutacji, a w dodatku liczba wszystkich dobrych permutacji jest podzielna przez tą liczbę.
