tuturwidodo..com

tuturwidodo..com

19 December 2013

Soal Teori Bilangan Dari Semifinal UNNES 2013

Ditulis Oleh pada 19 December 2013


Pada postingan sebelumnya, saya pernah membahas soal-soal dari UNNES berkaitan dengan barisan dan deret. Setali tiga uang, untuk kali ini saya akan memposting soal-soal teori bilangan dari semifinal UNNES 2013.

Ada tiga soal yang saya tampilkan. Satu soal dari tingkat SMP dan dua soal dari tingkat SMA. Ketiga soal tersebut saya selesaikan dengan menggunakan modular aritmatik. Entah kenapa solusinya agak repot dan panjang. Padahal ini soal isian singkat, ckckck. Apa mungkin saya yang terlalu ribet kali ya? Silakan simak dan beri masukan.

Soal pertama dari tingkat SMP,

Diketahui $\overline{4ab3}+\overline{3b95}=N$. Jika $N$ habis dibagi $99$ maka nilai $a+b$ adalah ...

Penyelesaian :

Dalam penyajian bilangan basis sepuluh diperoleh, $$\begin{align*} N&=\overline{4ab3}+\overline{3b95}\\ &=4000+100a+10b+3+3000+100b+90+5\\ &=7000+110b+100a+98 \end{align*}$$ Karena $N$ habis dibagi $99$ maka $N$ habis dibagi $9$ dan $11$. Akibatnya $$\begin{align*} N&\equiv0\text{ mod }11\\ 7000+110b+100a+98&\equiv0\text{ mod }11\\ 4+a+10&\equiv0\text{ mod }11\\ 3+a&\equiv0\text{ mod }11 \end{align*}$$ Mengingat $0\leq a\leq 9$ maka haruslah $a=8$.

Karena $N$ juga habis dibagi $9$ diperoleh $$\begin{align*} N&\equiv0\text{ mod }9\\ 7000+110b+100a+98&\equiv0\text{ mod }9\\ 7+2b+a+8&\equiv0\text{ mod }9\\ 2b+23&\equiv0\text{ mod }9\\ 2b+5&\equiv0\text{ mod }9 \end{align*}$$ sehingga $b=2$.

Oleh karena itu, $a+b=10$.

Berikutnya soal kedua dari tingkat SMA. Nie soal bikin males, huft

Bilangan enam angka $n$ yang memenuhi
  1. $n$ adalah bilangan kuadrat sempurna.
  2. bilangan dibentuk dengan tiga angka terakhir $n$ lebih satu dari tiga angka pertama $n$. (Sebagai contoh $n$ terlihat seperti $123124$ tetapi ini bukan bilangan kuadrat)
Bilangan $n$ yang memenuhi yaitu ...

Penyelesaian :

Misalkan $a$ adalah bilangan asli tiga digit maka dapat ditulis $n=1000a+a+1=1001a+1$. Misalkan pula $x$ adalah bilangan asli yang memenuhi $$\begin{equation*} n=x^2\Rightarrow 1001a=x^2-1=(x+1)(x-1) \end{equation*}$$ Karena $1001=7\cdot11\cdot13$, ada enam kasus yang mungkin

  1. $$\begin{align*} x&\equiv1\text{ mod }7\\ x&\equiv1\text{ mod }11\\ x&\equiv-1\text{ mod }13 \end{align*}$$ Untuk kasus ini diperoleh $x=1001m+155$. Tidak ada yang memenuhi.
  2. $$\begin{align*} x&\equiv1\text{ mod }7\\ x&\equiv-1\text{ mod }11\\ x&\equiv1\text{ mod }13 \end{align*}$$ Untuk kasus ini diperoleh $x=1001m+274$. Tidak ada yang memenuhi.
  3. $$\begin{align*} x&\equiv-1\text{ mod }7\\ x&\equiv1\text{ mod }11\\ x&\equiv1\text{ mod }13 \end{align*}$$ Untuk kasus ini diperoleh $x=1001m-428$. Nilai $x$ yang memenuhi yaitu $x=573$ dan nilai $n$ yang bersesuaian yaitu $n=328329$.
  4. $$\begin{align*} x&\equiv-1\text{ mod }7\\ x&\equiv-1\text{ mod }11\\ x&\equiv1\text{ mod }13 \end{align*}$$ Untuk kasus ini diperoleh $x=1001m-155$. Nilai $x$ yang memenuhi yaitu $x=846$ dan nilai $n$ yang bersesuaian yaitu $n=715716$.
  5. $$\begin{align*} x&\equiv-1\text{ mod }7\\ x&\equiv1\text{ mod }11\\ x&\equiv-1\text{ mod }13 \end{align*}$$ Untuk kasus ini diperoleh $x=1001m-274$. Nilai $x$ yang memenuhi yaitu $x=727$ dan nilai $n$ yang bersesuaian yaitu $n=528529$.
  6. $$\begin{align*} x&\equiv1\text{ mod }7\\ x&\equiv-1\text{ mod }11\\ x&\equiv-1\text{ mod }13 \end{align*}$$ Untuk kasus ini diperoleh $x=1001m+428$. Nilai $x$ yang memenuhi yaitu $x=428$ dan nilai $n$ yang bersesuaian yaitu $n=183184$.
Jadi, ada $4$ nilai $n$ yang memenuhi yaitu $183184, 328329, 528529, 715716$.

Terakhir soal ketiga. Saya memakai teorema Euler dan CRT dalam perhitungannya. Berharap ada yang lebih elementer sih.

Sisa pembagian dari $1776^{2013!+2012!+\cdots+2!+1!}$ oleh $2000$ adalah ...

Penyelesaian :

Misalkan $N=1776^{2013!+2012!+\cdots+2!+1!}$. Untuk menghitung nilai $N\equiv \text{ mod }2000$ secara langsung agak repot. Oleh karena itu kita pecah menjadi $\text{ mod }16$ dan $\text{ mod }125$.

Perhatikan bahwa $N\equiv0\text{ mod }16$. Dan $$\begin{align*} N&\equiv 1776^{2013!+2012!+\cdots+2!+1!}\text{ mod }125\\ &\equiv 26^{2013!+2012!+\cdots+2!+1!}\text{ mod }125\\ &\equiv 26^{2013!+2012!+\cdots+2!+1!}\text{ mod }125 \end{align*}$$ Dari teorema Euler diperoleh $26^{100}\equiv1\text{ mod }125$. Sehingga bentuk di atas dapat disederhanakan menjadi $$\begin{align*} N&\equiv 26^{9!+8!+\cdots+2!+1!}\text{ mod }125\\ &\equiv 26^{13}\text{ mod }125\\ &\equiv 76\text{ mod }125 \end{align*}$$

Karena $N\equiv 76\text{ mod }125$ dan $N\equiv 0\text{ mod }16$ berakibat $$\begin{align*} N&\equiv 76\cdot 16\cdot(-39)\text{ mod }2000\\ &\equiv 576\text{ mod }2000 \end{align*}$$ Jadi, Sisa pembagian dari $1776^{2013!+2012!+\cdots+2!+1!}$ oleh $2000$ adalah $576$.

Nah, selesai sudah ketiga soal berikut pembahasannya. Saya sendiri menilai solusi saya di atas agak ngoyo. Males bawaannya klo lihat solusi kayak gitu. Nah, jika ada yang punya solusi lebih cantik jangan sungkan-sungkan berbagi lewat kolom komentar. See you soon!





0 comments :

Post a Comment