Geomania.Org Forumları
Yarışma Soruları => Antalya Matematik Olimpiyatı 2. Aşama => 2022 => Konuyu başlatan: matematikolimpiyati - Mayıs 12, 2024, 02:33:40 öö
-
$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$
-
$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.
-
İ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.