podział zbioru

[tukanik]

Niech \(\displaystyle{ A}\) będzie dowolnym podzbiorem \(\displaystyle{ \{ 1...., 2n-1\}}\) gdzie \(\displaystyle{ |A| = n+2}\). Musimy udowodnić, że A zawiera dwie liczby \(\displaystyle{ m, k}\) takie, że
\(\displaystyle{ m+ k = 2n}\) lub \(\displaystyle{ m - k =0}\)

[sebnorth]

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

jest ich dokładnie \(\displaystyle{ n}\).

Jeśli \(\displaystyle{ n = 1}\), wtedy \(\displaystyle{ \{ 1, \ldots , 2n-1\} = \{ 1 \}}\) i nie ma trzyelementowego podzbioru \(\displaystyle{ A}\)

Jeśli \(\displaystyle{ n = 2}\), wtedy \(\displaystyle{ \{ 1, \ldots , 2n-1\} = \{ 1,2,3 \}}\) i \(\displaystyle{ A = \{ 1,2,3 \}, 1 + 3 = 2\cdot 2}\)

w ogólnym przypadku:

1) załóżmy, że \(\displaystyle{ n \in A}\). Niech \(\displaystyle{ A' = A \setminus \{ n\}}\). \(\displaystyle{ |A'| = n+1}\). Z ZSD wynika, że istnieją \(\displaystyle{ m}\) i \(\displaystyle{ k \in A'}\) takie, że \(\displaystyle{ m=p}\) i \(\displaystyle{ k = 2n-p}\) dla pewnego \(\displaystyle{ p \in \{1, \ldots, n-1 \}}\).

\(\displaystyle{ m+k = 2n}\)

2) załóżmy, że \(\displaystyle{ n \notin A}\). Podobnie.

[tukanik]

rozpatrzmy podzbiory \(\displaystyle{ \{1, 2n-1 \}, \{2, 2n-2 \}, \ldots, \{n-1, n+1 \}, \{ n \}}\)
Nie rozumiemy dlaczego rozpatrujemy takie podzbiory? Widzę, że sumują się do 2n, ale dlaczego możemy tylko je rozważać? Przecież \(\displaystyle{ (n+2)}\)-elementowych podzbiorów 2n-elementowego jest znacznie więcej.

Po drugie, zupełnie nie rozumiem o co chodzi w punkcie 1). Co to jest ZSD? Jeżeli to zasada szufladkowa to i tak nie widzę skąd dalej wyciągasz taki wniosek.
Dzięki

[sebnorth]

pudełkami są te podzbiory dwuelementowe, ze zbioru A wysypuję obiekty do pudełek czyli np. liczba 5 trafia do pudełka \(\displaystyle{ \{5, 2n - 5 \}}\). Jeśli w którymś pudełku są dwa elementy ze zbioru \(\displaystyle{ A}\) czy \(\displaystyle{ A'}\) to te elementy sumują się do \(\displaystyle{ 2n}\), tak mi się wydaje