Zasada szufladkowa Dirichleta - ciąg

Gwynnbleid1 · Post autor: **Gwynnbleid1** » 18 cze 2012, o 18:33

Witam
Mam następujące zadanie:
Niech A będzie ustalonym jedenastoelementowym podzbiorem zbioru {1,2,...50}. Sprawdzić, stosując zasadę szufladkową Dirichleta, czy w zbiorze A muszą istnieć dwa różne trzyelementowe podzbiory takie, że sumy wszystkich liczb każdego z nich są równe.

Moje rozwiązanie:
Najmniejsza suma, jaką możemy uzyskać tworząc trzyelementowy podzbiór, to 1 + 2 + 3 = 6
Największy natomiast to 48 + 49 + 50 = 147
Zatem możliwych sum mamy: 142

Natomiast ze zbioru jedenastoelementowego możemy utworzyć (kombinacja 3 z 11) \(\displaystyle{ {11 \choose 3} = \frac{11!}{3!8!} = \frac{11 \cdot 10 \cdot 9}{2 \cdot 3} = 11 * 5 * 3 = 165}\)

Korzystam teraz z twierdzenia:
Niech \(\displaystyle{ f}\) będzie funkcją całkowitą określoną na zbiorze \(\displaystyle{ X}\), \(\displaystyle{ f : X \in Y}\) oraz niech \(\displaystyle{ \left| X \right| > k*\left| Y\right|}\). Wtedy co najmniej dla jednego \(\displaystyle{ y}\), przeciwobraz \(\displaystyle{ f ^{-1} (\left\{ y\right\})}\) ma więcej niż \(\displaystyle{ k}\) elementów.

Tutaj się trochę gubię, byłbym wdzięczny za wytłumaczenie tego twierdzenia "na chłopski rozum". Znalazłem podobne zadanie, z którego wynikło z tego twierdzenia coś takiego:(tylko nie wiem w jaki sposób) W każdym bądź razie skoro sum jest mniej niż możliwych zbiorów, zatem muszą istnieć dwa różne zbiory 3 elementowe, których sumy są takie same.

adamglos92 · Post autor: **adamglos92** » 18 cze 2012, o 20:15

tworzysz 142 szufladki (troche na wyrost ale tutaj wystarczy)
Do kazdej z nich dokladasz jeden troj elementowy podzbior.
W ten sposob w kazdej szufladce masz jeden podzbior ale zostalo ci jezszcze 18 podzbiorow. Obojetnie jakbys je rozlozyla, zawsze w co najmniej jednej szufladce beda co najmniej dwa podzbiory:)
THE END:) na wikipedii jeszcze jest sporo fajnych przykładów

Gwynnbleid1 · Post autor: **Gwynnbleid1** » 18 cze 2012, o 21:51

Czyli mam rozumieć, że twierdzenie napisane prze zemnie wyżej jest inną wersją twierdzenia podstawowego o szufladkach ? Jak zatem z niego wynika, że te zbiory mają takie same sumy ?

adamglos92 · Post autor: **adamglos92** » 19 cze 2012, o 12:00

to że zbiory mogą mieć te same sumy to tak jest po prostu:) z tego korzystasz dalej. To co ja podałem to metoda na chłopski rozum. Rozdzielasz równo elementy między szufladki jak tylko sie da tak az zostanie ci mniej elementow niz szufladke. wtedy tyle ile rozdzielilas to azdej szufladki z osobna, tyle musi byc co najmniej elementow o danej cesze.