Zasada szufladkowa dirichleta

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
restarcik
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 12 gru 2019, o 00:00
Płeć: Mężczyzna
wiek: 20
Podziękował: 2 razy

Zasada szufladkowa dirichleta

Post autor: restarcik »

Zastanawiam się i nie mogę dojść do jednoznacznej decyzji, czy mając zadanie:

Wykaż, że wśród 10 osób, każda w wieku od 1 do 60 lat włącznie, można wskazać dwie rozłączne grupy w taki sposób, że sumy lat w obu tych grupach będą takie same. Uzasadnij, czy teza nadal pozostanie prawdziwa, gdy z grupy tej zostanie usunięta jedna osoba?

To mam rozpatrywać, że mogę wybrać zbiór pusty i pełny? Czy mam go nie rozpatrywać? (skoro nie jest to jasno określone)

Rozpatrując zbiór pusty i pełny, możliwe sumy lat \(\displaystyle{ x}\)\(\displaystyle{ 0 \leq x \leq 600}\), a samych podzbiorów mogę wygenerować \(\displaystyle{ 2^{10} = 1024}\)
No i ok... mam 601 możliwych sum 1024 możliwych podzbiorów więc z ZSD wynika, że dwie grupy muszą mieć tą samą sumę lat.

Natomiast...
rozpatrując, że nie mogę mieć zbioru pustego (zarazem nie mogę mieć i zbioru pełnego (?!), bo wtedy nie byłbym wstanie wskazać drugiego rozłącznego podzbioru niepustego), możliwe sumy lat \(\displaystyle{ x}\) wynoszą \(\displaystyle{ 1 \leq x \leq 9 \cdot 60 = 540}\).
A możliwe podzbiory to \(\displaystyle{ 2^{10} - 2 = 1022}\) (odejmując zbiór pusty i pełny).
Zadanie nadal jest prawidłowe bo na 540 możliwych sum przypada 1022 podzbiory, z czego wynika że dwa muszą mieć tą samą sumę lat.

Ale już chcąc rozwiązać drugą część zadania, napotykam problem, bo:
jeśli przyjmujemy że podzbiór może być pusty mamy 541 możliwości sum i 512 możliwych podzbiorów więc teza przestaje być prawdziwa.

A gdy przyjmiemy, że nie możemy mieć podzbioru pustego, wtedy to mamy 480 możliwych sum i 510 możliwych podzbiorów i teza nadal pozostaje prawdziwa

Czy mógłby mi ktoś wyjaśnić jak to powinno być zrobione?! Bo jak na moje rozumowanie, wszystko zależy od przyjętych założeń, niestety wtedy wyniki tego samego zadania są różne :evil:
FasolkaBernoulliego
Użytkownik
Użytkownik
Posty: 157
Rejestracja: 23 sty 2020, o 16:16
Płeć: Mężczyzna
wiek: 30
Podziękował: 14 razy
Pomógł: 18 razy

Re: Zasada szufladkowa dirichleta

Post autor: FasolkaBernoulliego »

Czy teza przestaje być prawdziwa dlatego, że nie udaje Ci się jej pokazać z zasady szufladkowej?

Nie do końca rozumiem Twój problem - to czy będziesz rozważał zbiór pusty i pełny, czy nie, zależy tylko od Ciebie. Przecież i tak wiadomo, że żaden zbiór rozłączny z pustym / pełnym nie będzie miał tej samej sumy lat. Zresztą jeśli wykażesz, że zawsze można znaleźć dwa rozłączne zbiory zbudowane jako różnice zbiorów innych, niż pusty/pełny o żądanej własności, to tym bardziej można znaleźć bez tego ograniczenia.
ODPOWIEDZ