Równe sumy podzbiorów zbioru liczb naturalnych

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Szustarol
Użytkownik
Użytkownik
Posty: 63
Rejestracja: 10 mar 2018, o 18:11
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 12 razy
Pomógł: 1 raz

Równe sumy podzbiorów zbioru liczb naturalnych

Post autor: Szustarol »

Witam,
Trześć zadania brzmi tak:

Pokazać, że dla dowolnego zbioru ośmiu różnych dwucyfrowych liczb naturalnych niewiększych niż 36 istnieją dwa rozłączne podzbiory,
których elementy sumują się do tej samej liczby.

Próbowałem podejść do tego tak:
Wg. mojej interpretacji, w zadaniu nie bierzemy pod uwage podziału na zbiór pusty bądź pełny.
Mamy więc \(\displaystyle{ \left\{ _{2}^{8} \right\}-1 = 127 }\) podziałów.

Teraz sprawdzamy możliwe sumy. Podzbiory moga być 1, 2, ... 7-mio elementowe, więc nasze sumy zawierają się w przedziale
od \(\displaystyle{ 10}\), do \(\displaystyle{ 36+35+34+33+32+31+30=231}\)
Łatwo więc zauważyć, że sum mamy \(\displaystyle{ 221}\).

Jeśli dla danego podzbioru po podziale nadamy dowolną sumę, to suma drugiego podzbioru jest wyznaczona jednoznacznie.

Jeśli natomiast elementy mają się sumować do tej samej liczby, to musi być ona większa od \(\displaystyle{ 46}\), ponieważ jest to
najmniejsza możliwa do uzyskania suma, jeśli dzielimy zbiór na równoliczne podzbiory, tj. spośród dwóch z utworzonych podzbiorów,
conajmniej jeden ma sumę większą bądź równą 46, więc liczba możliwych sum ogranicza się do \(\displaystyle{ 231-46 = 185}\)

Teraz należy zadać pytanie, ile możemy utworzyć podziałów takich, że suma składników jest równa w obu podzbiorach. Tutaj już się kompletnie pogubiłem i porzuciłem tą metodę. Liczyłem na zastosowanie Zasady Dirichleta, ale niestety sum jest więcej, niż podziałów.


Drugie podejście zakładało skorzystanie z Liczby bella - czyli nie dzielimy tylko na dwa podzbiory, ale na kilka.
Liczba podziałów jest równa (bez zbioru pustego) \(\displaystyle{ B _{8}-1 = 4139}\) . Sumy pozostają takie, jak wcześniej,
mamy więc 221 sum. Jest 4139 podziałów i 221 sum, więc każdemu "pierwszemu" podzbiorowi z danego podziału nadajemy jedną z sum. Tutaj porzuciłem drugą metodę, ponieważ rozważanie ilości możliwych przydzieleń jest zależne od ilości podziałów - prawdopodobnie jest to metoda z liczeniem bez końca.


Próbowałem również w jeszcze inny sposób. Mianowicie, liczba podzbiorów zbioru 8-mio elementowego jest równa \(\displaystyle{ 2 ^{8} }\). Mamy więc 256 podzbiorów, a tylko 231 sum. Jasnym jest więc, że dwa podzbiory mają taką samą sumę, ale nie da się w ten sposób wykazać, że są one rozłączne, a taki jest warunek zadania.

Miałem jeszcze kilka pomysłów, ale również nieudanych, więc oszczędzę sobie wypisywania ich tutaj, ponieważ uważam, że nic nie wniosą do dyskusji.

Czy ktoś mógłby udzielić wskazówki jak rozwiązać to zadanie?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Równe sumy podzbiorów zbioru liczb naturalnych

Post autor: Dasio11 »

Szustarol pisze: 9 lis 2019, o 20:57Próbowałem również w jeszcze inny sposób. Mianowicie, liczba podzbiorów zbioru 8-mio elementowego jest równa \(\displaystyle{ 2 ^{8} }\). Mamy więc 256 podzbiorów, a tylko 231 sum. Jasnym jest więc, że dwa podzbiory mają taką samą sumę, ale nie da się w ten sposób wykazać, że są one rozłączne, a taki jest warunek zadania.
Wskazówką jest, że to dobry trop.
Szustarol
Użytkownik
Użytkownik
Posty: 63
Rejestracja: 10 mar 2018, o 18:11
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 12 razy
Pomógł: 1 raz

Re: Równe sumy podzbiorów zbioru liczb naturalnych

Post autor: Szustarol »

Ok, idąc dalej tym tropem-
mamy co najmniej dwa takie zbiory, które mają tą samą sumę. Należy teraz wykazać, że są to zbiory rozłączne. Sprawdzam na ile sposobów mogę utworzyć podzbiory o takich samych sumach, listując wszystkie zbiory rozłączne.
1) Jeśli dzielę na podzbiory siedmioelementowe i singletony, to nie istnieją podzbiory o tej samej sumie, ponieważ minimalna suma podzbioru o mocy 7 jest większa od maksymalnej sumy singletonu.
2) W przypadku podziału na zbiory o mocy 6 i 2, zachodzi taki sam przypadek.
3) Wyżej wymieniony tok rozumowania zachodzi również dla podzbiorów o rozmiarach:
5 i 1, 6 i 1, 4 i 1, 1 i 1.
4) Mamy więc takie możliwości podziałów, które utworzą prawidłową sumę:
5 i 3, 5 i 2, 4 i 4, 4 i 3, 4 i 2, 3 i 3, 3 i 2, 3 i 1, 2 i 2, 2 i 1
5) Każdych z wyżej podanych podziałów jest:
5 i 3: \(\displaystyle{ \frac{8!}{5!3!} = 56}\)
5 i 2: \(\displaystyle{ \frac{8!}{5!2!} = 168}\)
4 i 4: \(\displaystyle{ \frac{8!}{4!4!2!} = 35}\) (dzielę na 2, ponieważ zespoły nie są rozróżnialne)
4 i 3: \(\displaystyle{ \frac{8!}{4!3!} = 280}\)
4 i 2: \(\displaystyle{ \frac{8!}{4!2!2!} = 420}\) (ponownie dzielę na 2, ponieważ powstaną 2 podzbiory 2-elementowe które są równoliczne)
3 i 3: \(\displaystyle{ \frac{8!}{3!3!2!} = 560}\) (ponownie dzielę na 2, ponieważ powstaną 2 podzbiory 2-elementowe które są równoliczne)
3 i 2: \(\displaystyle{ {8 \choose 3}\cdot {5 \choose 2} = 560}\)
3 i 1: \(\displaystyle{ {8 \choose 3}\cdot 5 = 280}\)
2 i 2: \(\displaystyle{ {8 \choose 2}\cdot {6 \choose 2} \cdot 0,5 = 210}\)
2 i 1: \(\displaystyle{ {8 \choose 2}\cdot 6 = 168}\)

6) Mamy w sumie \(\displaystyle{ 2737}\) podziałów, które spelniają warunki zadania.
7) Zauważam, że podzialów typu 4 i 3, 4 i 2 itp. mam więcej niż 210, czyli ilość możliwych sum.
8) Biorę na przykład podział na 3 i 3, ponieważ ma on największą możliwą ilość podziałów, czyli \(\displaystyle{ 560}\).
Po takim podziale, zbiór 8 elementowy, dzielimy na dwa zbiory o mocy 3, i jeden o mocy 2.
Maksymalna suma mocy 3: \(\displaystyle{ 36+35+34=105}\)
Minimalna suma mocy 3: \(\displaystyle{ 10+11+12=33}\)
Maksymalna i minimalna suma mocy 2: \(\displaystyle{ 71 - 21}\) - 50 sum.
Ilość sum mocy 3: \(\displaystyle{ 72}\)

Aby sumy były takie same, muszą się zgadzać sumy podzbiorów 3-elementowych, lub 3 i 2- elementowych, lub wszystkich na raz.
Mamy więc "zablokowaną" sumę zbiorów o mocy 3- wybieramy ją na \(\displaystyle{ 72}\) sposoby, a do tego sumę zbioru o mocy 2 na 50 sposobów.
W sumie \(\displaystyle{ 3600}\) sposobów, a to już o wiele więcej, niż liczba dostępnych sum, wiec rozumowanie w tym miejscu upada.

Dalej już nie mam pojęcia jak postępować, bo dla innych podziałów sytuacja wygląda analogicznie, opisałem tu jeden z wybranych


Wpadłem na jeszce jeden pomysł, ale nie wiem czy jest on poprawny - jeśli mamy \(\displaystyle{ 256}\) podziałów na podzbiory, a \(\displaystyle{ 221}\) sum, to wiadomo, że dwa z mają tą samą sumę. Jeśli jednak nie są one rozłączne (tj. mają te same elementy), to możemy odjąć którykolwiek element z ich części wspólnej nie zmieniając ich sumy - ponieważ w obu przypadkach dodaje się on do sumy zarówno pierwszego, jak i drugiego podzbioru.
Możemy tak uczynić dla każdego elementu z ich części wspólnej, aby otrzymać dwa podzbiory o równych sumach, ale bez części wspólnej, c.n.d.
Nie wiem tylko, czy ta metoda jest spójna z zasadą Dirichleta, tzn. czy jej użycie PO użyciu zasady szufladkowania ma sens.
Ostatnio zmieniony 10 lis 2019, o 13:27 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: co najmniej. Symbol mnożenia to \cdot.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Równe sumy podzbiorów zbioru liczb naturalnych

Post autor: Premislav »

Szustarol pisze:Wpadłem na jeszce jeden pomysł, ale nie wiem czy jest on poprawny - jeśli mamy \(\displaystyle{ 256}\) podziałów na podzbiory, a
\(\displaystyle{ 221}\) sum, to wiadomo, że dwa z mają tą samą sumę. Jeśli jednak nie są one rozłączne (tj. mają te same elementy), to możemy odjąć którykolwiek element z ich części wspólnej nie zmieniając ich sumy - ponieważ w obu przypadkach dodaje się on do sumy zarówno pierwszego, jak i drugiego podzbioru.
No i rozwiązałeś zadanie z dokładnością do pogrubionego przeze mnie stwierdzenia i do pomyłki z \(\displaystyle{ 221}\) zamiast \(\displaystyle{ 231}\), dokładniej wyrzucenie części wspólnej nie zmienia różnicy między sumami elementów tych podzbiorów. Ale sądzę, że coś takiego właśnie miałeś na myśli.

Sorry, ale tego rozpisywania wcześniej nie czytałem, szkoda mi czasu.
ODPOWIEDZ