Matematyka dyskretna (M) - Lista 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.