Podzbiory
-
- Użytkownik
- Posty: 273
- Rejestracja: 18 paź 2007, o 21:35
- Płeć: Kobieta
- Lokalizacja: Wrocław
- Podziękował: 22 razy
Podzbiory
Niech A będzie dowolnym 10-elementowym podzbiorem zbioru [50]. Pokazać, ze w A istnieją dwa rożne 5-elementowe podzbiory, których sumy elementów są równe.
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Podzbiory
Domyślam się, że \(\displaystyle{ [50]=\{1,2, \dots , 50 \}}\).
Zauważmy, że \(\displaystyle{ A}\) ma \(\displaystyle{ {10 \choose 5}=252}\) podzbiorów, a sumy ich elementów zawierają się między \(\displaystyle{ 1+2+3+4+5=15}\), a \(\displaystyle{ 46+47+48+49+50=240}\). Skoro więc mamy \(\displaystyle{ 252}\) podzbiorów oraz mniej niż \(\displaystyle{ 252}\) sum, to z zasady szufladkowej Dirichleta pewne dwa muszą mieć tę samą sumę elementów.
Q.
Zauważmy, że \(\displaystyle{ A}\) ma \(\displaystyle{ {10 \choose 5}=252}\) podzbiorów, a sumy ich elementów zawierają się między \(\displaystyle{ 1+2+3+4+5=15}\), a \(\displaystyle{ 46+47+48+49+50=240}\). Skoro więc mamy \(\displaystyle{ 252}\) podzbiorów oraz mniej niż \(\displaystyle{ 252}\) sum, to z zasady szufladkowej Dirichleta pewne dwa muszą mieć tę samą sumę elementów.
Q.