Podzbiór l. naturalnych i sumy jego podzbiorów - dowód

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
iglomosh
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 6 maja 2010, o 18:05
Płeć: Mężczyzna
Podziękował: 16 razy
Pomógł: 6 razy

Podzbiór l. naturalnych i sumy jego podzbiorów - dowód

Post autor: iglomosh »

Witam ponownie

Trafiło mi się kolejne, w moim odczuciu, dość nietypowe zadanie. Pochodzi z książki autorstwa J. Jaworskiego, Z. Palki i J. Szymańskiego pt. "Matematyka dyskretna dla informatyków. Część I: Elementy kombinatoryki" (Wydawnictwo Naukowe UAM).

Zadanie 1.20 ze strony 25
Dany jest zbiór złożony z dziesięciu liczb naturalnych, dwucyfrowych w rozwinięciu dziesiętnym. Pokazać, że w tym zbiorze istnieją takie dwa niepuste podzbiory, że sumy liczb obu podzbiorów są równe.
Hm... Z tego co rozumiem mamy do czynienia z liczbami, które można zapisać jako _,0, gdzie w miejsce _ możemy wrzucić liczby naturalne ze zbioru \(\displaystyle{ \left\{ 0, 1, 2, ..., 9\right\}}\) (tu pojawia się moja pierwsza wątpliwość - nie wiem czy \(\displaystyle{ 0}\) traktować jako l. naturalną). Mógłby ktoś wskazać, jak rozwiązać takie zadanko? Jak można w tym zadaniu wykorzystać chociażby metodę szufladkową Dirichleta?

Z góry dziękuję za odpowiedź.
Pozdrawiam
Awatar użytkownika
oldj
Użytkownik
Użytkownik
Posty: 133
Rejestracja: 5 wrz 2012, o 14:55
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy
Pomógł: 37 razy

Podzbiór l. naturalnych i sumy jego podzbiorów - dowód

Post autor: oldj »

liczb naturalnych, dwucyfrowych w rozwinięciu dziesiętnym
mowa o liczbach należących do zbioru \(\displaystyle{ \{10,11,12,...,98,99}\}}\)
było - 291860.htm
iglomosh
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 6 maja 2010, o 18:05
Płeć: Mężczyzna
Podziękował: 16 razy
Pomógł: 6 razy

Podzbiór l. naturalnych i sumy jego podzbiorów - dowód

Post autor: iglomosh »

Niby było, ale nie zostało niestety jednoznacznie rozwiązane. Nie wiem skąd się wzięło \(\displaystyle{ 2 ^{10} -1}\) zbiorów. Czy to dlatego, że jest 10 elementów i każdy z nich może być elementem podzbioru albo nie, a odejmujemy 1, by odrzucić zbiór pusty?
Awatar użytkownika
oldj
Użytkownik
Użytkownik
Posty: 133
Rejestracja: 5 wrz 2012, o 14:55
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy
Pomógł: 37 razy

Podzbiór l. naturalnych i sumy jego podzbiorów - dowód

Post autor: oldj »

Czy to dlatego, że jest 10 elementów i każdy z nich może być elementem podzbioru albo nie, a odejmujemy 1, by odrzucić zbiór pusty?
tak. ogólnie, gdy mamy zbiór n-elementowy, posiada on \(\displaystyle{ 2^n}\) podzbiorów. Chodziło nam o podzbiory niepuste, więc odejmujemy jeden.

Zatem mamy 1023 możliwe podzbiory. Ile jest możliwych sum (biorąc różne liczby dwucyfrowe, minimalnie jedną, maksymalnie 10)? Należą one do zbioru \(\displaystyle{ \{10,11,...,945\}}\) (minimalnie bierzemy jednoelementowy zbiór składający się z samej 10, a maksymalnie 10-cio elementowy zbiór składający się z największych liczb dwucyfrowych - \(\displaystyle{ \{90,91,...,98,99\}}\) ), zatem jest ich 936. No i mamy Dirichleta - są 1023 podzbiory, 936 sum, a 1023 > 936, więc istnieją 2 podzbiory które mają taką samą sumę. Ja pamiętam wersję tego zadania, gdzie pytano o podzbiory rozłączne, ale to nie problem - jeśli mamy dwa podzbiory, które mają taką samą sumę elementów i mają pewne elementy wspólne, to po prostu usuwamy te elementy i powstają dwa podzbiory rozłączne z równymi sumami (odjęliśmy to samo z obu zbiorów).
iglomosh
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 6 maja 2010, o 18:05
Płeć: Mężczyzna
Podziękował: 16 razy
Pomógł: 6 razy

Podzbiór l. naturalnych i sumy jego podzbiorów - dowód

Post autor: iglomosh »

Dzięki za szczegółowe wyjaśnienie .

Krótko mówiąc to \(\displaystyle{ 2^{n}}\) można wyjaśnić przez bijekcję na zbiór binarny:
1 - element znajduje się w podzbiorze
0 - element nie znajduje się w podzbiorze
Zatem mamy 2 opcje, które dobieramy dla n elementów, stąd \(\displaystyle{ 2 ^{n}}\)
ODPOWIEDZ