Ilość podzbiorów o sumie podzielnej przez 3.

lukki_173 · Post autor: **lukki_173** » 22 lut 2009, o 00:14

Witam. Proszę o pomoc w następującym zadaniu.
Zad 1
Wybieramy ze zbioru \(\displaystyle{ \{1,2,3,...,2009\}}\) podzbiór 3-elementowy, w którym suma liczb ma być podzielna przez 3. Ile jest takich podzbiorów?

Zacząłem coś liczyć.
\(\displaystyle{ \{a,b,c\} \\
3|a+b+c}\)
I teraz są dwie możliwości:
I a,b,c - dają te same reszty z dzielenia przez 3
II a,b,c - dają każda inną resztę z dzielenia przez 3
Muszę to skończyć tym sposobem.
Bardzo proszę o pomoc.

sushi · Post autor: **sushi** » 22 lut 2009, o 00:27

to juz sam rozwiązales to zadanie, teraz tylko musisz podzielic ten zbior na 3 czesci dajace reszte 0, reszte1 i reszte 2 --> ile elementow liczy kazdy podzbior i potem odpowiednia kombinacja

do roku 2007 wszytkie 3 zbiory bedą rownoliczne bo liczba 2007 jest podzielna przez 3, zatem zbior z reszta1 i reszta2 bedzie o 1 liczniejszy niz z reszta0 dla roku 2009

reszta0, reszta1, reszta 2
reszta0,reszta0, reszta0
reszta1,reszta1,reszta1
reszta2,reszta2,reszta2

lukki_173 · Post autor: **lukki_173** » 22 lut 2009, o 00:28

A poprowadzisz mi dalej rozwiązanie? Bo nie potrafię ruszyć.

sushi · Post autor: **sushi** » 22 lut 2009, o 00:48

mamy 2009 wiec najblizej do liczby podzielnej przez 3 jest liczba 2007 , ktora po podzieleniu przez 3 daje 669,
zatem zbior:
z reszta0 wynosi 669 elementow
z reszta1 wynosi 670 elementow
z reszta2 wynosi 670 elementow

wiec dla wariantu 0,1,2 to losujesz po jednej liczbie z kazdego zbioru
zatem mamy kombinacje 1z669* 1z670 * 1z670==> 669*670*670=..

reszta0,0,0 to masz kombinacje 3z669
reszta 1,1,1 to masz kombinacje 3z670
reszta2,2,2 to masz kombinacje 3z670

jezeli masz zbior skladajacy sie z 669 elementow, to wylosowanie jednego z nich to mozesz to zrobic na 669 sposobów
669, 670, 670 razem daje 2009