Dla dowolnego niepustego podzbioru \(\displaystyle{ X}\) zbioru \(\displaystyle{ \{1, 2, . . . , n \}}\) niech \(\displaystyle{ m(X)}\) będzie sumą najmniejszej i największej liczby ze zbioru \(\displaystyle{ X}\). Niech \(\displaystyle{ S }\) będzie sumą wszystkich liczb \(\displaystyle{ m(X)}\), gdzie \(\displaystyle{ X \subset \{1, 2, . . . , n \}}\) (tzn. \(\displaystyle{ X}\) jest dowolnym niepustym podzbiory zbioru \(\displaystyle{ \{1, 2, . . . , n \}}\)). Wykazać, że liczba \(\displaystyle{ S}\) jest podzielna przez \(\displaystyle{ n + 1}\).
Uwaga: \(\displaystyle{ m(\{k \}) = 2k}\)
Sumy sum
-
arek1357
Re: Sumy sum
\(\displaystyle{ \sum_{X}^{} m(X)=?}\)
najpierw zbiory jednoelementowe: \(\displaystyle{ X=\left\{ i\right\} }\)
\(\displaystyle{ \sum_{}^{} m\left( \left\{ i\right\} \right) =2 \frac{n(n+1)}{2}=n(n+1)=0 \mod n+1 }\)
teraz podzbiory typu:
\(\displaystyle{ \left\{ i,...,j\right\}}\) - najmniejsza liczba w tym zbiorze to \(\displaystyle{ i}\) a największa to \(\displaystyle{ j}\)
Najpierw zliczamy podzbiory:
\(\displaystyle{ \left\{ 1,2\right\} \left\{ \right\} , \left\{ 2,3\right\} \left\{ \right\},...,\left\{ n-1,n\right\} \left\{ \right\} }\) - może być między nimi od zero liczb na \(\displaystyle{ 2^0 =1}\)- sposobów
potem:
\(\displaystyle{ \left\{ 1,...,3\right\} \left\{ \right\} , \left\{ 2,...,4\right\} \left\{ \right\},...,\left\{ n-2,...,n\right\} \left\{ \right\} }\) może być między nimi od zera do \(\displaystyle{ 1}\) liczb różnych na \(\displaystyle{ 2^1}\) - sposobów
-
\(\displaystyle{ \left\{ 1,...,n \right\} }\) - może być między nimi od zera do \(\displaystyle{ n-2}\) liczb różnych na \(\displaystyle{ 2^{n-2}}\) - sposobów
Reasummując sumy minimów i maximów wyniosą:
\(\displaystyle{ \sum_{i=2}^{n} 2^{i-2}\left[ 1+2+...+\left( n-i+1\right) \right] + \sum_{i=2}^{n} 2^{n-2}\left[ i+(i+1)+...+n \right] }\)
nie wdając się w rachunki otrzymamy, że sumy te wyniosą:
\(\displaystyle{ \sum_{i=2}^{n} 2^{i-2}\left[ \left( n+1\right)^2-\left( n+1\right)i \right] =0 \mod n+1}\)
cnd...
najpierw zbiory jednoelementowe: \(\displaystyle{ X=\left\{ i\right\} }\)
\(\displaystyle{ \sum_{}^{} m\left( \left\{ i\right\} \right) =2 \frac{n(n+1)}{2}=n(n+1)=0 \mod n+1 }\)
teraz podzbiory typu:
\(\displaystyle{ \left\{ i,...,j\right\}}\) - najmniejsza liczba w tym zbiorze to \(\displaystyle{ i}\) a największa to \(\displaystyle{ j}\)
Najpierw zliczamy podzbiory:
\(\displaystyle{ \left\{ 1,2\right\} \left\{ \right\} , \left\{ 2,3\right\} \left\{ \right\},...,\left\{ n-1,n\right\} \left\{ \right\} }\) - może być między nimi od zero liczb na \(\displaystyle{ 2^0 =1}\)- sposobów
potem:
\(\displaystyle{ \left\{ 1,...,3\right\} \left\{ \right\} , \left\{ 2,...,4\right\} \left\{ \right\},...,\left\{ n-2,...,n\right\} \left\{ \right\} }\) może być między nimi od zera do \(\displaystyle{ 1}\) liczb różnych na \(\displaystyle{ 2^1}\) - sposobów
-
\(\displaystyle{ \left\{ 1,...,n \right\} }\) - może być między nimi od zera do \(\displaystyle{ n-2}\) liczb różnych na \(\displaystyle{ 2^{n-2}}\) - sposobów
Reasummując sumy minimów i maximów wyniosą:
\(\displaystyle{ \sum_{i=2}^{n} 2^{i-2}\left[ 1+2+...+\left( n-i+1\right) \right] + \sum_{i=2}^{n} 2^{n-2}\left[ i+(i+1)+...+n \right] }\)
nie wdając się w rachunki otrzymamy, że sumy te wyniosą:
\(\displaystyle{ \sum_{i=2}^{n} 2^{i-2}\left[ \left( n+1\right)^2-\left( n+1\right)i \right] =0 \mod n+1}\)
cnd...