Geomania.Org Forumları
Yarışma Soruları => Antalya Matematik Olimpiyatı 1. Aşama => 2024 => Konuyu başlatan: matematikolimpiyati - 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$
-
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.
-
İ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.