Gönderen Konu: Tübitak Lise 2. Aşama 2005 Soru 6  (Okunma sayısı 1933 defa)

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1713
  • Karma: +8/-0
Tübitak Lise 2. Aşama 2005 Soru 6
« : Ağustos 06, 2013, 04:37:24 öö »
Terimleri tam sayılar olan bir $(a_{n})_{n=1}^{\infty }$ dizisinde, her $n\ge N$ için, $$a_{n}= \left \vert \lbrace i \mid i\le i<n \text{ ve } a_{i}+i\ge n\rbrace \right \vert $$ olacak şekilde bir $N$ pozitif tam sayısı varsa, $(a_{n})_{n=1}^{\infty }$ dizisinin en çok kaç değeri sonsuz kere alabileceğini belirleyiniz?
« Son Düzenleme: Haziran 22, 2014, 09:05:49 öö Gönderen: geo »

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2943
  • Karma: +21/-0
  • İstanbul
Ynt: 6
« Yanıtla #1 : Ağustos 06, 2013, 05:49:51 öö »
(Eren DURLANIK)

${\max  \left\{a_i\right\}\ }=K$ olsun.

İddia: $a_i$ dizisinin üstten sınırı vardır.

İspat: ${\max  \left\{a_1,\ a_2,\ \dots ,a_N\right\}\ }=K$ olsun.  $i=1,\ 2,\ \dots ,\ m-1$ için $a_i \leq K$  olsun. $a_m \leq K$  olduğunu gösterelim. $i \leq m-K-1$  için  $a_i \leq K$  olduğundan  $a_i+i<m$ olur ve dizinin tanımı gereği $a_m \leq K$  bulunur ve iddianın ispatı tamamlanır.

İddia: $a_i$  dizisi bir yerden sonra periyodik devam eder.

İspat: İlk iddiadan $a_i$  terimi yalnızca kendinden önceki  $K$  terime bağlıdır.  Dizinin alttan ve üstten sınırı da olduğundan $\left\{a_{m+1},\ a_{m+2},\dots ,\ a_{m+K}\right\}=\{a_{s+1},a_{s+2},\dots ,\ a_{s+K}\}$  olan  $m$  ve $s$  bulunmaktadır. Dizi de yalnızca kendinden önceki  $K$  terime bağlı olduğundan, $a_{m+i}=a_{s+i}$  olur ve dizi $a_m$  teriminden sonra  $s-m$  periyoduyla devam eder ve iddianın ispatı tamamlanır.

Dizi  $a_L$  teriminden itibaren periyodik olsun.  ${\max  \left\{a_i\ \right|\ }\ i \geq L\}=M$ olsun. Bundan sonra dizinin yalnızca  $a_L$  den sonraki kısmını inceleyelim. Dizinin tanımından dizi yalnızca kendinden önceki $M$  terime bağlı olarak değişir.

İddia: $a_i=M$  ise $a_{i-M}=M$  dir.

İspat:  Dizinin tanımından ve her terim yalnızca kendinden önceki  $M$  terime bağlı olduğundan $a_{i-1} \geq1,\ a_{i-2} \geq2,\ \dots ,a_{i-M} \geq M$  dir. Dolayısıyla $a_{i-M}=M$  olur ve iddianın ispatı tamamlanır.

İddia: $a_k<M-1$ ise $a_{k+M-1}<M-1$ dir.

İspat: Öncelikle $a_{k-1}=M$  olamayacağını gösterelim. Diyelim $a_{k-1}=M$  olsun.  Dizinin periyoduna  $t$ dersek $a_{k+tM-1}=M$  olur. Bir önceki iddiayı da kullanarak  $a_{k+M-1}=M$  olur. Fakat $a_k+k<k+M-1$ olduğundan ve her terim önceki  $M$  terime bağlı olduğundan  $a_{k+M-1}<M$  olur ve çelişki elde ederiz. Yani  $a_{k-1}<M$  olmalıdır. Bu kez de $a_{k-1}+k-1<M$ olacağından $a_{k+M-1}<M-1$ elde ederiz ve iddianın ispatı tamamlanır.

Şimdi $a_k<M-1$ olamayacağını gösterelim. Diyelim $a_k<M-1$ olsun.  $a_n=M$ olan bir $n$  alalım. Dizinin periyoduna  $t$  dersek  $a_{n+tM}=M$  olur. Daha önce ispatladığımız iddialardan da  $a_n=a_{n+m}=\dots =a_{n+lm}=\dots =M$  olur. Son iddiayı kullanarak $a_k<M-1$ olduğundan $a_{k+l\left(M-1\right)}<M-1$  elde ederiz.  $k+l(M-1) \equiv n \pmod M$  olan $l$  bulunur; çünkü $M-1$  ile $M$  aralarında asaldır. Öyleyse bu  $l$  için $a_{k+l\left(M-1\right)}=M$  olur; fakat  $a_{k+l\left(M-1\right)}<M-1$ olmalıydı, çelişki elde ettik. Yani  $a_k<M-1$  olamaz. Öyleyse $a_i$  dizisi yalnızca $M-1$  ve  $M$  değerlerini sonsuz kez alabilir, yani cevabımız en fazla $2$  dir. Şimdi de cevabın $2$  olduğu duruma örnek verelim.

$a_1=a_2=\dots =a_{N-2}=0,\ a_{N-1}=1,\ a_N=2$  alırsak $a_n$  dizisi $a_N$  den itibaren $2,1,2,1,\dots$  şeklinde devam eder ve böylece dizi  $2$  değerini sonsuz kez alır.
« Son Düzenleme: Haziran 22, 2014, 09:05:15 öö Gönderen: geo »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

 


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 
SimplePortal 2.3.3 © 2008-2010, SimplePortal