szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 wrz 2013, o 03:33 
Użytkownik

Posty: 75
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
Cytuj:
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 \left\{ 0, 1, 2, ..., 9\right\} (tu pojawia się moja pierwsza wątpliwość - nie wiem czy 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 ;)
Góra
Mężczyzna Offline
PostNapisane: 16 wrz 2013, o 04:33 
Użytkownik
Avatar użytkownika

Posty: 135
Lokalizacja: Wrocław
Cytuj:
liczb naturalnych, dwucyfrowych w rozwinięciu dziesiętnym

mowa o liczbach należących do zbioru \{10,11,12,...,98,99}\}
było - 291860.htm
Góra
Mężczyzna Offline
PostNapisane: 16 wrz 2013, o 18:10 
Użytkownik

Posty: 75
Niby było, ale nie zostało niestety jednoznacznie rozwiązane. Nie wiem skąd się wzięło 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?
Góra
Mężczyzna Offline
PostNapisane: 16 wrz 2013, o 18:23 
Użytkownik
Avatar użytkownika

Posty: 135
Lokalizacja: Wrocław
Cytuj:
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 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 \{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 - \{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).
Góra
Mężczyzna Offline
PostNapisane: 17 wrz 2013, o 00:24 
Użytkownik

Posty: 75
Dzięki za szczegółowe wyjaśnienie ;).

Krótko mówiąc to 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 2 ^{n}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Permutacje dowód  buttonik  1
 funkcja tworząca z ciągu liczb naturalnych  JakubCh  13
 graf petersena nie jest hamiltonowski dowód??  alefx  2
 wartość sumy - zadanie 5  TLOTR  4
 wybieranie podzbiorów 5-elementowych ze zbioru 20-el.  Z_i_o_M_e_K  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl