Udowodnij istnienie

[Dario1]

Udowodnij, że jeśli A jest dziesięcioelementowym podzbiorem zbioru liczb \(\displaystyle{ \left\{ 1,2,3,...,50\right\}}\) to w A istnieją co najmniej dwa czteroelementowe podzbiory, których sumy elementów są takie same.

[Zahion]

Podzbiorów \(\displaystyle{ 4}\) elementowych \(\displaystyle{ 10}\) elementowego zbioru mamy \(\displaystyle{ {10 \choose 4} = 210}\), tj. \(\displaystyle{ 210}\) sum. Maksymalna wartość sumy wynosi \(\displaystyle{ 50 + 50 + 50 + 50 = 200}\), a minimalna \(\displaystyle{ 1 + 1 + 1 + 1 = 4}\), tj. ilość wartości sum to \(\displaystyle{ 200 - 4 + 1 = 197}\), stąd mamy, że co najmniej \(\displaystyle{ 2}\) sumy muszą być równe.

[Dario1]

Ale nie może być maksymalna równa \(\displaystyle{ 50+50+50+50}\) bo w zbiorze elementy nie mogą się powtarzać, nie jest to multizbiór podobnie dla jedynek.

[Zahion]

Wtedy mamy \(\displaystyle{ 50 + 49 + 48 + 47 = 194}\) i \(\displaystyle{ 1 + 2 + 3 + 4 = 10}\), tj. \(\displaystyle{ 185}\) wartości i \(\displaystyle{ 210}\) sum.

[Dario1]

Ale to z tego chyba wynika, że 25 sum co najmniej się powtórzy?

[Zahion]

Tak.