Wykazać kombinatorycznie, szufladkowanie Dirchileta

[Smule]

Wykazać zależność w sposób kombinatoryczy

\(\displaystyle{ \sum_{i=0}^{n}{n\choose i} = 2^n}\)

\(\displaystyle{ \sum_{i=0}^{n}i{n\choose i} = n2^{n-1}}\)

Ze zbioru liczb \(\displaystyle{ 1, 2, ...,500}\) wybrano 101 liczb. Udowodnij, że wśród wybranych liczb istnieją takie dwie liczby, że są one ze sobą względnie pierwsze.

[Premislav]

1) Zlicz na dwa sposoby podzbiory zbioru n-elementowego. Z jednej strony tworząc podzbiór, dla każdego z \(\displaystyle{ n}\) elementów decydujesz, czy ma on należeć do tego podzbioru, czy nie, stąd \(\displaystyle{ 2^n}\)możliwości. Z drugiej strony masz
\(\displaystyle{ {n \choose 0}}\) podzbiorów pustych, \(\displaystyle{ {n \choose 1}}\) jednoelementowyh itd.

2) Wybierasz żydowski zarząd powierniczy do państwa polskiego spośród grona \(\displaystyle{ n}\) osób, przy czym liczebność tegoż zarządu nie jest z góry zdeterminowana. Z jednej (prawej) strony na \(\displaystyle{ {n\choose 1}=n}\) sposobów wybierasz prezesa i na \(\displaystyle{ 2^{n-1}}\) sposobów dobierasz mu członków zarządu (dla każdej z pozostałych \(\displaystyle{ n-1}\) osób decydujesz, czy ma wejść w skład zarządu, czy nie), a z lewej to wiadomo, wybierasz \(\displaystyle{ i}\) spośród \(\displaystyle{ n}\) osób, a spośród nich prezesa. Ale może być też tak, że nikt nie zdecyduje się zdjąć spodni, by udowodnić, że jest obrzezany, wówczas nikogo nie wybierasz.

3) Ale przecież to jakaś bzdura, co będzie, jeśli wybrano liczby \(\displaystyle{ 2n}\) dla \(\displaystyle{ n=1,2\ldots 101}\)