Strona 1 z 1
Wykazać, że istnieją w danym zbiorze 2 różne podzbiory
: 20 wrz 2009, o 09:40
autor: natalia2007
Dany jest zbiór złożony z \(\displaystyle{ 10-ciu}\) liczb naturalnych mniejszych od \(\displaystyle{ 107}\)
Wykazać, że istnieją w nim co najmniej dwa różne, niepuste podzbiory, których sumy elementów są jednakowe.
Wykazać, że istnieją w danym zbiorze 2 różne podzbiory
: 20 wrz 2009, o 17:29
autor: Goter
Wszystkich niepustych podzbiorów jest \(\displaystyle{ 2^{10}-1 = 1023}\).
Suma maksymalna:106+105+104+103+102+101+100+99+98+97 = 1015
Suma minimalna: 0 *
Ilość możliwych sum: 1016
sufit z 1023/1016 = 2
Z zasady szufladkowej Dirichleta wynika że przynajmniej 2 różne, niepuste pozdbiory będą miały równą sumę elementów.
*I jeszcze tutaj zależy, jak zdefiniowaliście liczby naturalne, czy zero wchodzi czy nie jeśli nie, to tutaj suma minimalna będzie 1, ilośc możliwych sum: 1015, ale dalej nic się nie zmieni, sufit z 1023/1015 to również jest 2.