Dowód - zasada szufladkowa

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
arctic55661
Dopiero zaczynam
Dopiero zaczynam
Posty: 10
Rejestracja: 13 gru 2017, 12:49
Płeć:

Dowód - zasada szufladkowa

Post autor: arctic55661 » 01 cze 2018, 16:44

Niech A będzie ustalonym dziesięcioelementowym podzbiorem zbioru {1,2,...50}. Udowodnij stosując zasadę szufladkową Dirichleta, że w zbiorze A istnieją dwa różne pięcioelementowe podzbiory takie, że sumy wszystkich liczb każdego z nich są równe.

kerajs
Fachowiec
Fachowiec
Posty: 1394
Rejestracja: 14 lis 2016, 15:38
Otrzymane podziękowania: 598 razy
Płeć:

Post autor: kerajs » 01 cze 2018, 18:58

Ilość możliwych 5-elementowych sum S w zbiorze 10-elementowym to \({ 10\choose 5}=252\)
A drugiej strony:
\(1+2+3+4+5 \le S \le 46+47+48+49+50\\
15 \le S \le 240\)

różnych sum S jest tylko \(240-15+1=226\)
Jaki stąd wniosek?