Just an exam problem

11:12:00   soal-soal

Soal

Misalkan $$A={\underbrace{(999 \cdots 9)}_{\mbox{2008 buah}}}^{2009} \qquad \mbox{dan} \qquad B={\underbrace{(999 \cdots 9)}_{\mbox{2005 buah}}}^{2009}$$

Tunjukan bahwa digit dari

B dapat diperoleh dari A dengan cara menghapus beberapa buah digit

nya.

Solusi:

Untuk $0\leq m \leq 2009$ misalkan

$$A_m=\sum_{k=0}^{m} \binom{2009}{k} 10^{2008k} (-1)^{k+1} \qquad B_m= \sum_{k=0}^{m} \binom{2009}{k} 10^{2005k} (-1)^{k+1}$$

Jadi $A_{2009}=A$ dan $B_{2009}=B$.

Pertama-tama ditunjukan bahwa $2005$ buah digit terakhir dari $A$ dan $B$ sama. Karena $2005<2008$  maka $A \pmod {10^{2005}} = -1$ dan $B \pmod {10^{2005}} = -1$. Jadi $2005$ buah digit terakhir $A$ dan $B$ sama.

Berikutnya akan ditunjukan bahwa aturan pencoretan dari digit-digit $A$ untuk memperoleh digit-digit $B$ adalah dengan  sebagai berikut:

Mulai dari digit paling kanan, dimana telah dibuktikan $2005$ buah digit paling kanan $A$ sama dengan $B$. Kemudian hapus $3$ digit seterusnya (digit ke $2006$ sampai digit ke $2008$ dari kanan)

kemudian $2005$ digit berikutnya dari $A$ akan sama dengan digit ke $2006$ sampai $2(2005)$ digit $B$ dari kanan, dan seterusnya.

$$A=\underbrace{c_1 c_2 c_3}_{\mbox{dicoret}} d_1 d_2 \cdots d_{2005}\underbrace{e_1 e_2 e_3}_{\mbox{dicoret}}\cdots\cdots\underbrace{f_1 f_2 f_3}_{\mbox{dicoret}} g_1 g_2 \cdots g_{2005}$$

$$B= b_1 b_2 \cdots b_{2005} \cdots \cdots d_1 d_2 \cdots d_{2005} \cdots \cdots g_1 g_2 \cdots g_{2005}$$

Untuk membuktikan hal ini, pertama-tama kita buktikan beberapa lemma berikut:

Lemma 1

 Untuk $0\leq m \leq 2009$ berlaku 

$$|A_m|<10^{2008m+1005} \qquad \text{dan} \qquad |B_m|<10^{2005m+1005}$$

bukti:

 Berdasarkan sifat koefisien binomial $\binom{2009}{k} < \binom{2009}{1004} = \frac{(2009)(2008)\cdots (1006)}{(1004)(1003)\cdots (1)}<10^{1004}$. Dengan ketaksamaan segitiga

$$\begin{align*}\left|\sum_{k=0}^{m} \binom{2009}{k} (-1)^{k+1} 10^{2008k}\right| &\leq \sum_{k=0}^m \left|\binom{2009}{k} 10^{2008k}\right|\\ &<\binom{2009}{1004} \sum_{k=0}^{m} 10^{2008k}\\ &= \binom{2009}{1004} \left(\frac{10^{2008m+2008}}{10^{2008}-1}\right)\\ &< 10^{1004} \left(\frac{10^{2008m+2008}-1}{10^{2008}-1}\right) \\ &< 10^{1004} \left(\frac{10^{2008m+2008}}{ 10^{2007}}\right)\\ &< 10^{2008m+1005}\end{align*}$$

Ketaksamaan yang kedua dapat dibuktikan secara similar.

Lemma 2

 Jika $m$ ganjil maka $A_m >0$ dan $B_m>0$, sebaliknya jika $m$ genap maka $A_m<0$ dan $B_m<0$.

Bukti:

Berdasarkan Lemma 1,
$$-10^{2008m}< A_{m-1} <10^{2008m}.$$

Untuk $m$ ganjil berlaku $10^{2008m}<\binom{2009}{m} (-1)^{m+1} 10^{2008m}$. Sehingga diperoleh

$$0<-10^{2008m}+\binom{2009}{m} (-1)^{m+1} 10^{2008m}< A_m \Longrightarrow A_m>0.$$

Untuk $m$ genap berlaku $10^{2008m}<\binom{2009}{m} (-1)^{m} 10^{2008m}$, kalikan ketaksamaan ini dengan $-1$ diperoleh \\ $\binom{2009}{n} (-1)^{n+1} 10^{2008n}<-10^{2008n}$. Sehingga diperoleh

$$A_m < \binom{2009}{m} (-1)^{m+1} 10^{2008m}+10^{2008m} < 0 \Longrightarrow A_m<0.$$

Pembuktian untuk $B_m$ dapat dilakukan dengan similar.

Sekarang akan dibuktikan pernyataan yang diklaim diawal. Misalkan $n$ adalah bilangan bulat yang terletak pada interval $(0,2009)$.

perhatikan bahwa hasil dari $A \mod {10^{2008n+2005}}$ menyatakan $2008n+2005$ digit terakhir dari $A$ (dengan menambahkan beberapa buah 0 dikiri apabila diperlukan). Karena $10^p \mod 10^q=0$ untuk $p \geq q$ maka

$$\begin{align*}A \mod 10^{2008n+2005} &=\left[\sum_{k=0}^{2009} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\right] \mod 10^{2008n+2005}\\ &=A_n +a10^{2008n+2005}\end{align*}$$

Berdasarkan Lemma 1 , $|A_n|<10^{2008n+1005}<10^{2008n+2005}$,  jadi hasil modulo diatas tidak lebih dari $10^{2008n+2005}$ sehingga apabila $A_n$ positif maka nilai $A_n$ samadengan $2008n+2005$ digit terakhir dari $A$, dan apabila $A_n$ negatif maka $2008n+2005$ digit terakhir dari $A$ adalah $10^{2008n+2005}+A_n$. Dengan kata lain, menggunakan Lemma 2 diperoleh

$$a=\begin{cases}1\quad & \mbox{$n$ genap}\\ 0 \quad & \mbox{$n$ ganjil}\end{cases}$$

Kemudian $2008n$ digit terakhir dari $A$ adalah

$$\begin{align*}A \mod {10^{2008n}}&=\left[\sum_{k=0}^{2009} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\right] \mod 10^{2008n}\\ &\equiv\sum_{k=0}^{n-1} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\\ &=A_{n-1}+b10^{2008n}\end{align*}$$

Berdasarkan Lemma 1 , $|A_{n-1}|<10^{2008(n-1)+1005}<10^{2008n}$,  jadi hasil modulo diatas tidak lebih dari $10^{2008n}$ sehingga apabila $A_{n-1}$ positif maka nilai $A_{n-1}$ samadengan $2008n$ digit terakhir dari $A$, dan apabila $A_{n-1}$ negatif maka $2008n$ digit terakhir dari $A$ adalah $10^{2008n}+A_{n-1}$.  Dengan kata lain, menggunakan Lemma 2 diperoleh

$$b=\begin{cases}1 \quad & \mbox{$n-1$ genap}\\ 0 \quad & \mbox{$n-1$ ganjil}\end{cases}$$

Hal ini berarti $a \neq b$, atau $|a-b|=1$.

Dengan penalaran yang sama

$$\begin{align*}B \mod {10^{2005n}} &=\left[\sum_{k=0}^{2009} \binom{2009}{k}10^{2008k}(-1)^{k+1}\right]\mod 10^{2005n}\\ &\equiv\sum_{k=0}^{n-1} \binom{2009}{k} 10^{2005k} (-1)^{k+1} \\ &=B_{n-1}+c10^{2005n}\end{align*}$$

dimana $c=b$.

$$\begin{align*}B\mod{10^{2005(n+1)}}&=\left[\sum_{k=0}^{2009} \binom{2009}{k} 10^{2008k} (-1)^{k+1}\right] \mod 10^{2005(n+1)}\\ &\equiv\sum_{k=0}^{n} \binom{2009}{k} 10^{2005k} (-1)^{k+1}\\ &=B_{n}+d10^{2005(n+1)}\end{align*}$$

dimana $d=a$.

Akan dibuktikan

  $$\begin{align}\left(\frac{A \mod {10^{2008n+2005}} - A \mod {10^{2008n}}}{10^{3n}}\right)+ B \mod {10^{2005n}} = \\ B \mod {10^{2005(n+1)}}\end{align}$$

yang berarti bagian digit $2008n+1$ sampai $2008n+2005$ dari $A$  samadengan bagian digit ke $2005n+1$ sampai $2005(n+1)$ dari $B$. Persamaan (1) setara dengan

$$\begin{aligned}\frac{A_n +a10^{2008n+2005}-A_{n-1}-b10^{2008n}}{10^{3n}} +B_{n-1}+c10^{2005n} =B_{n}+d10^{2005(n+1)}\end{aligned}$$

Dari persamaan-persamaan yang diperoleh sebelumnya diperoleh

$$\begin{align*}A_n +a10^{2008n+2005}-A_{n-1}-b10^{2008n} =\\ \binom{2009}{n}10^{2008n} (-1)^n + a10^{2008n+2005} -b10^{2008n} \end{align*}$$

Jadi

$$\begin{align*}\frac{A_n +a10^{2008n+2005}-A_{n-1}-b10^{2008n}}{10^{3n}} +B_{n-1}+c10^{2005n} = \\ B_n + a10^{2005(n+1)} -b10^{2005n}+ c10^{2005n} \end{align*}$$

Karena  $c=b$ dan $a=d$ diperoleh

$$B_n + a10^{2005(n+1)} -b10^{2005n}+ c10^{2005n} =B_n + a10^{2005(n+1)} = B_n + d10^{2005(n+1)}$$

seperti yang diharapkan.

ShareShare on Facebook

TweetShare on Twitter

Pin ItShare on Pinterest