Podzielność liczb

[bar03]

Dana jest liczba naturalna \(\displaystyle{ n>1}\). wykaż, że wśród \(\displaystyle{ 2n-1}\) liczb całkowitych zawsze można wybrać \(\displaystyle{ n}\) o sumie podzielnej przez \(\displaystyle{ n}\).
Wszelkie wskazówki mile widziane.

[marcinz]

Zacznij od tego, że jeśli twierdzenie jest prawdziwe dla liczb \(\displaystyle{ m,n}\), to zachodzi dla \(\displaystyle{ mn}\).

[bar03]

A mógłbyś jaśniej, bo ta wskazówka do mnie nie przemawia?

[silvaran]

Dla \(\displaystyle{ n=2}\), zawsze znajdziemy albo dwie parzyste albo dwie nieparzyste, a ich suma będzie parzysta. Weźmy dla 3. Czyli rozpatrujemy 5 liczb z powtórzeniami ze zbioru \(\displaystyle{ \left\{ 0,1,2\right\}}\) (modulo 3 - najłatwiej). Jeśli jakaś powtórzy się trzy razy to po problemie, wybieramy te trzy i mamy sumę podzielną przez 3. Czyli rozpatrujemy przypadki gdzie są max po dwa razy powtórzone no i szybko widać, że wtedy muszą wystąpić wszystkie trzy liczby przynajmniej po razie, więc wybieramy 0, 1 i 2 suma będzie podzielna przez 3. Myślę, że ten trop może być dobry

[bar03]

A ja myślę, że niekoniecznie, bo dla\(\displaystyle{ n=4}\) i większego sprawa jest znacznie bardziej skomplikowana.

[silvaran]

Zacznij od tego, że jeśli twierdzenie jest prawdziwe dla liczb \(\displaystyle{ m,n}\), to zachodzi dla \(\displaystyle{ mn}\).

No dobra, to jest w miarę łatwe do pokazania. Ale później trzeba wykazać, że problem z treści zadania jest prawdziwy dla wszystkich liczb pierwszych, co z tym?

[marcinz]

Dla liczby pierwszej \(\displaystyle{ p}\) robimy tak. Rozważmy wszystkie możliwe wybory \(\displaystyle{ p}\) liczb. Otrzymamy \(\displaystyle{ {2p-1\choose p}}\) zbiorów \(\displaystyle{ p}\)-elementowych. Oznaczmy otrzymane sumy przez \(\displaystyle{ S_1,S_2,...,S_N}\), gdzie \(\displaystyle{ N={2p-1\choose p}}\) (niektóre liczby dają tą samą sumę). Niech \(\displaystyle{ S= \sum_{i=1}^{N} {S_i}^{p-1}}\), zauważmy , że jeśli \(\displaystyle{ \forall_{i} p\nmid S_i}\), to \(\displaystyle{ {S_i}^{p-1}\equiv 1(mod\ p), S\equiv {2p-1\choose p} \not \equiv 0 (mod\ p)}\). Można jednak pokazać, że \(\displaystyle{ p|S}\).

[silvaran]

Zacznij od tego, że jeśli twierdzenie jest prawdziwe dla liczb \(\displaystyle{ m,n}\), to zachodzi dla \(\displaystyle{ mn}\).

No dobra, to jest w miarę łatwe do pokazania.

Chyba jednak wycofuję się z tego. Bo co prawda można zrobić tak, że z \(\displaystyle{ 2mn-1}\) odejmiemy \(\displaystyle{ n-1}\) (lub \(\displaystyle{ m-1}\), bez znaczenia) liczb i wtedy zostanie nam \(\displaystyle{ 2mn-n=n(2m-1)}\)
Czyli mamy \(\displaystyle{ n}\) zestawów po \(\displaystyle{ 2m-1}\) liczb, a z założenia z każdego takiego zestawu można wybrać \(\displaystyle{ m}\) liczb, których suma jest podzielna przez \(\displaystyle{ m}\). No ale mając \(\displaystyle{ n}\) zestawów liczb, których sumy są podzielne przez \(\displaystyle{ m}\), to one wszystkie razem nie muszą być podzielne przez \(\displaystyle{ mn}\). Widać to?
Weźmy np dla \(\displaystyle{ m=2,n=2}\) no i otrzymane zestawy to \(\displaystyle{ 1,1}\) oraz \(\displaystyle{ 2,2}\). I w jednym i w drugim przypadku suma jest podzielna przez dwa, ale wszystkie nie są podzielne przez cztery. Wygląda na to, że w jakiś inny sposób (nie losowy ) nalezy dobierać te liczby.

[marcinz]

Chodzi o to, że możemy trochę lepiej wybierać te liczby. Powiedzmy na początku wybieramy \(\displaystyle{ n}\), których suma jest podzielna przez \(\displaystyle{ n}\). Zostaje nam \(\displaystyle{ 2mn-1-n}\) liczb, z nich znowu wybieramy \(\displaystyle{ n}\), tak możemy zrobić \(\displaystyle{ 2m-1}\) razy. Oznaczmy sumy, które dostaliśmy przez \(\displaystyle{ A_1,A_2,...,A_{2m-1}}\), wówczas liczby \(\displaystyle{ \frac{A_1}{n},\frac{A_2}{n},...,\frac{A_{2m-1}}{n}}\) są całkowite, jest ich \(\displaystyle{ 2m-1}\), więc z założenia można wybrać \(\displaystyle{ m}\), których suma jest podzielna przez \(\displaystyle{ m}\). Przypominamy sobie, że każda suma pochodzi od \(\displaystyle{ n}\) liczb, więc wybraliśmy \(\displaystyle{ mn}\) liczb. Wiemy, że \(\displaystyle{ m|\frac{A_1+A_2+...A_{2m-1}}{n}}\), czyli \(\displaystyle{ mn|A_1+A_2+...A_{2m-1}}\).

[silvaran]

No właśnie, nie mogłem wpaść w jaki sposób lepiej dobierać te liczby

[bar03]

Mimo tylu wskazówek pozostaje jeszcze problem, jak pokazac, że \(\displaystyle{ p\mid S}\), ale to w zasadzie nie jest takie trudne. Dzięki za wszystkie wskazówki. Zadanie było naprawdę trudne.

[silvaran]

Mimo tylu wskazówek pozostaje jeszcze problem, jak pokazac, że \(\displaystyle{ p\mid S}\)

No właśnie z tym mam problem. Jakieś wskazówki?

[marcinz]

\(\displaystyle{ S}\) daje się zapisać jako suma elementów postaci \(\displaystyle{ c_{i_1,i_2,\ldots,i_s} {a_{i_1}}^{k_1} {a_{i_2}}^{k_2}\ldots {a_{i_s}}^{k_s},k_1+...+k_s=p-1}\). Wystarczy pokazać, że te \(\displaystyle{ c}\) są podzielne przez \(\displaystyle{ p}\). Wybieramy zbiór indeksów \(\displaystyle{ i_1,i_2,\ldots,i_s}\). Ustalmy jedną z sum, w której wybieraliśmy te liczby, licząc ją podnosimy podnosimy do potęgi \(\displaystyle{ p-1}\) sumę \(\displaystyle{ p}\) liczb. Ze znanego wzoru w tej sumie przy \(\displaystyle{ {a_{i_1}}^{k_1} {a_{i_2}}^{k_2}\ldots {a_{i_s}}^{k_s}}\) stoi współczynnik \(\displaystyle{ p-1 \choose {k_1,\ldots, k_s}}\). To teraz zobaczmy ile jest takich sum, w których występowały \(\displaystyle{ a_{i_1},\ldots, a_{i_s}}\). Liczb jest \(\displaystyle{ s}\), każda suma powstaje z \(\displaystyle{ p}\) liczb, więc dowolny wybór \(\displaystyle{ p-s}\) liczb spośród pozostałych daje inną sumę. Czyli wszystko trzeba pomnożyć przez \(\displaystyle{ {2p-1-s \choose p-s}}\), a więc ostatecznie współczynnik to \(\displaystyle{ {2p-1-s \choose p-s} {p-1 \choose {k_1,\ldots, k_s}}}\).