Permutacje N

[mol_ksiazkowy]

Czy istnieje nieskończony ciąg liczb naturalnych \(\displaystyle{ x_1, x_2, x_3,...}\), zawierający wszystkie liczby naturalne, i każdą tylko jeden raz i taki, że \(\displaystyle{ x_1+...+x_k}\) dzieli się przez \(\displaystyle{ k}\) dla \(\displaystyle{ k=1,2,3,...}\) ?

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

Dla jakich \(\displaystyle{ n}\) istnieje permutacja \(\displaystyle{ (x_1,...,x_n)}\) zbioru \(\displaystyle{ \{ 1, ...,n \}}\) taka, że \(\displaystyle{ x_1+...+x_k}\) dzieli się przez \(\displaystyle{ k}\) dla \(\displaystyle{ k=1,2,3,...,n}\) ?

[Dasio11]

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

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

\(\displaystyle{ x_1 + \ldots + x_{2n} + x_{2n+1} \equiv 0 \pmod{2n+1}}\) oraz \(\displaystyle{ x_1 + \ldots + x_{2n} + x_{2n+1} + k \equiv 0 \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 \(\displaystyle{ x_1, \ldots, x_{2n}, k}\). Na koniec kładziemy \(\displaystyle{ x_{2n+2} = k}\) i pyka.

[Slup]

Bardzo eleganckie rozumowanie Dasio11.

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

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

dla \(\displaystyle{ k=n-2, n-1, n}\) oraz

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

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


Zauważmy, że mamy

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

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

\(\displaystyle{ 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 \(\displaystyle{ n\geq 5}\) dostajemy nierówność

\(\displaystyle{ 3\leq \frac{n+1}{2}\leq n-2}\)

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

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

Zatem

\(\displaystyle{ 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 \(\displaystyle{ x_{n-1}\equiv\frac{n+1}{2}(\mathrm{mod}\,n-2)}\) oraz faktu, że \(\displaystyle{ x_{n-1}\in \{1,2,...,n\}}\) uzyskujemy \(\displaystyle{ x_{n-1} = \frac{n+1}{2}}\). Kończy to dowód, bo

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

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