szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Permutacje N
PostNapisane: 25 sty 2019, o 14:14 
Użytkownik

Posty: 5772
Lokalizacja: Kraków
Czy istnieje nieskończony ciąg liczb naturalnych x_1, x_2, x_3,..., zawierający wszystkie liczby naturalne, i każdą tylko jeden raz i taki, że x_1+...+x_k dzieli się przez k dla k=1,2,3,... ?

To samo pytanie dla ciągów skończonych :

Dla jakich n istnieje permutacja (x_1,...,x_n) zbioru \{ 1, ...,n \} taka, że x_1+...+x_k dzieli się przez k dla k=1,2,3,...,n ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 25 sty 2019, o 16:12 
Moderator
Avatar użytkownika

Posty: 8286
Lokalizacja: Wrocław
1. Idzie przez forsing: definiujemy indukcyjnie ciąg x_1, x_2, \ldots różnych liczb naturalnych, który spełnia warunek zadania a ponadto \{ 1, \ldots, n \} \subseteq \{ x_1, \ldots, x_{2n} \}.

Niech n \ge 0 i załóżmy, że zdefiniowaliśmy już x_i dla 1 \le i \le 2n. Niech k będzie najmniejszą liczbą naturalną, która nie jest jeszcze elementem ciągu. Skoro 2n+1 i 2n+2 są względnie pierwsze, z chińskiego twierdzenia o resztach dostajemy takie x_{2n+1}, że

x_1 + \ldots + x_{2n} + x_{2n+1} \equiv 2n+1 \pmod{2n+1} oraz x_1 + \ldots + x_{2n} + x_{2n+1} + k \equiv 2n+2 \pmod{2n+2}.

Oczywiście liczb spełniających powyższe warunki jest nieskończenie wiele, więc możemy wybrać taką, której nie ma wśród liczb x_1, \ldots, x_{2n}, k. Na koniec kładziemy x_{2n+2} = k i pyka.
Góra
Mężczyzna Offline
 Tytuł: Permutacje N
PostNapisane: 26 sty 2019, o 18:28 
Użytkownik

Posty: 364
Lokalizacja: Warszawa
Bardzo eleganckie rozumowanie Dasio11.

Pozostał przypadek skończony. Pokazemy, że dla n\geq 5 takie permutacje nie istnieją. W rzeczywistości pokażemy trochę więcej.
Niech n\geq 5 oraz załóżmy, że dany jest ciąg x_1,...,x_n o wartościach w zbiorze \{1,2,...,n\} taki, że

x_1+...+x_k\equiv 0 (\mathrm{mod}\,k)

dla k=n-2, n-1, n oraz

x_1+x_2+...+x_n = n\cdot \frac{n+1}{2}

Wówczas x_n = x_{n-1}. W szczególności dla takich n permutacje, które spełniają warunki zadania, nie istnieją.


Zauważmy, że mamy

n\cdot \frac{n+1}{2} = x_1+x_2+...+x_n \equiv 0\,(\mathrm{mod}\,n)

czyli \frac{n+1}{2}\in \mathbb{Z}. Następnie zauważmy, że

x_n = n\cdot \frac{n+1}{2} - \left(x_1+...+x_{n-1}\right) \equiv n\cdot \frac{n+1}{2} \equiv \frac{n+1}{2}(\mathrm{mod}\,n-1)

Ponadto z faktu, że n\geq 5 dostajemy nierówność

3\leq \frac{n+1}{2}\leq n-2

Z tej nierówności, kongruencji x_n \equiv \frac{n+1}{2}(\mathrm{mod}\,n-1) oraz faktu, że x_n \in \{1,2,...,n\} uzyskujemy x_n =\frac{n+1}{2}. Stąd dalej wynika, że

x_1+...+x_{n-1} = (n-1)\cdot \frac{n+1}{2}

Zatem

x_{n-1} = (n-1)\cdot \frac{n+1}{2} - \left(x_1+...+x_{n-2}\right) \equiv (n-1)\cdot \frac{n+1}{2}\equiv \frac{n+1}{2}(\mathrm{mod}\,n-2)

Znowu na mocy nierówności, kongruencji x_{n-1}\equiv\frac{n+1}{2}(\mathrm{mod}\,n-2) oraz faktu, że x_{n-1}\in \{1,2,...,n\} uzyskujemy x_{n-1} = \frac{n+1}{2}. Kończy to dowód, bo

x_n = x_{n-1} = \frac{n+1}{2}

Zatem takie permutacje nie istnieją dla n\geq 5. W sytuacji, gdy 1\leq n \leq 4, to po pierwsze zauważmy, że wciąż musi zachodzić \frac{n+1}{2}\in \mathbb{Z} czyli n musi być liczbą nieparzystą. Stąd jedyne możliwe wartości n dla których takie permutacje istnieją to n=1 oraz n=3. Dla tych n wystarczy wziąć (1) oraz (3,1,2)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Permutacje - jak to robić ?  mcmcjj  1
 Permutacje zbioru - zadanie 3  Milenka L  0
 Permutacje - dwa przykłady  Harahido  4
 Pytanie o permutacje z powtórzeniami  qww  3
 Permutacje + Indukcja mat ?  Nessie  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl