Zbiór zadań, (zadania różne)
Zadanie 275
Ile jest liczb naturalnych 0 < n < 1000, które wyrażone w systemie binarnym zawierają parzystą liczbę jedynek?
Rozwiązanie
Wypiszmy kilka początkowych liczb w postaci binarnej łącznie z zerem:
0 - 0000
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101
6 - 0110
7 - 0111
8 - 1000
Wśród liczb od 0 do 7 są 4 z parzystą liczbą jedynek i 4 z nieparzystą liczbą jedynek. Liczby od $8 = 2^3$ do $15 = 2^4-1$ będą także zawierały po 4 liczby z parzystą liczbą jedynek i 4 liczby z nieparzystą liczbą jedynek, ponieważ w pierwszej kolumnie cyfra 0 zostanie zastąpiona cyfrą 1, a pozostałe nie zmienią się. Razem dla $n<2^4$ mamy po $2^3$ liczb obu rodzajów.
Ogólnie dla $n<2^k$ otrzymujemy po $2^{k-1}$ liczb obu rodzajów.
Dla $n<2^{10}$ mamy $512$ liczb z parzystą liczbą jedynek.
Ponieważ $1000 = 2^{10}-24$, więc należy sprawdzić $24$ liczby $1000 \le n < 2^{10}$. Wśród tych liczb jest $12$ o parzystej liczbie jedynek. Pomijając liczbę 0 łącznie otrzymujemy $512 - 12 - 1 = 499$ liczb spełniających warunki zadania.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>