Gönderen Konu: 2024 Antalya Matematik Olimpiyatı 10. Sınıf Soru 20  (Okunma sayısı 424 defa)

Çevrimdışı matematikolimpiyati

  • Geo-Maniac
  • ********
  • İleti: 1.562
  • Karma: +4/-0
2024 Antalya Matematik Olimpiyatı 10. Sınıf Soru 20
« : Haziran 16, 2024, 11:58:12 ös »
$a,b,c$ harfleri yardımıyla oluşturulan ve $a$ harfinin çift sayıda bulunduğu tüm $40$ harfli kelimelerin sayısı $S$ olsun. $S$ sayısının $55$ ile bölümünden kalan kaçtır? (Uyarı : Sıfır da bir çift sayıdır.)

$\textbf{a)}\ 24  \qquad\textbf{b)}\ 2  \qquad\textbf{c)}\ 54  \qquad\textbf{d)}\ 1  \qquad\textbf{e)}\ 15$

Çevrimdışı Metin Can Aydemir

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 1.338
  • Karma: +9/-0
Ynt: 2024 Antalya Matematik Olimpiyatı 10. Sınıf Soru 20
« Yanıtla #1 : Haziran 17, 2024, 06:36:19 öö »
Cevap: $\boxed{D}$

$k\in\{0,1,2,\dots,20\}$ için $a$ sayısı $2k$ defa bulunsun. Bu durumda $b$ ve $c$ sayıları toplamda da $40-2k$ sayıda bulunacaktır. $b$'nin $m$ tane bulunması durumunda tekrarlı permütasyondan, $$\frac{40!}{(2k)!m!(40-2k-m)!}$$ tane kelime olacağından $2k$ tane $a$ için $$\sum_{m=0}^{40-2k}\frac{40!}{(2k)!m!(40-2k-m)!}$$ kelime ve tüm $k$ değerleri için toplarsak, $$S=\sum_{k=0}^{20}\sum_{m=0}^{40-2k}\frac{40!}{(2k)!m!(40-2k-m)!}=\sum_{k=0}^{20}\sum_{m=0}^{40-2k}\frac{40!}{(2k)!(40-2k)!}\cdot \frac{(40-2k)!}{m!(40-2k-m)!}$$ $$=\sum_{k=0}^{20}\sum_{m=0}^{40-2k}\dbinom{40}{2k}\dbinom{40-2k}{m}$$ olacaktır. İçteki toplamda $m$'den bağımsız olan terimleri dışarı atabiliriz, yani $$S=\sum_{k=0}^{20}\dbinom{40}{2k}\sum_{m=0}^{40-2k}\dbinom{40-2k}{m}=\sum_{k=0}^{20}2^{40-2k}\dbinom{40}{2k}$$ olacaktır çünkü $(1+1)^{40-2k}=\sum\limits_{m=0}^{40-2k}\binom{40-2k}{m}$'dir. $$(2+1)^{40}=\sum_{r=0}^{40}\dbinom{40}{r}2^{40-r}$$ $$(2-1)^{40}=\sum_{r=0}^{40}\dbinom{40}{r}2^{40-r}(-1)^{r}$$ toplamlarını da toplarsak, $r$'nin tek olduğu terimler birbirini götürür ve $$3^{40}+1=2\sum_{k=0}^{20}2^{40-2k}\dbinom{40}{2k}$$ elde edilir. Dolayısıyla, $S=\frac{3^{40}+1}{2}$'dir. $5$ ve $11$ modlarında incelersek, Fermat teoreminden $$3^{40}+1\equiv 2\pmod{5}\implies S\equiv 1\pmod{5}$$ $$3^{40}+1\equiv 2\pmod{11}\implies S\equiv 1\pmod{11}$$ bulunur. Dolayısıyla $S\equiv 1\pmod{55}$'dir.

Not: Normalde bu tarz sorular, kendilerine denk olan başka bir şeye dönüştürülerek daha kolay çözülebilir. Örneğin bir dağılım sorusunu, bir polinomdaki bir terimin katsayısını bulmaya dönüştürebiliriz. Benim aklıma şu anda o şekilde bir dönüştürme gelmediği için uzun yoldan çözdüm.
Gerçek hikayeler aslında söylenmeyenlerdir.

Çevrimdışı Hüseyin Yiğit EMEKÇİ

  • Geo-Maniac
  • ********
  • İleti: 795
  • Karma: +2/-0
Ynt: 2024 Antalya Matematik Olimpiyatı 10. Sınıf Soru 20
« Yanıtla #2 : Ekim 16, 2024, 11:15:44 ös »
İndirgemeli diziler ile çözüm üretelim. $n$  harfli bir kelimede $a$  harfinin tek olduğu durumlar $x_n$  ve $a$  harfinin çift olduğu durumlar $y_n$  olsun. $x_n+y_n=3^n$  dir. Buna göre $n$  harfin

$i)$ Son harfi $a$  ise önceki $n-1$  harfte tek sayıda $a$  olur, durum sayısı $x_{n-1}$  dir.

$i)$ Son harfi $b$  veya $c$  ise önceki $n-1$  harfte çift sayıda $a$  olur, durum sayısı $2y_{n-1}$  dir.

Dolayısıyla $y_n=x_{n-1}+2y_{n-1}=3^{n-1}+y_{n-1}$  indirgeme bağıntısı elde edilir. Bu bağıntıda homojen olan taraftan $r_1=1$  ve tamamlayıcı çözüm fikriyle $r_2=3$  kökleri elde edilir. Ayrıca $y_1=2$  ve $y_2=5$  olduğundan

$$y_n=A\cdot 1^n+B\cdot 3^n$$
$$n=1\quad \text{için} \quad A+3B=2$$
$$n=2\quad \text{için} \quad A+9B=5$$

elde edilir. Buradan $A=B=1/2$  olur. Dolayısıyla

$$y_n=\dfrac{1}{2}\left(3^{n}+1\right)\qquad n=40\quad \text{için} \quad S=y_{40}=\dfrac{1}{2}\left(3^{40}+1\right)$$
olarak belirlenir. $\phi(55)=4.10=40$  olduğundan
$$\dfrac{3^{40}+1}{2}\equiv \dfrac{1+1}{2}=1 \pmod{55}$$ 
elde edilir.
« Son Düzenleme: Ekim 20, 2024, 05:12:39 ös Gönderen: Hüseyin Yiğit EMEKÇİ »
''Uzman, çok dar bir alanda yapılabilecek tüm hataları yapmış kişidir.''   ~Niels Bohr

 


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