szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 19 sty 2013, o 17:36 
Użytkownik
Avatar użytkownika

Posty: 31
Lokalizacja: Polska
Mam takie zadanie:

Niech A będzie ustalonym ośmioelementowym podzbiorem zbioru \left\{1, \ 2, \  \ldots , \ 50 \right\}. Sprawdzić, stosując zasadę szufladkową Dirichleta, czy w zbiorze A muszą istnieć dwa różne czteroelementowe podzbiory takie, że sumy wszystkich liczb każdego z nich są równe.

Oczywiście wiem, co to zasada szufladkowa, ale jakoś nie mam pomysłu jak to ugryźć. Może ktoś podrzuci pomysł?
Góra
Mężczyzna Offline
PostNapisane: 19 sty 2013, o 17:58 
Administrator
Avatar użytkownika

Posty: 12358
Lokalizacja: Kraków
Szufladki to możliwe sumy 8 liczb. Jest ich tyle, ile wynosi największa suma 8 liczb, a więc

43+44+\ldots+50=372

Przedmioty, które wkładamy, to podzbiory zbioru 8-elementowego, a tych jest 2^8=256.

Widać, że brakuje przedmiotów, by wypełnić szufladki.

Wniosek jest taki, że zasada szufladkowa nie daje pozytywnej odpowiedzi.
Góra
Mężczyzna Offline
PostNapisane: 19 sty 2013, o 18:32 
Użytkownik
Avatar użytkownika

Posty: 31
Lokalizacja: Polska
Albo nie rozumiem, albo to nie tak. Mamy podzbiór 8-elementowy i dopiero w nim mają być dwa podzbiory 4-elementowe o takich samych sumach.
Góra
Mężczyzna Offline
PostNapisane: 19 sty 2013, o 18:41 
Administrator
Avatar użytkownika

Posty: 12358
Lokalizacja: Kraków
Może rzuć okiem na to:

http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Wyk%C5%82ad_3:_Zliczanie_zbior%C3%B3w_i_funkcji#Zasada_Szufladkowa

Jest tam przykład odpowiadający Twojemu problemowi.
Góra
Mężczyzna Offline
PostNapisane: 19 sty 2013, o 18:49 
Użytkownik
Avatar użytkownika

Posty: 31
Lokalizacja: Polska
To jest to! Dzięki.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 zasada szufladkowa - zadanie 7  marffy  1
 Zasada szufladkowa - zadanie 15  Nesquik  2
 Zasada szufladkowa - zadanie 5  Hnoss  3
 Zasada szufladkowa - zadanie 12  sympatia17  1
 Zasada szufladkowa - zadanie 14  max12333  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com