Kombinatoryka/dyskretna

Adrian112 · Post autor: **Adrian112** » 22 kwie 2016, o 08:47

Bardzo proszę o rozwiązanie tego zadania.
Mając danych dowolnych 10 różnych liczb dodatnich całkowitych mniejszych od 107, pokaż, że
istnieją dwa
rozłączne podzbiory tych liczb, których elementy dają taką samą sumę. Odpowiedź uzasadnij.

z góry dziekuję emotka

kicaj · Post autor: **kicaj** » 22 kwie 2016, o 09:03

Wszystkich możliwych sum jest \(\displaystyle{ 1+106 +...+97 =5\cdot 204 +1 =1021}\) zaś wszystkich podzbiorów zbioru \(\displaystyle{ 10}\) elementowego mamy \(\displaystyle{ 2^{10} =1024 >1021}\) zatem pewne dwa podzbiory dają taką samą sumę. Usuwając z nich ich wspólne elementy otrzymamy szukane zbiory.