ile jest liczb podzielnych przez 3

[doras]

Proszę o pomoc w rozwiązaniu zadania i przy okazji wytłumaczenie:

Ile jest liczb podzielnych przez 3, do których zapisu użyto wyłącznie cyfr 0 i 1, jeśli liczby te są 8-cyfrowe.

Z góry dziękuję

[soku11]

Szukamy wiec liczb z 3 jedynkami Pierwsza taka liczba bedzie 10000011. Teraz szukamy nastepnej i cos zauwazamy
\(\displaystyle{ a_1=10000011\\
a_2=10000101\\
a_3=10001001\\
a_4=10010001\\
a_4=10100001\\
a_4=11000001\\
...\\}\)
Teraz wystarczy zauwazyc ze 11 moze wystepowac na 6 pozycjach, 101 na 5, 1001 na 4 itd...

Dodane:
Rzeczywiscie moze byc jeszcze 6 jedynek, tak wiec:
\(\displaystyle{ a_1=10011111\\
a_3=10111101\\
a_4=10111011\\
a_5=10110111\\
a_6=10101111\\}\)

Czyli trzeba jeszcze dodac:
\(\displaystyle{ n=6+5+4+3+2+1+3+2+2+2+2=32}\)

Powinno byc dobrze POZDRO

[doras]

dzieki, ale to chyba nie jest zrobione do konca, jeszcze istnieje mozliwosc ze bedzie 6 jedynek... i wtedy liczba tez jest podzielna przez trzy

[soku11]

No tak Zaraz dopisze ;] POZDRO

[Xitami]

Powinno byc dobrze POZDRO

Ano nie jest.
Poprawna odpowiedź to 42
10000011, 10000101, 10000110, 10001001, 10001010, 10001100, 10010001, 10010010,
10010100, 10011000, 10011111, 10100001, 10100010, 10100100, 10101000, 10101111,
10110000, 10110111, 10111011, 10111101, 10111110, 11000001, 11000010, 11000100,
11001000, 11001111, 11010000, 11010111, 11011011, 11011101, 11011110, 11100000,
11100111, 11101011, 11101101, 11101110, 11110011, 11110101, 11110110, 11111001,
11111010, 11111100.

Pierwsza cyfra to oczywiście jedynka.
Pozostaje 7 cyfr. Takich, że liczba jedynek równa jest 3 jest \(\displaystyle{ {7 \choose 3}}\),
a takich które mają 6 jedynek jest \(\displaystyle{ {7 \choose 6}}\), czyli razem \(\displaystyle{ 35+7=42}\)

Można też inaczej \(\displaystyle{ (1+x)^7=1+7x+21x^2+35x^3+35x^4+21x^5+7x^6+x^7}\)
Dodajemy współczynniki występujące przy \(\displaystyle{ x^3}\) i \(\displaystyle{ x^6}\), czyli znowu \(\displaystyle{ 35+7=42}\)

[*Kasia]

Xitami, jeden drobiazg: jeśli na pierwszym miejscu jest jedynka to "pozostaje" ich tylko dwie albo pięć.

Czyli raczej: \(\displaystyle{ {7\choose2}+{7\choose 5}=42}\) - przypadkiem wychodzi to samo, ale inaczej w trakcie...

[Xitami]

Ten sam błąd popełniłem rozwiązując zadanie korzystając z funkcji tworzących.
Dzięki symetrii trójkąta Pascala otrzymałem poprawne rozwiązanie. (mało ciekawe)
W pytaniu domyślamy się, że chodzi o układ dziesiętny, można przyjąć inne podstawy i otrzymać identyczne rozwiązania. (chyba ciekawsze)

[Janusz Tracz]

Można to uogólnić dla liczb \(\displaystyle{ n+1}\) cyfrowy. Daje się też wynik przedstawić w jawnej postaci:

\(\displaystyle{ \#\left\{k\in \NN: \text{liczby } n+1 \text{ cyfrowe zbudowane z samych } 0 \text{ i } 1 \text{ podzielne przez }3\right\} = \frac{2^n+2\cos\left(\frac{n-4}{3}\pi\right)}{3}}\)