====== Matematyka dyskretna (M) - Lista 5. ======

===== Zadanie 5 =====
Dowód z Dyskretnej Wrighta, za pomocą zasady szufladkowej Dirichleta:

Pokażemy, że jeśli $\displaystyle a_1, a_2, \ldots , a_n$ są całkowite, niekoniecznie różne, to suma $a_i + a_{i+1} + \ldots + a_{j}$ jest wielokrotnością $n$. \\
Rozważmy funkcję 
$mod n : \mathbb{Z} \to \mathbb{Z_n}$ 
zastosowaną do elementów zbioru $S = \{0, a_1, a_1 + a_2, \ldots, a_1 + a_2 + ... + a_n\}$.\\
Ponieważ $|S| = n + 1 > n = |\mathbb{Z_n}|$, zasada szufladkowa pokazuje, że dwóm różnym liczbom $a$ i $b$ ze zbioru $S$ przyporządkowana jest ta sama wartość w $Z_n$. \\
Skoro $a \bmod n = b \bmod n$, to mamy $a \equiv b \pmod n$, a zatem różnice $a - b$ i $b - a$ są wielokrotnościami liczby n. Jedna z tych różnic ma postać $a_i + a_{i+1} + \ldots + a_j$, co jest szukaną przez nas sumą będącą wielokrotnością $n$.

{{tag>[listy_zadan]}}