Zasada szufladkowania i podzielność liczb

[lola456]

Witam,
mam do rozwiązania dwa zadania z zasady szufladkowania. Oba dotyczą podzielności.
1) Wykaż, że spośród dowolnego zbioru n liczb całkowitych da się wybrać niepusty podzbiór, którego suma elementów jest podzielna przez \(\displaystyle{ n}\).
2) Udowodnij, że spośród dowolnych \(\displaystyle{ n+2 }\) liczb naturalnych można wybrać dwie \(\displaystyle{ a, b }\) takie że liczba \(\displaystyle{ a^{2} - b^{2}}\) jest podzielna przez \(\displaystyle{ 2n }\).

[Premislav]

1) Ponumerujmy te liczby całkowite: nazwijmy je \(\displaystyle{ x_{1}, x_{2}\ldots x_{n}}\). Rozważmy następujące liczby:
\(\displaystyle{ x_{1}\\x_{1}+x_{2}\\x_{1}+x_{2}+x_{3}\\\ldots\\x_{1}+x_{2}+\ldots+x_{n}}\).
Tych sum (niektóre mogą się powtórzyć, ale to nie ma znaczenia) jest \(\displaystyle{ n}\), więc jeśli dają one parami różne reszty z dzielenia przez \(\displaystyle{ n}\), to w szczególności jest wśród nich taka, która daje resztę zero z dzielenia przez \(\displaystyle{ n}\), powiedzmy \(\displaystyle{ x_{1}+x_{2}+\ldots+x_{r}}\) i wówczas warunki zadania spełnia zbiór \(\displaystyle{ \left\{x_{1},x_{2}\ldots x_{r}\right\}}\),
a jeśli pewne dwie reszty się zgadzają, powiedzmy \(\displaystyle{ x_{1}+x_{2}+\ldots+x_{k}\equiv x_{1}+x_{2}+\ldots+x_{m} \pmod{n}, \ k<m, \ k,m\in \left\{1,2\ldots n\right\}}\), to różnica tych dwóch liczb, równa \(\displaystyle{ x_{k+1}+\ldots+x_{m}}\), dzieli się przez \(\displaystyle{ n}\) i wtedy zbiór
\(\displaystyle{ \left\{x_{k+1}, \ldots x_{m}\right\}}\) spełnia warunki zadania.

[arek1357]

wsk. do drugiego:

\(\displaystyle{ x_{i}=2nt_{i}+r_{i}}\)

popodnoś do kwadratu i zauważ, że reszt kwadratowych jest mniej... niż wszystkich reszt

Liczba reszt dla pierścienia:

\(\displaystyle{ \ZZ_{2n}}\)

Nie przekracza \(\displaystyle{ n+1}\)...


Bo:

\(\displaystyle{ x^2=(2n-x)^2}\)

Resztę sobie dośpiewasz...

[lola456]

Dziękuję bardzo za pomoc