Olimpiady Matematyczne

Matematyka jest drzwiami i kluczem do nauki.

Roger Bacon

Komentarz

by Gość - 01/31/2011 - 19:46

Alternatywne rozwiązanie

Wykażemy, że wyrażenie $\sum_{i=0}^{n} 2 ^{n-i} {n+i \choose i}$ jest równe liczbie podzbiorów zbioru $X=\{1,2,\ldots,2n\}$ , czyli $2^{2n}$ . Oznaczmy $S_i=\{1, 2,\ldots,i\}$ . Niech funkcja $f$ każdemu podzbiorowi $Y$ zbioru $X$ przyporządkuje największy taki indeks $k\in\{0,1\ldots,n\}$ , że moc co najmniej jednego ze zbiorów $Y \cap S_{n+k}$ lub $(S_{2n}\backslash Y) \cap S_{n+k}$ wynosi $n$ . Mówiąc obrazowo, szukamy największego $k\leq n$ takiego, że spośród liczb $1,2,\ldots , n+k$ dokładnie $n$ należy do $Y$ lub dokładnie $n$ z nich do niego nie należy. Funkcja ta jest w oczywisty sposób dobrze określona i tak dalej :P Prosto wykazać, że moc rodziny $f^{-1}(k)$ wynosi $2^{n-k} {n+k \choose k}$ , ponieważ każdy zbiór $Y''$ z tej rodziny możemy rozpisać na sumę dowolnego podzbioru zbioru $S_{2n}\backslash S_{n+k+1}$ (jest ich $2^{n-k-1}$ ) oraz $k$ lub $n$ - elementowego podzbioru zbioru $S_{n+k}$ (liczba $n+k+1$ - o ile należy do $X$ - musi należeć do $Y''$ jeżeli $\overline{\overline{Y'' \cap S_{n+k}}}=n$ oraz nie może należeć gdy $\overline{\overline{Y'' \cap S_{n+k}}}=k$ ). To oznacza, że $\overline{\overline{f^{-1}(k)}}=2^{n+k-1}{n+k\choose k}+2^{n+k-1}{n+k\choose n}=2^{n-k}{n+k\choose k}$ .
Podzbiory o innej postaci nie pozwolą nam uzyskać wartości $k$ dla funkcji $f$ . Ponieważ zbiorem wartości funkcji $f$ jest zbiór $\{0,1,\ldots,n\}$ to liczba podzbiorów $X$ będzie równa $2^{2n}=\sum_{k=0}^n\overline{\overline{f^{-1}(k)}}=\sum_{k=0}^n 2^{n-k}{n+k\choose k}$ , co kończy dowód.