Drukuj
Dany jest zbiór złożony z dziesięciu liczb naturalnych dwucyfrowych w zapisie dziesiętnym. Pokaż, że w zbiorze tym istnieją dwa niepuste podzbiory, których sumy są równe.
Rozważmy wszystkie niepuste podzbiory tego zbioru. Jest ich dokładnie \[ 2^{10}-1 = 1023. \] Każdy taki podzbiór ma sumę będącą liczbą naturalną z przedziału \[ 10,11,12,\dots,990, \] a więc co najwyżej \[ 990 - 10 + 1 = 981 \] różnych wartości. Zatem przy próbie przypisania \(1023\) podzbiorom wartości sum do \(981\) możliwych „szufladek” zasada Dirichleta gwarantuje, że co najmniej dwa różne podzbiory otrzymają tę samą sumę. W konsekwencji w zbiorze istnieją dwa niepuste podzbiory o równych sumach.
Strony z tym zadaniem
Zasada szufladkowa Dirichleta
Sąsiednie zadania
Zadanie 4604Zadanie 4605
Zadanie 4606 (tu jesteś)
Zadanie 4607Zadanie 4609