Yanıt: $\boxed{D}$
Soru, $2$ tabanındaki gösteriminde $1111$ içermeyen $2^{10} = 1024$ ten küçük negatif olmayan tam sayıların sayısını bulmakla özdeş. Açıklayalım: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
1&2&3&4&5&6&7&8&9&10 \\ \hline
0&0&0&1&0&1&1&1&0&0 \\ \hline
\end{array} $$ Örneğin, yukarıda $\{4,6,7,8\}$ alt kümesinin $2$ sayı tabanına dönüştürülmüş şeklini görüyoruz.
$f(n)$ ile $n$ basamaklı (başta etkisiz $0$ lar olabilir) son basamağı $0$ olan ve $1111$ içermeyen sayıların sayısını gösterelim.
$1$ basamaklı bu şekilde tek sayı, $0$. O halde, $f(1)=1$.
$2$ basamaklı sayılar, $00$, $10$. $f(2)=2$.
$f(3)=4$ ve $f(4)=8$.
$f(5)$ için, $11110$ sayısını çıkarmamız gerekiyor. Yani $f(5)=2^4-1=15$.
$f(5)$'i hesaplamanın, biraz daha değişik bir yolu var:
$f(1)$ şartını sağlayan sayıların sonuna $1110$ yazarsak, $f(5)$ şartını sağlayan bir sayı elde ederiz.
$f(2)$ şartını sağlayan sayıların sonuna $110$ yazarsak, $f(5)$ şartını sağlayan bir sayı elde ederiz.
$f(3)$ şartını sağlayan sayıların sonuna $10$ yazarsak, $f(5)$ şartını sağlayan bir sayı elde ederiz.
$f(4)$ şartını sağlayan sayıların sonuna $0$ yazarsak, $f(5)$ şartını sağlayan bir sayı elde ederiz.
Oluşan bu dörtlü grup ayrıktır. O halde, $f(5) = f(4) + f(3) + f(2) + f(1) = 15$ tir.
Genellersek, $f(n+1)=f(n)+f(n-1)+f(n-2)+f(n-3)$ elde ederiz.
Soruda, bizden istenen, $f(11)$ i bulmamız. Fibonacci benzeri bir yöntemle, diziyi oluşturursak, $$1,2,4,8,15,29,56,108,208,401,773$$ elde ederiz.
