Metoda szufladkowa

[adinho58]

Witam.
Mam problem z tym zadaniem :

Niech \(\displaystyle{ A}\) będzie zbiorem złożonym z dziesięciu dwucyfrowych liczb naturalnych.
Dowieść, ze istnieją dwa rożne i niepuste podzbiory zbioru \(\displaystyle{ A}\) takie, ze sumy liczb w obu
podzbiorach są takie same.

Moje pytanie brzmi czy do jednej szuflady wrzucamy po jednej liczbie i wtedy dodajemy go z inna szufladą i szukamy 2 innych szuflad, które po dodaniu do siebie dają taki sam wynik co te poprzednie ?

Czy zupełnie inaczej ?

[Mruczek]

Hint:    

Trzeba zrobić tak, żeby szuflady były wartościami sum możliwymi do uzyskania, a kulkami były podzbiory. Trzeba pokazać, że w pewnej szufladzie wylądują dwie kulki.

Rozwiązanie:    

Każdy z tych podzbiorów ma sumę, która jest \(\displaystyle{ \ge 10}\) oraz \(\displaystyle{ \le 90 + 91 + 92 + ... + 99=945}\), czyli suma może przyjmować \(\displaystyle{ 945 - 9 = 936}\) różnych wartości, no ale niepustych podzbiorów jest \(\displaystyle{ 2^{10} -1 = 1023}\), więc z zasady szufladkowej pewne dwa podzbiory będą miały tą samą sumę.

Ciekawostka:    

Można wzmocnić założenie tego zadania i zapytać się o dwa rozłączne podzbiory. Niewiele to zmienia, bo wystarczy wziąć te dwa podzbiory z rozwiązania podstawowej wersji zadania, które być może nie są rozłączne i odjąć od każdego z nich ich część wspólną - od sumy każdego z nich odejmiemy tyle samo, więc oba będą miały dalej tą samą sumę, ale teraz będą już rozłączne.

[adinho58]

Dziękuję, ale nie mogę dojść do tego czemu : \(\displaystyle{ 2^{10}}\) bo dlaczego odejmujemy \(\displaystyle{ 1}\) rozumiem, bo to jest ten pusty zbiór, ale czemu \(\displaystyle{ 2^{10}}\) już nie

[Mruczek]

Bo tyle jest wszystkich podzbiorów zbioru \(\displaystyle{ 10}\)-cioelementowego. Każdy element spośród tych \(\displaystyle{ 10}\)-ciu może być w danym podzbiorze lub nie. Tak więc dla każdego z \(\displaystyle{ 10}\)-ciu elementów mamy dwie możliwości. Mnożymy te dwójki dziesięć razy - dlatego mamy \(\displaystyle{ 2^{10}}\) podzbiorów.