Talia 52 kart i 13 kupek

[Peter Zof]

Talię 52 kart rozbijamy na 13 kupek po 4 karty. Udowodnij że można tak wybrać po jednej karcie z każdej kupki, że otrzymamy 13 kart różnych wartości.

Jak na razie doszedłem to tego że trzeba prawdopodobnie skorzystać z twierdzenia Halla, ale nie mam pomysłu co dalej z tym faktem zrobić.

[norwimaj]

Jak na razie doszedłem to tego że trzeba prawdopodobnie skorzystać z twierdzenia Halla,

No to już prawie rozwiązałeś zadanie. Wystarczy sprawdzić warunek Halla. Weź dowolny (powiedzmy: \(\displaystyle{ k}\)-elementowy) podzbiór zbioru wartości. Ile kupek pasuje do co najmniej jednej z tych wartości?

[Peter Zof]

Co najmniej jedna?

@edit:
Zastanowiłem się i dochodzę do wniosku że to co napisałem jest bez sensu. Jeżeli wezmę np. 2 wartości to mogę je wcisnąć do jednej kupki, jeżeli cztery to też. Ale już Pięć wartości muszę wcisnąć do dwóch kupek a więc czy to będzie \(\displaystyle{ \lceil \frac{k}{4} \rceil}\)?

[norwimaj]

Dla ustalenia notacji podaję link do twierdzenia o warunku Halla: .

W tym przypadku mamy:
\(\displaystyle{ V_1}\) — zbiór wszystkich wartości,
\(\displaystyle{ V_2}\) — zbiór wszystkich kupek.
Mamy więc \(\displaystyle{ |V_1|=|V_2|=13}\).
Niech \(\displaystyle{ K}\) będzie dowolnym, \(\displaystyle{ k}\)-elementowym podzbiorem \(\displaystyle{ V_1}\). Ile jest kupek, które mają choćby jedną kartę o wartości ze zbioru \(\displaystyle{ K}\)? Uwzględnij to, że każdej wartości odpowiadają \(\displaystyle{ 4}\) karty. W szczególności dwóch wartości nie zmieścisz na jednej kupce, bo musiałoby na tej kupce być co najmniej \(\displaystyle{ 8}\) kart.