2022 Antalya Matematik Olimpiyatı 2. Aşama Soru 11

[matematikolimpiyati]

$1,2$ ve $3$ rakamları kullanılarak yazılan ve $1$ rakamının çift sayıda bulunduğu $62$ basamaklı sayıların sayısı $S$ olsun. $2S-1$ sayısının $77$'ye bölümünden kalan kaçtır? (Uyarı : Sıfır da bir çift sayıdır.)

$\textbf{a)}\ 11  \qquad\textbf{b)}\ 76  \qquad\textbf{c)}\ 9  \qquad\textbf{d)}\ 12  \qquad\textbf{e)}\ 75$

[diktendik]

$1$ sayısı $0$ adet bulunursa $2^{62}$ adet sayı elde edilebilir. $2$ adet kullanılırsa $2^{60}\cdot{\binom{62}{2}}$ adet sayı elde edilir.bu şekilde sorunun bizden istediği şeyin $\sum_{i=0}^{31} \binom{62}{2n}\cdot2^{62-2n}$ olduğu görülür. Buda binom mantığından $\frac {(2+1)^{62}+(2-1)^{62}}2$ ye eşittir. Yani $S$=$\frac{(3^{62}+1)}2$ dir. $2S-1$=$3^{62}$ olduğu söylenebilir. Fermat teoreminden $3^6 \equiv 1 \pmod 7$ ve $3^{10} \equiv 1 \pmod {11}$ dir. Buradan $3^{62}$ nin $7$ ile bölümünden kalan $9$ ve $11$ ile bölümünden kalan $9$ dur. Dolayısıyla $77$ ile bölümünden kalanda $9$ olur.

[Hüseyin Yiğit EMEKÇİ]

İndirgemeli diziler ile çözüm üretelim. $n$  basamaklı bir sayıda $1$  rakamının tek olduğu durumlar $x_n$  ve $1$  rakamının çift olduğu durumlar $y_n$  olsun. $x_n+y_n=3^n$  dir. Buna göre $n$  basamağın

$i)$ Son basamağı $1$  ise önceki $n-1$  basamakta tek sayıda $1$  olur, durum sayısı $x_{n-1}$  dir.

$i)$ Son basamağı $2$  veya $3$  ise önceki $n-1$  basamakta çift sayıda $1$  olur, durum sayısı $y_{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=62\quad \text{için} \quad 2S-1=2y_{62}-1=3^{62}$$
olarak belirlenir. $\phi(77)=6.10=60$  olduğundan $3^{62}\equiv 3^2=9 \pmod{77}$  dir.