Równe sumy podzbiorów zbioru liczb naturalnych
: 9 lis 2019, o 20:57
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?
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?