Zasada szufladkowania Dirichleta - dwie identyczne sumy

[Fixus]

Witam, poniżej zadanie które może mieć 0,1,2,3 dobrych odpowiedzi. Bardzo proszę o sprawdzenie czy dobrze rozumuję

Stosując zasadę szufladkowania Dirichleta można udowodnić, że dla zbioru A = {5,6,...,n} można wybrać dwa różne podzbiory których sumy elementów sa równe, gdy:
a) \(\displaystyle{ n=10}\)
b) \(\displaystyle{ n=7}\)
c) \(\displaystyle{ n=12}\)

Moja podstawowa bolączka to obliczenie ile podzbiorów ma dany zbiór

Np. dla odpowiedzi b \(\displaystyle{ A={5,6,7}}\). Czy mam założyć że jest to \(\displaystyle{ S(3,1)}\) czy \(\displaystyle{ S(3,2)}\) czy może jako iloczyn ?

W swoich wyliczeniach założyłem, że będe dzielił zbiór A na połowy (poza b oczywiście). Na pichotę sprawdziłem b i wyszło mi na to, że nie ma takiej sumy.

W a i c postąpiłem tak (pokaże na przykładzie a)
Ilość podzbiorów zbioru A wynosi \(\displaystyle{ S(6,3) = 90}\)
najmniejsza suma to 18 a największa to 27 w związku z tym szukam takiej funkcji \(\displaystyle{ f: X -> {18,19,20,21,22,23,24,25,26,27}}\) Te wypisane wartości to możliwe sumy. Moc zbioru Y wynosi 10 więc jeśli \(\displaystyle{ |X| > k * |Y|}\) gdzie \(\displaystyle{ k = 2}\) to znaczy, że istnieją takie dwa podzbiory w których suma elementów jest równa.

postepując w ten sposób dla punktów a i c wychodzi, że istnieją takie elementy. Gdy zastosowałem to na wszelki wypadek do b wyszło to czego się spodziewałem czyli, że nie sitnieje (zastosowałem podział \(\displaystyle{ S(3,2)}\)

Co więcej w a i c na piechotę udowodniłem, że istnieją takie podzbiory że ich sumy są sobie równe. Chciałbym jednak spytać czy dobrze to rozumiem i czy tak należy postępować. Jesli nie bardzo prosze o naprostowanie a jeśli tak to o potwierdzenie poprawności odpowiedzi

[pyzol]

Jeśli zbiór ma \(\displaystyle{ k}\) elementów, to wszystkich podzbiorów jest \(\displaystyle{ 2^k}\), wliczając również zbiór pusty.
I tak zbiór \(\displaystyle{ A}\) ma 6 elementów. Natomiast jakie są sumy. Najmniejsza, to \(\displaystyle{ 0}\) dla zbioru pustego, a największa to \(\displaystyle{ 45}\) dla zbioru \(\displaystyle{ A}\). Wniosek?

[Fixus]

w związku z tym idąc dalej przykładem a

skoro A ma 6 elementów to ilość podzbiorów wynosi 64
najmniejsza suma (jak napisałes) wynosi \(\displaystyle{ 0}\) a największa \(\displaystyle{ 45}\)

więc wychodzi na to, że sie myliłem bo
\(\displaystyle{ |X| > 2 * |Y|}\) jest nieprawdą bo \(\displaystyle{ 64}\) nie jest większe od \(\displaystyle{ 2 * 46}\) bo \(\displaystyle{ 46}\) to ilość elementów w zbiorze Y co wprowadza mi jeszcze więcej zamieszania ponieważ na piechotę znalazłem dwa podzbiory których sumy elementów sa równe więc moje wnioski musze być teraz błędne

// edit

wróc. właśnie spojrzałem na owe dwa podzbiory, które znalazłem i wzajemnie się wykluczają bo oba zawierają ten sam element co byłoby raczej sprzeczne z założeniem. w związku z tym chciałbym Cię prosić czy moje wnioski sa prawidłowe cyz błedne

[pyzol]

wróc. właśnie spojrzałem na owe dwa podzbiory, które znalazłem i wzajemnie się wykluczają bo oba zawierają ten sam element co byłoby raczej sprzeczne z założeniem. w związku z tym chciałbym Cię prosić czy moje wnioski sa prawidłowe cyz błedne

Z jakim założeniem? Zbiory różne nie muszą mieć wszystkich elementów różnych.
Wniosek jest taki mamy \(\displaystyle{ 64}\) podzbiory, którym przypisujemy maksymalnie \(\displaystyle{ 45}\) liczb. Więc najmniej 2 zbiory mają identyczną liczbę.

[Fixus]

W jaki spsoób dochodzisz tego, że najmniej 2 zbiory mają identyczną liczbę ? Ponieważ z moich wniosków - które jak widac są błędne - wychodzi, że nia ma takich dwóch podzbiorów a chciałbym zrozumieć gdzie popełniam błąd. Dlatego byłbym wdzięczny jakbyś to wyjasnił

[pyzol]

Może tak. Załóżmy, że mamy zbiór \(\displaystyle{ 64}\) elementów. Chcemy mu przypisać liczby, ale tak, by każdy element miał różną liczbę. Ile potrzebujemy liczb?

[Fixus]

\(\displaystyle{ 64}\) po jednej na element

[pyzol]

A jest tylko \(\displaystyle{ 45}\), więc kilka elementów będzie miało takie same wartości?

[Fixus]

aaa w ten sposób. Czyli skoro jest więcej podzbiorów niż sum które są dostępne w puli to w końcu musi się coś powtórzyć. Czyli zamieszałem z tym parametrem k

czyli dla \(\displaystyle{ n = 12}\) jest podobnie ponieważ podzbiorów z elementów od \(\displaystyle{ 5}\) do \(\displaystyle{ 12}\) jest 256 (\(\displaystyle{ 2 ^{8}}\)) a maksymalna suma wynosi \(\displaystyle{ 68}\) czyli elementów w zbiorze Y jest \(\displaystyle{ 69}\) również istnieją co najmniej dwa podzbiory o takiej samej sumie

idąc dalej dla \(\displaystyle{ n=7}\) ilość podzbiorów wynosi \(\displaystyle{ 8}\) z kolei maksymalna suma wynosi \(\displaystyle{ 18}\) co daje nam \(\displaystyle{ 19}\) elementów czyli nie ma takich dwóch pozdbiorów które dałyby nam tą samą sumę co się zgadza

Teraz rozumiem. Bardzo dziękuje

[pyzol]

idąc dalej dla n=7 ilość podzbiorów wynosi 8 z kolei maksymalna suma wynosi 18 co daje nam 19 elementów czyli nie ma takich dwóch podzbiorów które dałyby nam tą samą sumę co się zgadza

Nie tak do końca. Twierdzenie działa tylko w jedną stronę. Tutaj pozostaje Ci wypisać wszystkie wyniki. Dla zbioru \(\displaystyle{ A=\{1,2,3 \}}\) wszystkich podzbiorów jest \(\displaystyle{ 8}\), ale weź sobie zbiory \(\displaystyle{ \{3 \},\{1,2\}}\). Suma jest taka sama.

[Fixus]

W jedną stronę ? W sensie jeśli miejsc jest więcej niż sum to udowadniam, że conajmiej 2 mają ta samą sume, ale jak ilość miejsc jest mniejsza niż ilość sum to wcale nie znaczy, że dwa podzbiory nie mogą mieć takiej samej sumy ?

to trochę komplikuje, ale czy to twierdzenie nie powinno jednoznacznie odpowiedzieć na to pytanie ?

[pyzol]

Ad. 1. Dokładnie to znaczy. Jak widać podałem też prosty przykład, że to w drugą stronę nie działa.