Gönderen Konu: Tübitak Lise 1. Aşama 2012 Soru 12  (Okunma sayısı 2163 defa)

Çevrimdışı ERhan ERdoğan

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 1421
  • Karma: +12/-0
Tübitak Lise 1. Aşama 2012 Soru 12
« : Eylül 03, 2013, 12:04:26 öö »
$\left \{ 1,2,3,4,5,6,7,8,9,10 \right \}$ kümesinin dört tane ardışık tam sayı içermeyen kaç alt kümesi vardır?

$
\textbf{a)}\ 596
\qquad\textbf{b)}\ 648
\qquad\textbf{c)}\ 679
\qquad\textbf{d)}\ 773
\qquad\textbf{e)}\ 812
$
« Son Düzenleme: Mayıs 12, 2014, 11:16:38 öö Gönderen: geo »

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1812
  • Karma: +8/-0
Ynt: Tübitak Lise 1. Aşama 2012 Soru 12
« Yanıtla #1 : Mayıs 11, 2014, 02:29:42 ös »
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.


« Son Düzenleme: Mayıs 18, 2014, 11:51:19 ös Gönderen: geo »

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 
SimplePortal 2.3.3 © 2008-2010, SimplePortal