zasada szufladkowa Dirichleta

[monari]

Udowodnij, że w dowolnej grupie n+2 różnych liczb całkowitych są dwie, których różnica lub suma dzieli się przez 2n.

[sebnorth]

Rozpatrzmy zbiór A reszt z dzielenia przez \(2n\) danego zestawu liczb. A będzie podzbiorem \(\{0, 1...., 2n-1\}\) gdzie \(|A| \leq n+2\). Musimy udowodnić, że \(A\) zawiera dwie liczby \(m, k\) takie, że \(m+ k = 2n\) lub \(m - k =0\)

rozpatrzmy podzbiory\(\{1, 2n-1 \}, \{2, 2n-2 \}, \ldots, \{n-1, n+1 \}, \{ n \}, \{0 \}\)

jest ich dokładnie \(n+1\)

Wrzucamy liczby z \(A\) do tych podziorów, np jeśli \(5 \in A\) to \(5\) ląduje w \(\{5, 2n-5\}\).

przypadek 1: \(|A| < n+2\), wówczas istnieją co najmniej dwie liczby o tej samej reszcie, więc ich róznica jest podzielna przez \(2n\)

przypadek 2: \(|A| = n+2\)

Z ZSD wynika, że

istnieją \(m\) i \(k \in A\) takie, że \(m=p\) i \(k = 2n-p\) dla pewnego \(p \in \{1, \ldots, n-1 \} \setminus \{ n \}.\)

\(m+k = 2n\)