Catatan si Jay

November 12, 2010

3 Pangkat 2 Pangkat n

Filed under: Barisan Bilangan, Matematika — Hendra Jaya @ 12:58 pm

Problem

Hitunglah nilai dari

\frac{1}{3+1}+\frac{2}{3^2+1}+\frac{4}{3^4+1}+\ldots+\frac{2^{2009}}{3^{2^{2009}}+1}+\frac{2^{2010}}{3^{2^{2010}}+1}

Sumber

Post dari silvergrashopper di www.olimpiade.org. Soal aslinya telah sedikit dimodifikasi

Pra-Pembahasan

Sekedar menyegarkan ingatan, perhatikan beberapa sifat berikut :

  • {(x^a)}^b=x^{ab} untuk sembarang a,b,x\in\mathbb{R}
  • x^a.x^b=x^{a+b} untuk sembarang a,b,x\in\mathbb{R}
  • (x-y).(x+y)=x^2-y^2 untuk sembarang x,y\in\mathbb{R}

Misalkan kita ambil

x=3

a=2^n

b=2^1=2

Maka kita peroleh {(3^{2^n})}^2=3^{2^n.2}

Sekarang, karena 2^n.2=2^n.2^1=2^{n+1}

Maka nilai dari {(3^{2^n})}^2 dapat dituliskan sebagai :

{(3^{2^n})}^2=3^{2^n.2}=3^{2^{n+1}}

Pembahasan

Salah satu trik yang sangat ampuh dalam problem jenis ini adalah mengubah f(n) menjadi bentuk g(n)-g(n+1).

Pada problem ini, secara eksplisit dalam soal, diberitahu bahwa f(n)=\frac{2^n}{3^{2^n}+1}

Agar, tidak terlalu “ribet”, kita mulai manipulasi f(n) dari \frac{1}{3^{2^n}+1}

Melalui aljabar kita peroleh :

\begin{array}{rcll}\frac{1}{3^{2^n}-1}-\frac{1}{3^{2^n}+1}&=&\frac{(3^{2^n}+1)-(3^{2^n}-1)}{{(3^{2^n})}^2-1^2}\\\\&=&\frac{3^{2^n}+1-3^{2^n}+1}{3^{2^{n+1}}-1}\\\\&=&\frac{2}{3^{2^{n+1}}-1}\end{array}

Dengan demikian :

\begin{array}{ccccll}\frac{1}{3^{2^n}-1}&-&\frac{1}{3^{2^n}+1}&=&\frac{2}{3^{2^{n+1}}-1}\\\\\frac{1}{3^{2^n}-1}&-&\frac{2}{3^{2^{n+1}}-1}&=&\frac{1}{3^{2^n}+1}\\\\\frac{2^n}{3^{2^n}-1}&-&\frac{2^n.2}{3^{2^{n+1}}-1}&=&\frac{2^n}{3^{2^n}+1}&\mbox{Kalikan kedua sisi dengan }2^n\\\\\frac{2^n}{3^{2^n}-1}&-&\frac{2^{n+1}}{3^{2^{n+1}}-1}&=&\frac{2^n}{3^{2^n}+1}\end{array}

Bentuk di atas sungguh merupakan bentuk yang sangat sempurna untuk di-eksploitasi 😉

Yaitu f(n)=\frac{2^n}{3^{2^n}+1} dapat ditulis ulang sebagai g(n)-g(n+1) dimana g(n)=\frac{2^n}{3^{2^n}-1}

Sekarang waktunya menjawab soal :

\begin{array}{lcl}N&=&\frac{1}{3+1}+\frac{2}{3^2+1}+\frac{4}{3^4+1}+\ldots+\frac{2^{2009}}{3^{2^{2009}}+1}+\frac{2^{2010}}{3^{2^{2010}}+1}\\\\&=&(\frac{2^0}{3^{2^0}-1}-\frac{2^1}{3^{2^1}-1})+(\frac{2^1}{3^{2^1}-1}-\frac{2^2}{3^{2^2}-1})+(\frac{2^2}{3^{2^2}-1}-\frac{2^3}{3^{2^3}-1})+\ldots+(\frac{2^{2009}}{3^{2^{2009}}-1}-\frac{2^{2010}}{3^{2^{2010}}-1})+(\frac{2^{2010}}{3^{2^{2010}}-1}-\frac{2^{2011}}{3^{2^{2011}}-1})\\\\&=&\frac{2^0}{3^{2^0}-1}+(\frac{2^1}{3^{2^1}-1}-\frac{2^1}{3^{2^1}-1})+(\frac{2^2}{3^{2^2}-1}-\frac{2^2}{3^{2^2}-1})+(\frac{2^3}{3^{2^3}-1}-\frac{2^3}{3^{2^3}-1})+\ldots+(\frac{2^{2010}}{3^{2^{2010}}-1}-\frac{2^{2010}}{3^{2^{2010}}-1})-\frac{2^{2011}}{3^{2^{2011}}-1}\\\\&=&\frac{2^0}{3^{2^0}-1}-\frac{2^{2011}}{3^{2^{2011}}-1}\\\\&=&\frac{1}{2}-\frac{2^{2011}}{3^{2^{2011}}-1}\end{array}

Introduction to Computer

November 11, 2010

Kejutan!!

Filed under: Barisan Bilangan, Matematika, Puzzle — Hendra Jaya @ 11:52 am

Problem

Hitunglah nilai dari

\begin{array}{l}\sqrt{1+\frac{1}{1^2}+\frac{1}{2^2}}+\sqrt{1+\frac{1}{2^2}+\frac{1}{3^2}}+\sqrt{1+\frac{1}{3^2}+\frac{1}{4^2}}+\ldots+\sqrt{1+\frac{1}{2008^2}+\frac{1}{2009^2}}+\sqrt{1+\frac{1}{2009^2}+\frac{1}{2010^2}}\end{array}

Sumber

Post dari aldo di www.olimpiade.org. Soal aslinya telah sedikit di-modifikasi

Pembahasan

Penulis akui bahwa penulis sedikit bingung apakah hasil perhitungan berupa bilangan rasional atau irasional. Tetapi, secara psikologis penulis yakin bahwa hasil akhirnya pasti berupa bilangan rasional.

Berangkat dari sini, manipulasi aljabar akan sangat dibutuhkan. Masalahnya adalah “Manipulasi yang seperti apa?”

Beberapa cara akan kita coba. Identitas aljabar yang perlu diingat pertama kali adalah (x+y+z)^2=x^2+y^2+z^2+2xy+2xz+2yz

Dengan identitas ini diharapkan terjadi ‘keajaiban’ bahwa manipulasi aljabar akan dapat menyingkirkan tanda akar (\sqrt{}) yang sangat mengganggu.

Dari sini, kita coba aljabar pertama, yaitu :

\begin{array}{lll}(1+\frac{1}{a}+\frac{1}{b})^2&=&1+\frac{1}{a^2}+\frac{1}{b^2}+\frac{2}{a}+\frac{2}{b}+\frac{2}{ab}\\\\&=&1+\frac{1}{a^2}+\frac{1}{b^2}+\frac{2(a+b+1)}{ab}\end{array}

Cukup mirip dengan yang kita inginkan, tetapi belum sesuai. Mari kita coba aljabar kedua :

\begin{array}{lll}(1+\frac{1}{a}-\frac{1}{b})^2&=&1+\frac{1}{a^2}+\frac{1}{b^2}+\frac{2}{a}-\frac{2}{b}-\frac{2}{ab}\\\\&=&1+\frac{1}{a^2}+\frac{1}{b^2}+\frac{2(b-a-1)}{ab}\end{array}

Sepertinya aljabar yang terakhir memang aljabar yang kita inginkan. Agar bentuk yang terakhir sama persis dengan apa yang kita inginkan, kita ambil :

b=a+1 sehingga :

\begin{array}{lll}(1+\frac{1}{a}-\frac{1}{(a+1)})^2&=&1+\frac{1}{a^2}+\frac{1}{(a+1)^2}+\frac{2}{a}-\frac{2}{(a+1)}-\frac{2}{a(a+1)}\\\\&=&1+\frac{1}{a^2}+\frac{1}{(a+1)^2}+\frac{2(a+1-a-1)}{a(a+1)}\\\\&=&1+\frac{1}{a^2}+\frac{1}{(a+1)^2}+\frac{2.0}{a(a+1)}\\\\&=&1+\frac{1}{a^2}+\frac{1}{(a+1)^2}\end{array}

Voila! Persis dengan yang kita inginkan. Suatu bentuk ‘ajaib’ yang bisa meng-eliminasi tanda akar (\sqrt{})dengan mudah 😉

Dari sini kita peroleh :

\begin{array}{rll}1+\frac{1}{a^2}+\frac{1}{(a+1)^2}&=&(1+\frac{1}{a}-\frac{1}{(a+1)})^2\\\\\sqrt{1+\frac{1}{a^2}+\frac{1}{(a+1)^2}}&=&1+\frac{1}{a}-\frac{1}{(a+1)}\end{array}

Dengan memanfaatkan sepenuh-penuhnya bentuk terakhir, kita dapat menjawab soal dengan mudah :

latex

Exit Interview

November 9, 2010

Menghitung Kemunculan Karakter ‘1’ Pada Bilangan n-Digit

Filed under: Matematika, Peluang, Puzzle — Hendra Jaya @ 1:12 pm

Problem

  • Kemunculan karakter ‘1’ pada angka 10 adalah 1
  • Kemunculan karakter ‘1’ pada angka 51 adalah 1
  • Kemunculan karakter ‘1’ pada angka 11 adalah 2
  • Kemunculan karakter ‘1’ pada angka 121 adalah 2
  • Kemunculan karakter ‘1’ pada angka 1141 adalah 3
  • dst…

Pertanyaannya :

  • Diketahui A=\{1,2,3,\ldots,999,1000\}.
    • Berapa banyak bilangan di dalam himpunan tersebut yang mengandung karakter ‘1’?
    • Berapa kali karakter ‘1’ muncul di dalam himpunan A?
  • Misalkan N=\{n_1,n_2,n_3,\ldots,n_k\} adalah himpunan seluruh bilangan n-digit.
    • Berapa banyak bilangan di dalam himpunan N yang mengandung karakter 1?
    • Berapa kali karakter ‘1’ muncul pada himpunan tersebut?

Sumber : Nanda Daiva Putra

Referensi : 10th Binomial Transform dan Number of “9ish numbers” with n digits

Dear Diary

Pra-Pembahasan 1 (Leading Zero)

Normalnya, awalan 0 (leading zero) tidak diperbolehkan dalam menulis angka. Sebagai contoh :

  • Penulisan 06 dianggap tidak valid, yang valid adalah 6
  • Penulisan 029 dianggap tidak valid, yang valid adalah 29

Sehingga :

Banyaknya bilangan 1 digit yang dapat dibentuk adalah 9
Banyaknya bilangan 2 digit yang dapat dibentuk adalah 9 . 10 = 90
Banyaknya bilangan 3 digit yang dapat dibentuk adalah 9 . 10 . 10 = 900
dst..

Namun, seandainya leading zero diperbolehkan, yaitu setiap karakter pada himpunan C=\{0,1,2,3,4,5,6,7,8,9\} boleh dipakai, maka :

Banyaknya bilangan 1 digit yang dapat dibentuk adalah 10
Banyaknya bilangan 2 digit yang dapat dibentuk adalah 10 . 10 = 100
Banyaknya bilangan 3 digit yang dapat dibentuk adalah 10 . 10 . 10 = 1000
dst…

Dari sini kita dapat menyimpulkan bahwa :

  1. Banyaknya bilangan n-digit yang dapat dibentuk jika awalan 0 tidak diperbolehkan (non-leading zero) adalah 9.10^{n-1}
  2. Banyaknya bilangan n-digit yang dapat dibentuk jika awalan 0 (leading zero) diperbolehkan adalah 10^{n}

Pra-Pembahasan 2 (Kemunculan Karakter ‘1’ pada Leading Zero)

Jika awalan 0 (non-leading zero) tidak diperbolehkan, maka :

Bilangan-bilangan 1 digit yang mengandung karakter ‘1’ adalah \{1\}
Banyaknya bilangan 1 digit yang mengandung karakter ‘1’ adalah 1 buah.
Total kemunculan karakter ‘1’ pada bilangan 1 digit adalah 1 kali.

Bilangan-bilangan 2 digit yang mengandung karakter ‘1’ adalah \{10,11,12,13,14,15,16,17,18,19,21,31,41,51,61,71,81,91\}
Banyaknya bilangan 2 digit yang mengandung karakter ‘1’ adalah 18 buah.
Total kemunculan karakter ‘1’ pada bilangan 2 digit adalah 19 kali.

Jika awalan 0 (leading zero) diperbolehkan, maka :

Bilangan-bilangan 1 digit yang mengandung karakter ‘1’ adalah \{1\}
Banyaknya bilangan 1 digit yang mengandung karakter ‘1’ adalah 1 buah.
Total kemunculan karakter ‘1’ pada bilangan 1 digit adalah 1 kali.

Bilangan-bilangan 2 digit yang mengandung karakter ‘1’ adalah \{01,10,11,12,13,14,15,16,17,18,19,21,31,41,51,61,71,81,91\}
Banyaknya bilangan 2 digit yang mengandung karakter ‘1’ adalah 19 buah.
Total kemunculan karakter ‘1’ pada bilangan 2 digit adalah 20 kali.

Mengapa terdapat perbedaan antara kasus leading zero dan kasus non-leading zero?

Jawabannya terletak pada leading zero itu sendiri.

Pada kasus non-leading zero, bilangan 1 tidak akan muncul pada bilangan 2-digit karena bilangan 1 hanya terdiri dari 1 buah digit. Selamanya begitu. Tidak bisa “naik pangkat” menjadi bilangan 2-digit.

Sebaliknya, pada kasus leading zero, bilangan 1 akan muncul pada bilangan 2-digit. Yaitu dengan memberikan awalan 0 (leading zero) pada bilangan 1, maka akan dihasilkan bilangan baru 01 yang panjangnya 2 digit. Kita katakan “1 naik pangkat menjadi bilangan 2-digit”.

Dari logika ini, semua bilangan 1-digit akan naik pangkat menjadi bilangan 2-digit, lalu naik pangkat menjadi bilangan 3-digit, dan seterusnya sampai menjadi bilangan n-digit.
Dari logika yang sama, semua bilangan 2-digit akan naik pangkat menjadi bilangan 3-digit, lalu naik pangkat menjadi bilangan 4-digit, dan seterusnya sampai menjadi bilangan n-digit.
dst..
Begitu pula dengan bilangan (n-1)-digit. Bilangan ini akan naik pangkat menjadi bilangan n-digit.

Lantas, apa hubungan antara bilangan non-leading zero dan leading zero?

Misalkan :

  • f(n) adalah fungsi yang menghitung banyaknya kemunculan ‘1’ pada seluruh bilangan n-digit non-leading zero.
  • g(n) adalah fungsi yang menghitung banyaknya kemunculan ‘1’ pada seluruh bilangan n-digit leading zero.

Secara intuitif kita tahu bahwa g(n) pasti lebih besar dari f(n). Hal ini cukup jelas juga secara matematis, mengingat bilangan-bilangan yang leading zero boleh menggunakan 0, sementara bilangan-bilangan yang non-leading zero tidak.

Cukup jelas juga bahwa selisih antara g(n) dan f(n) berasal dari bilangan-bilangan yang “naik pangkat”.

Lantas, berapa banyak bilangan-bilangan yang “naik pangkat”?

Semua bilangan-bilangan berdigit lebih kecil dari n akan naik pangkat. Mulai dari berdigit 1 sampai berdigit n-1.

Banyaknya bilangan berdigit 1 yang naik pangkat adalah f(1)
Banyaknya bilangan berdigit 2 yang naik pangkat adalah f(2)
Banyaknya bilangan berdigit 3 yang naik pangkat adalah f(3)
dst…
Banyaknya bilangan berdigit n-1 yang naik pangkat adalah f(n-1)

Sehingga, total bilangan yang naik pangkat adalah f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)

Jika dikembalikan ke relasi antara g(n) dan f(n), maka akan kita peroleh :

\begin{array}{rcl}g(n)-f(n)&=&f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)\\g(n)&=&f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)+f(n)\end{array}

Pra-Pembahasan 3 (Sebaran Bilangan yang Mengandung karakter ‘1’ Pada Bilangan n-digit Leading Zero)

Misalkan pada seluruh bilangan n-digit leading zero, terdapat :

  • x buah bilangan yang mengandung karakter ‘1’
  • y buah bilangan yang tidak mengandung karakter ‘1’
  • g(n)=z buah kemunculan karakter ‘1’.

Jelas sekali bahwa relasi antara x dan y adalah x+y=10^n

Selanjutnya, kita asumsikan :

  • Ada a_1 buah bilangan yang mengandung 1 buah karakter ‘1’
  • Ada a_2 buah bilangan yang mengandung 2 buah karakter ‘1’
  • Ada a_3 buah bilangan yang mengandung 3 buah karakter ‘1’
  • dst…
  • Ada a_{n-1} buah bilangan yang mengandung n-1 buah karakter ‘1’
  • Ada a_n buah bilangan yang mengandung n buah karakter ‘1’

Banyaknya bilangan yang mengandung karakter ‘1’ adalah a_1+a_2+a_3+\ldots+a_{n-1}+a_n alias x.
Sehingga kita peroleh invarian x=a_1+a_2+a_3+\ldots+a_{n-1}+a_n

Sebaliknya, banyaknya kemunculan karakter ‘1’ adalah 1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n alias z.
Sehingga kita peroleh invarian lainnya, yakni g(n)=z=1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n

Bagaimana dengan y, adakah cara untuk menghitungnya?

Untuk mencari nilai y tidak terlalu sulit. Cukup menggunakan “pohon kemungkinan”.

Karena terdiri dari n-digit dan leading zero, maka setiap digit-nya boleh menggunakan bilangan-bilangan pada himpunan \{0,2,3,4,5,6,7,8,9\} yang banyaknya (kardinalitas) ada 9 buah. Sehingga :

y=9.9.9\ldots 9.9=9^n

Knuth Mistakes

Pembahasan

Misalkan \overline{ABCDE\ldots} adalah sebuah bilangan n digit.

Bilangan ini dapat kita pecah menjadi 2 bagian yaitu \overline{A} dan \overline{BCDE\ldots} dimana :

  • \overline{A} jelas merupakan bilangan 1 digit dan tidak boleh dimulai dengan 0 (non-leading zero).
    Sehingga himpunan bilangan yang mungkin untuk \overline{A} adalah \{1,2,3,4,5,6,7,8,9\}.
  • Sedikit berbeda, \overline{BCDE\ldots} merupakan bilangan (n-1)-digit yang boleh dimulai dari 0.
    Sehingga himpunan bilangan yang mungkin untuk \overline{B},\overline{C},\overline{D},\overline{E},\ldots adalah \{0,1,2,3,4,5,6,7,8,9\}.

Secara intuitif, kita dapat menyadari bahwa munculnya karakter ‘1’ hanya mungkin terjadi dalam 3 buah kasus, yaitu :

  1. Karakter ‘1’ hanya disumbangkan oleh \overline{A}
  2. Karakter ‘1’ hanya disumbangkan oleh \overline{BCDE\ldots}
  3. Karakter ‘1’ disumbangkan oleh kedua pihak, yaitu \overline{A} dan \overline{BCDE\ldots}

Kasus 1

Karena karakter ‘1’ hanya disumbangkan oleh \overline{A}, berarti :

  • Hanya ada 1 buah nilai yang mungkin untuk \overline{A}
  • Ada y buah nilai yang mungkin untuk \overline{BCDE\ldots}

Sehingga :

  • Banyaknya bilangan yang mengandung ‘1’ pada kasus 1 adalah 1.y=y
  • Banyaknya kemunculan karakter ‘1’ ada sebanyak y kali

Catatan : Walaupun \overline{BCDE\ldots} tidak memiliki satupun karakter ‘1’, namun \overline{BCDE\ldots} berjumlah y buah. Ketika dipasangkan dengan \overline{A} maka akan muncul y buah karakter ‘1’ yang baru.

Kasus 2

Dalam kasus ini, karakter ‘1’ hanya disumbangkan oleh \overline{BCDE\ldots}, yang berarti :

  • Ada 8 buah nilai yang mungkin untuk \overline{A}, yaitu \{2,3,4,5,6,7,8,9\}
  • Ada x buah nilai yang mungkin untuk \overline{BCDE\ldots}
  • Ada z buah kemunculan karakter ‘1’ pada \overline{BCDE\ldots}

Sehingga :

  • Banyaknya bilangan yang mengandung ‘1’ pada kasus 2 adalah 8.x=8x
  • Banyaknya kemunculan karakter ‘1’ ada sebanyak 8.z=8z kali

Kasus 3

Kasus ini adalah kasus yang paling tricky. Perhatikan bahwa :

  • Ada 1 buah nilai yang mungkin untuk \overline{A}
  • Ada x buah nilai yang mungkin untuk \overline{BCDE\ldots}
  • Ada z buah kemunculan karakter ‘1’ pada \overline{BCDE\ldots}

Sebaran dari z adalah 1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n
Ketika digabungkan dengan \overline{A}, sebarannya akan naik menjadi 2.a_1+3.a_2+4.a_3+\ldots+n.a_{n-1}+(n+1).a_n.

Catatan : Kenaikan sebaran terjadi karena terjadi penggabungan (concatenation) dengan karakter ‘1’ yang berasal dari \overline{A}.  Sebagai contoh, bilangan 31216 semula memiliki 2 buah karakter ‘1’. Ketika dibubuhi prefix ‘1’ akan menjadi 131216 yang mengandung 3 buah karakter ‘1’.

Jika disederhanakan, bentuk di atas akan menjadi :

\begin{array}{rcl}2.a_1+3.a_2+4.a_3+\ldots+n.a_{n-1}+(n+1).a_n&=&(1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n)+(a_1+a_2+a_3+\ldots+a_{n-1}+a_n)\\&=&z+x\end{array}

Sehingga :

  • Banyaknya bilangan yang mengandung ‘1’ pada kasus 3 adalah 1.x=x
  • Banyaknya kemunculan karakter ‘1’ ada sebanyak x+z kali

Rumus Umum Untuk Menghitung Banyaknya Bilangan n-digit yang Mengandung Karakter ‘1’

Untuk mencari rumus umum banyaknya bilangan pengandung karakter ‘1’ akan kita gabungkan ketiga kasus :

\begin{array}{lll}p(n)&=&(y)+(8x)+(x)\\&=&9x+y\\&=&9(10^{n-1}-y)+y\\&=&9.10^{n-1}-9y+y\\&=&9.10^{n-1}-8y\end{array}

Karena y adalah banyaknya bilangan pada \overline{BCDE\ldots} yang tidak mengandung karakter ‘1’, maka nilai dari y adalah 9^{n-1}

Dengan mensubstitusikan y=9^{n-1} kita peroleh :

p(n)=9.10^{n-1}-8.9^{n-1}

Rumus di atas adalah rumus umum untuk mencari banyaknya bilangan n-digit yang mengandung karakter ‘1’ di dalamnya.

Rumus Umum Untuk Menghitung Kemunculan Karakter ‘1’ Pada Bilangan n-digit

Sama seperti sebelumnya, untuk mencari rumus umum kemunculan, akan kita gabungkan ketiga kasus :

\begin{array}{llll}f(n)&=&\mbox{Kasus 1}+\mbox{Kasus 2}+\mbox{Kasus 3}\\&=&(y)+(8z)+(x+z)\\&=&x+y+9z\\&=&10^{n-1}+9z&\mbox{Karena }x+y=10^{n-1}\\f(n)&=&10^{n-1}+9(f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1))&\mbox{Karena }z=g(n-1)=f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)\end{array}

Kita peroleh rumus umum untuk mencari f(n). Mari kita cicip rumus kita :

\begin{array}{lll}f(1)&=&1\\\\f(2)&=&10^{2-1}+9(f(1))\\&=&10^1+9.1\\&=&19\\\\f(3)&=&10^{3-1}+9(f(1)+f(2))\\&=&10^2+9(1+19)\\&=&280\\\\f(4)&=&10^{4-1}+9(f(1)+f(2)+f(3))\\&=&10^3+9(1+19+280)\\&=&3700\\\\&&\cdots\end{array}

Walaupun rumus ini dapat memberikan hasil perhitungan dengan benar, namun rumus ini kurang ‘pas’ untuk diandalkan karena rumus ini bersifat rekursif dan sangat tergantung pada hasil-hasil perhitungan pada digit-digit sebelumnya.

Sekarang akan kita coba untuk memodifikasi rumus ini menjadi sedikit lebih baik. Perhatikan beberapa aljabar di bawah ini :

\begin{array}{rll}f(1)+f(2)&=&f(1)+10^1+9(f(1))\\&=&10^1+10(f(1))\\&=&10^1(1+f(1))\end{array}

\begin{array}{rll}f(1)+f(2)+f(3)&=&f(1)+f(2)+10^2+9(f(1)+f(2))\\&=&10^2+10(f(1)+f(2))\\&=&10^2+10.10^1(1+f(1))\\&=&10^2+10^2(1+f(1))\\&=&10^2(1+1+f(1))\end{array}

\begin{array}{rll}f(1)+f(2)+f(3)+f(4)&=&f(1)+f(2)+f(3)+10^3+9(f(1)+f(2)+f(3))\\&=&10^3+10(f(1)+f(2)+f(3))\\&=&10^3+10.10^2(1+1+f(1))\\&=&10^3+10^3(1+1+f(1))\\&=&10^3(1+1+1+f(1))\end{array}

dst…

\begin{array}{rll}f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)&=&10^{n-2}(1+1+1+\ldots+1+1+f(1))\\&=&10^{n-2}(n-2+f(1))\\&=&10^{n-2}(n-2+1)\\&=&10^{n-2}(n-1)\end{array}

Catatan : Aljabar di atas bukan pembuktian matematika yang sah. Walaupun demikian, pola aljabar di atas akan terus berulang-ulang dan hasilnya akan sama seperti yang ada di atas. Pembuktian matematis yang sah diserahkan kepada pembaca.

Sekarang, kita dapat menghitung f(n) dengan mudah, tanpa harus rekursif lagi

\begin{array}{lll}f(n)&=&10^{n-1}+9(f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1))\\&=&10^{n-1}+9.10^{n-2}.(n-1)\\&=&10.10^{n-2}+9.10^{n-2}.(n-1)\\&=&10^{n-2}(10+9.(n-1))\\&=&10^{n-2}(10+9n-9)\\f(n)&=&10^{n-2}(9n+1)\end{array}

Rumus yang terakhir ini adalah rumus yang kita inginkan. Rumus ini mampu “loncat” langsung ke digit yang kita inginkan tanpa harus menghitung satu persatu setiap digit mulai dari 1, 2, 3, …, sampai n-1.

Jawaban Atas Pertanyaan

Terkait dengan pertanyaan yang diajukan di awal artikel.

  1. Banyaknya bilangan di dalam himpunan tersebut yang mengandung karakter ‘1’ ada sebanyak :
    \begin{array}{lll}p(1)+p(2)+p(3)+1&=&(9.10^0-8.9^0)+(9.10^1-8.9^1)+(9.10^2-8.9^2)+1\\&=&(9.1-8.1)+(9.10-8.9)+(9.100-8.81)+1\\&=&(9-8)+(90-72)+(900-648)+1\\&=&1+18+252+1\\&=&272\end{array}
  2. Banyaknya kemunculan karakter ‘1’ ada sebanyak :
    \begin{array}{lll}f(1)+f(2)+f(3)+1&=&(10^{1-2}.(9.1+1))+(10^{2-2}.(9.2+1))+(10^{3-2}.(9.3+1))+1\\&=&(10^{-1}.(9+1))+(10^0.(18+1))+(10^1.(27+1))+1\\&=&(10^{-1}.10)+(1.19)+(10.28)+1\\&=&1+19+280+1\\&=&301\end{array}

Catatan : Perhatikan bahwa dalam soal di atas penulis mengasumsikan bahwa 1 dan 1000 diikutsertakan dalam perhitungan (inclusive). Dengan demikian rentang 1-1000 melibatkan 3 buah digit, yaitu digit 1, digit 2, dan digit 3 plus angka 1000 itu sendiri.

Angka 1 pada perhitungan di atas datang dari angka 1000 yang banyaknya ada 1 dan jelas sekali mengandung karakter ‘1’ di dalamnya.

The Code giveth, The Code Taketh away

November 8, 2010

[Mengapa oh Mengapa] Sulap Tanggal Lahir

Filed under: Brain Teaser, Matematika — Hendra Jaya @ 8:02 am

Sulap tanggal lahir adalah sulap matematis yang sangat populer. Sulap ini biasanya meminta “korban” untuk melakukan beberapa operasi matematika sederhana terkait dengan tanggal/bulan/tahun lahirnya. Di akhir sulap, korban akan diminta untuk memberikan angka hasil perhitungannya. Setelah menerima angka tersebut, abrakadabra pun terjadi. Sang pesulap mampu menebak dengan tepat tanggal/bulan/tahun lahir korban.

Artikel ini ditulis untuk menjelaskan, secara matematis tentunya, mengapa “Sulap Tanggal Lahir” dapat dilakukan.

Referensi

Ada banyak sekali metode untuk melakukan sulap tanggal lahir. Berikut ini penulis sajikan dua buah di antaranya.

Sulap 1

  • Kalikan tanggal lahir anda dengan 4, simpan hasilnya.
  • Tambahkan angka tersebut dengan 13, simpan hasilnya.
  • Kalikan angka tersebut dengan 25, simpan hasilnya.
  • Kurangi angka tersebut dengan 200, simpan hasilnya.
  • Tambahkan bulan lahir anda pada angka tersebut, simpan hasilnya.
  • Kalikan angka tersebut dengan 2, simpan hasilnya.
  • Kurangi angka tersebut dengan 40, simpan hasilnya.
  • Kalikan angka tersebut dengan 50, simpan hasilnya.
  • Tambahkan dua digit tahun kelahiran anda pada angka tersebut, simpan hasilnya

Pesulap lalu meminta angka tersebut dan melakukan operasi berikut :

  • Angka yang diperoleh dikurangi 10500
  • Sisanya adalah tanggal lahir korban dalam format “ddmmyy”

Sebagai contoh, penulis akan ambil tanggal lahir dedek tersayang :oops:, yaitu 17 Oktober 1985 (Bentuk lain : 17-10-1985)

  • Kalikan tanggal lahir dengan 4. Angka = 17 x 4 = 68
  • Tambahkan dengan 13. Angka = 68 + 13 = 81
  • Kalikan dengan 25. Angka = 81 x 25 = 2025
  • Kurangi dengan 200. Angka = 2025 – 200 = 1825
  • Tambahkan bulan lahir. Angka = 1825 + 10 = 1835
  • Kalikan dengan 2. Angka = 1835 x 2 = 3670
  • Kurangi dengan 40. Angka = 3670 – 40 = 3630
  • Kalikan dengan 50. Angka = 3630 x 50 = 181500
  • Tambahkan 2 digit tahun lahir. Angka = 181500 + 85 = 181585

Korban lalu memberikan angka 181585 ini kepada pesulap dan pesulap pun (secara diam-diam) melakukan :

  • Kurangi dengan 10500. Angka = 181585 – 10500 = 171085
  • Angka ini lalu dipecah-pecah menjadi 3 bagian, yaitu 17-10-85

Abrakadabra pun terjadi. Pesulap tinggal mengatakan “Saudari Nurul, benarkah anda lahir pada tanggal 17, bulan 10 tahun 85?”

Sulap 2

  • Kalikan tanggal lahir anda dengan 5, lalu simpan hasilnya.
  • Tambahkan angka tersebut dengan 5, simpan hasilnya.
  • Kalikan angka tersebut dengan 20, simpan hasilnya.
  • Kurangi angka tersebut dengan 85, simpan hasilnya. (Dimodifikasi sedikit oleh penulis)
  • Tambahkan bulan lahir anda pada angka tersebut, simpan hasilnya.
  • Kalikan angka tersebut dengan 2, simpan hasilnya.
  • Kurangi angka tersebut dengan 60, simpan hasilnya.
  • Kalikan angka tersebut dengan 50, simpan hasilnya.
  • Tambahkan 2 digit terakhir tahun kelahiran anda pada angka tersebut, simpan hasilnya.

Pesulap lalu meminta angka tersebut dan melakukan operasi berikut :

  • Angka yang diperoleh ditambah dengan 1500
  • Sisanya adalah tanggal lahir korban dalam format “ddmmyy”

Catatan : Penulis – dengan sengaja – memodifikasi sulap 2 agar sedikit lebih singkat. Pada versi asli (lih. referensi), dilakukan satu buah “pengurangan dengan 100” lalu “penambahan dengan 15”. Kedua operasi aritmatika ini penulis sederhanakan menjadi satu buah “pengurangan dengan 85”.

Masih dengan contoh yang sama, yaitu tanggal lahir dedek tersayang :oops:, 17 Oktober 1985 alias 17-10-1985.

  • Kalikan tanggal lahir anda dengan 5. Angka = 17 x 5 = 85
  • Tambahkan dengan 5. Angka = 85 + 5 = 90
  • Kalikan dengan 20. Angka = 90 x 20 = 1800
  • Kurangi dengan 85. Angka = 1800 – 85 = 1715
  • Tambahkan bulan lahir anda. Angka = 1715 + 10 = 1725
  • Kalikan dengan 2. Angka = 1725 x 2 = 3450
  • Kurangi dengan 60. Angka = 3450 – 60 = 3390
  • Kalikan dengan 50. Angka = 3390 x 50 = 169500
  • Tambahkan 2 digit terakhir tahun lahir anda. Angka = 169500 + 85 = 169585

Tanpa curiga, korban memberitahukan angka 169585 ini kepada pesulap dan pesulap pun langsung melakukan :

  • Tambahkan dengan 1500. Angka = 169585 + 1500 = 171085
  • Memecah angka ini menjadi 3 bagian, yaitu 17-10-85

Abrakadabra pun terjadi. Dengan sedikit acting, pesulap berujar “Sepertinya ada kesalahan disini… Tanggal lahir saudari Nurul adalah 17 Oktober 1985. Benarkah begitu?”

Pra-Pembahasan

Tanggal lahir adalah x
Bulan lahir adalah y
Dua digit terakhir tahun lahir adalah z
Angka yang dihitung oleh korban adalah m
Nilai m yang sudah “dimanipulasi” oleh pesulap adalah n

Aljabar Sulap 1

\begin{array}{rlll}m&=&4x&\mbox{Kalikan tanggal lahir dengan 4}\\m&=&4x+13&\mbox{Tambahkan dengan 13}\\m&=&25.(4x+13)&\mbox{Kalikan dengan 25}\\&=&100x+325\\m&=&100x+125&\mbox{Kurangi dengan 200}\\m&=&100x+y+125&\mbox{Tambahkan bulan lahir}\\m&=&2.(100x+y+125)&\mbox{Kalikan dengan 2}\\&=&200x+2y+250\\m&=&200x+2y+210&\mbox{Kurangi dengan 40}\\m&=&50.(200x+2y+210)&\mbox{Kalikan dengan 50}\\&=&10000x+100y+10500\\m&=&10000x+100y+z+10500&\mbox{Tambahkan 2 digit terakhir tahun lahir}\\n&=&10000x+100y+z&\mbox{Kurangi dengan 10500}\end{array}

Aljabar Sulap 2

\begin{array}{rlll}m&=&5x&\mbox{Kalikan tanggal lahir dengan 5}\\m&=&5x+5&\mbox{Tambahkan 5}\\m&=&20.(5x+5)&\mbox{Kalikan dengan 20}\\&=&100x+100\\m&=&100x+15&\mbox{Kurangi dengan 85}\\m&=&100x+y+15&\mbox{Tambahkan bulan lahir}\\m&=&2.(100x+y+15)&\mbox{Kalikan dengan 2}\\&=&200x+2y+30\\m&=&200x+2y-30&\mbox{Kurangi dengan 60}\\m&=&50.(200x+2y-30)&\mbox{Kalikan dengan 50}\\&=&10000x+100y-1500\\m&=&10000x+100y+z-1500&\mbox{Tambahkan 2 digit terakhir tahun lahir}\\n&=&10000x+100y+z&\mbox{Tambahkan 1500}\end{array}

Pembahasan

Angka yang saat ini dipegang oleh pesulap, yaitu n, me-representasikan tanggal-bulan-tahun lahir si korban dalam format “ddmmyy”.
Berikut penjelasannya :

Misalkan X adalah sebuah bilangan 2 digit, dimana digit pertama adalah X_1 dan digit kedua adalah X_2. Secara matematis \overline{X}=10.X_1+X_2

Misalkan Y adalah sebuah bilangan 2 digit, dimana digit pertama adalah Y_1 dan digit kedua adalah Y_2. Secara matematis \overline{Y}=10.Y_1+Y_2

Digit pertama pada Z kita namai Z_1 dan digit kedua kita namai Z_2. Secara matematis \overline{Z}=10.Z_1+Z_2

Akan kita peroleh :

\begin{array}{lll}n&=&10000x+100y+z\\n&=&10000(10.x_1+x_2)+100(10.y_1+y_2)+(10.z_1+z_2)\\n&=&100000x_1+10000x_2+1000.y_1+100y_2+10.z_1+z_2\end{array}

Jika di-representasikan dalam penjumlahan akan berbentuk seperti :

\begin{array}{ccccccr}X_1&0&0&0&0&0\\&X_2&0&0&0&0\\&&Y_1&0&0&0\\&&&Y_2&0&0\\&&&&Z_1&0\\&&&&&Z_2\\-&-&-&-&-&-&+\\X_1&X_2&Y_1&Y_2&Z_1&Z_2\end{array}

Sekarang, karena :

\overline{X} adalah tanggal lahir
\overline{Y} adalah bulan lahir
\overline{Z} adalah 2 digit terakhir tahun lahir

Maka nilai n akan secara tegas menyatakan tanggal-bulan-tahun lahir si korban dalam format “ddmmyy”. Pesulap hanya perlu membacakannya dengan sedikit berpura-pura terkejut 🙂

Bagaimana jika tanggal/bulan/tahun lahir adalah bilangan 1 digit?

Tidak ada masalah

Jika tanggal lahir adalah bilangan 1 digit, maka nilai n yang semula berupa bilangan 6 digit, kini akan berbentuk bilangan 5 digit. Sedikit lebih jauh, jumlah digit pada n hanya bergantung kepada tanggal lahir. Seorang pesulap yang handal pasti sudah menyadari hal ini.

Jika bulan lahir adalah bilangan 1 digit, maka bilangan yang dihasilkan tidak berubah digit-nya. Satu-satunya dampak yang perlu disadari hanyalah digit ke-4 dari kanan, yakni Y_1, bernilai 0.

Jika tahun lahir adalah bilangan 1 digit-pun tidak ada masalah. Sama seperti sebelumnya, satu-satunya efek yang timbul hanyalah digit ke-2 dari kanan, yakni Z_1, bernilai 0.

Untuk tahun lahir kita ambil contoh z=\overline{01}.

Dalam ilmu matematika yang “buta”, kita tidak bisa memastikan apakah \overline{01} bermakna 1801 atau 1901, 2001 dan seterusnya. Hal ini wajar mengingat bilangan-bilangan …, 1801, 1901, 2001,… semuanya kongruen dengan \overline{01} dalam modulo 100. Tetapi, selisih 1 abad jelas memberikan efek fisik yang kuat. Seseorang yang lahir di tahun 1901 jelas akan terlihat “berbeda” dengan orang yang lahir di tahun 2001. Untuk membedakannya tentu bukan perkara yang sulit.

Math Magic

November 7, 2010

Algoritma Logaritma

Filed under: Algoritma, Logaritma, Matematika — Hendra Jaya @ 12:17 pm

Referensi

Binary Logarithm

Pra-Pembahasan

Artikel ini akan membahas implementasi teknis tentang algoritma menghitung logaritma. Dimulai dari logaritma basis 2 (binary logarithm) sampai ke basis yang lain. Artikel ini mengasumsikan pembaca sudah memahami sifat-sifat dasar logaritma seperti :

\begin{array}{lll}log_a(a)&=&1\\log_a(a^n)&=&n\\log_a(x^y)&=&y.log_a(x)\\log_a(xy)&=&log_a(x)+log_a(y)\\log_a(\frac{x}{y})&=&log_a(x)-log_a(y)\end{array}

Logaritma dalam basis 2 secara matematis dinyatakan sebagai log_2(x) atau ada pula yang menuliskan lb(x)

Pembahasan

Setiap bilangan real positif x selalu dapat ditulis dalam basis 2 (biner), maka berlaku 2^n\leq x<2^{n+1} dimana n\in\mathbb{Z}.
Perhatikan bahwa persamaan 2^n=x hanya terjadi jika dan hanya jika x adalah bilangan kelipatan 2 (power of two).

Sebagai contoh :

\begin{array}{llcllcrlllr}2^0&\leq&1&<&2^1&\text{artinya}&0&\leq&log_2(1)&<&1\\2^1&\leq&2&<&2^2&\text{artinya}&1&\leq&log_2(2)&<&2\\2^2&\leq&4&<&2^3&\text{artinya}&2&\leq&log_2(4)&<&3\\2^-1&\leq&0.5&<&2^0&\text{artinya}&-1&\leq&log_2(0.5)&<&0\\2^0&\leq&1.414&<&2^1&\text{artinya}&0&\leq&log_2(1.414)&<&1\\2^2&\leq&6.5796&<&2^3&\text{artinya}&2&\leq&log_2(6.5796)&<&3\\2^6&\leq&64&<&2^7&\text{artinya}&6&\leq&log_2(64)&<&7\\2^{-4}&\leq&\frac{1}{16}&<&2^{-3}&\text{artinya}&-4&\leq&log_2(\frac{1}{16})&<&-3\\2^3&\leq&10&<&2^4&\text{artinya}&3&\leq&log_2(10)&<&4\end{array}

Secara sekilas dapat kita lihat bahwa log_2(x) tidak selalu berupa bilangan bulat. Nilai log_2(x) hanya akan bulat, yaitu n, jika dan hanya jika x adalah bilangan kelipatan 2 (power of two). Hal ini senada dengan paragraf sebelumnya.

Namun, untuk log_2(x) yang tidak bulat, maka nilainya pasti berada di rentang n dan n+1.
Atau secara matematis log_2(x)=n+\text{suatu nilai yang tidak bulat}

Contoh lagi :

\begin{array}{lllll}log_2(1)&=&0\\log_2(2)&=&1\\log_2(4)&=&2\\log_2(0.5)&=&-1\\log_2(1.414)&=&0.4997&=&0+0.4997\\log_2(6.5796)&=&2.7179&=&2+0.7179\\log_2(64)&=&6\\log_2(\frac{1}{16})&=&-4\\log_2(10)&=&3.3219&=&3+0.3219\end{array}

Sekarang, melalui aljabar sederhana, kita bisa memperoleh :

\begin{array}{rlclll}2^n&\leq&x&<&2^{n+1}\\1&\leq&2^{-n}.x&<&2&\mbox{Kalikan ketiga bagian dengan }2^{-n}\\log_2(1)&\leq&log_2(2^{-n}.x)&<&log_2(2)&\mbox{Kenakan fungsi }log_2(x)\mbox{ pada ketiga bagian pertidaksamaan}\\ 0&\leq&log_2(2^{-n})+log_2(x)&<&1\\ 0&\leq&-n+log_2(x)&<&1\\ 0&\leq&log_2(y)&<&1&\mbox{Misalkan }log_2(y)=log_2(x)-n\\1&\leq&y&<&2\end{array}

Di dalam bagian terakhir pertidaksamaan kita peroleh 1\leq y<2 dimana log_2(x)=log_2(y)+n

Dari bentuk log_2(x)=log_2(y)+n, pembaca seharusnya dapat memaklumi bahwa n adalah bagian bulat (integer part) dari log_2(x) sedangkan log_2(y) adalah bagian tidak bulat (fractional part). Seperti sudah dijelaskan di beberapa paragraf sebelum ini.

Untuk menghitung bagian yang bulat dapat dilakukan dengan mudah. Yaitu cukup dengan mengalikan/membagi x dengan 2 secara terus menerus sampai diperoleh 1\leq x<2.

Mengingat nilai log_2(1) adalah 0 dan nilai dari log_2(2) adalah 1, maka nilai dari log_2(x) sekarang pasti berupa 0.abcd\ldots Nilai inilah yang dimaksud dengan “bagian tidak bulat”.

Lantas, bagaimana menghitung bagian yang tidak bulat-nya?

Untuk menghitung bagian yang tidak bulat akan kita lakukan trik “mengkuadratkan terus menerus”.

Karena 1\leq y<2, kuadratkan bagian tengah menjadi 1\leq y^2<2

Karena 1\leq y^2<2, kuadratkan bagian tengah menjadi 1\leq y^4<2

Karena 1\leq y^4<2, kuadratkan bagian tengah menjadi 1\leq y^8<2

Berhenti ketika 2\leq y^{2^m}<4.

Triknya cukup mudah dimengerti. Yaitu kuadratkan terus sampai bagian tengah lebih besar atau sama dengan 2.

Intermezzo

Mengapa trik ini dapat dipakai?

Suatu bilangan 1.abcd\ldots jika dikuadratkan berkali-kali pasti akan “berkembang” sehingga pada akhirnya menembus angka 2. Kita tidak tahu berapa kali “pengkuadratan” yang diperlukan. Yang pasti, cepat atau lambat pasti bilangan tersebut akan menembus angka 2.

Sebagai contoh angka 1.001 baru akan menembus 2 pada saat dipangkatkan dengan 694, yakni 1.001^{694}\geq 2.
Di lain pihak, angka 1.2 sudah menempus angka 2 saat dipangkatkan dengan 4, yakni 1.2^4\geq 2.

Mungkinkah bilangan tersebut – ketika menembus angka 2 – juga menembus angka 4?

Ketika menembus angka 2 yang pertama kalinya, bilangan tersebut tidak akan menembus angka 4 karena :

\begin{array}{llllll}1&\leq&x&<&2&\text{Saat ini }x<2\\1^2&\leq&x^2&<&2^2\\1&\leq&x^2&<&4&\text{Saat ini }x^2\geq2\end{array}

Saatnya kembali ke pembahasan algoritma logaritma.

Sekarang, jika kita misalkan z=y^{2^m}, tentu saja berlaku 2\leq z<4. Dengan membagi ketiga bagian pertidaksamaan dengan 2 kita peroleh 1\leq \frac{z}{2}<2

Karena 2\leq y^{2^m}<4 dan z=y^{2^m}, maka :

\begin{array}{rlll}z&=&y^{2^m}\\log_2(z)&=&log_2(y^{2^m})&\text{Kenakan fungsi }log_2(x)\text{ pada kedua sisi}\\log_2(z)&=&2^m.log_2(y)\\log_2(2.\frac{z}{2})&=&2^m.log_2(y)&\text{Identitas perkalian}\\log_2(2)+log_2(\frac{z}{2})&=&2^m.log_2(y)\\1+log_2(\frac{z}{2})&=&2^m.log_2(y)\\2^{-m}.(1+log_2(\frac{z}{2}))&=&log_2(y)&\text{Kalikan kedua sisi dengan } 2^{-m}\\2^{-m}+2^{-m}.log_2(\frac{z}{2})&=&log_2(y)\end{array}

Kita peroleh log_2(y)=2^{-m}+2^{-m}.log_2(\frac{z}{2}). Ingat bahwa sebelumya kita telah mengetahui bahwa 1\leq \frac{z}{2}<2, sehingga trik yang sama dapat kita lakukan :

Dengan meng-kuadratkan \frac{z}{2} secukupnya, kita peroleh 2\leq \frac{z}{2}^{2^n}<4

Misalkan w=\frac{z}{2}^{2^n}, maka 2\leq w<4 atau 1\leq \frac{w}{2}<2

\begin{array}{rll}w&=&\frac{z}{2}^{2^n}\\log_2(w)&=&log_2(\frac{z}{2}^{2^n})\\log_2(w)&=&2^n.log_2(\frac{z}{2})\\log_2(2.\frac{w}{2})&=&2^n.log_2(\frac{z}{2})\\log_2(2)+log_2(\frac{w}{2})&=&2^n.log_2(\frac{z}{2})\\1+log_2(\frac{w}{2})&=&2^n.log_2(\frac{z}{2})\\2^{-n}.(1+log_2(\frac{w}{2}))&=&log_2(\frac{z}{2})\\2^{-n}+2^{-n}.log_2(\frac{w}{2})&=&log_2(\frac{z}{2})\end{array}

Dengan men-substitusikan log_2(\frac{z}{2}), kita peroleh :

log_2(y)=2^{-m}+2^{-m}.(2^{-n}+2^{-n}.log_2(\frac{w}{2}))

Dengan teknik yang sama, kita peroleh log_2(\frac{w}{2})=2^{-o}+2^{-o}.log_2(\frac{v}{2}).

Lalu di-substitusikan menjadi :

log_2(y)=2^{-m}+2^{-m}.(2^{-n}+2^{-n}.(2^{-o}+2^{-o}.log_2(\frac{v}{2})))

Dan seterusnya…

Sehingga bentuk umum-nya dapat dituliskan sebagai : log_2(y)=2^{-m}+2^{-m}.(2^{-n}+2^{-n}.(2^{-o}+2^{-o}(\ldots)))

atau ekivalen dengan : log_2(y)=2^{-m}+2^{-m-n}+2^{-m-n-o}+\ldots

atau jika ditulis ke dalam bentuk yang lebih seragam : log_2(y)=2^{-m_1}+2^{-m_1-m_2}+2^{-m_1-m_2-m_3}+\ldots

Sampai disini kita telah dapat menghitung bagian tidak bulat (fractional part) dari log_2(x).
Dengan menggabungkan bagian bulatnya kita peroleh log_2(x)=n+2^{-m_1}+2^{-m_1-m_2}+2^{-m_1-m_2-m_3}+\ldots

Dimana :

x adalah sembarang bilangan real positif, x>0 dan x\in\mathbb{R}
n adalah bagian bulat dari log_2(x)
2^{-m_1}+2^{-m_1-m_2}+2^{-m_1-m_2-m_3}+\ldots adalah bagian tidak bulat dari log_2(x)
Galat dari algoritma ini sangat kecil. Yaitu kurang dari 2^{-(m_1+m_2+m_3+\ldots+m_i)}

Untuk mencari logaritma dalam basis lain dapat menggunakan invarian log_a(b)=\frac{log_2(b)}{log_2(a)}

Pseudo-Code Algoritma log_2(x) :

  1. Asumsikan bahwa kondisi x>0 terpenuhi
  2. Tentukan batas toleransi kesalahan, err, secukupnya.
  3. Bagian bulat :
    1. Ambil a=0
    2. Periksa salah satu rentang nilai yang memenuhi x :
      1. Jika x memenuhi x<1 : lanjut ke langkah 3.3
      2. Jika x memenuhi 1\leq x<2 : lompat ke langkah 4
      3. Jika x memenuhi x\geq 2 : lanjut ke langkah 3.4
    3. Lakukan :
      1. Kali x dengan 2
      2. Kurangi a dengan 1
      3. Periksa apakah kondisi x<1 masih terpenuhi.
        1. Jika masih terpenuhi, kembali ke langkah 3.3
        2. Jika sudah tidak terpenuhi, lompat ke langkah 4
    4. Lakukan :
      1. Bagi x dengan 2
      2. Tambahkan a dengan 1
      3. Periksa apakah kondisi x\geq 2 masih terpenuhi.
        1. Jika masih terpenuhi, kembali ke langkah 3.4
        2. Jika sudah tidak terpenuhi, lompat ke langkah 4
  4. Bagian tidak bulat :
    1. Ambil b=1
    2. Periksa apakah kondisi b>err terpenuhi.
      1. Jika terpenuhi : lanjut ke langkah 4.3
      2. Jika tidak terpenuhi : lompat ke langkah 5
    3. Periksa apakah kondisi 1\leq x<2 terpenuhi.
      1. Jika terpenuhi :
        1. Kuadratkan x
        2. Bagi b oleh 2
        3. Kembali ke langkah 4.2
      2. Jika tidak terpenuhi :
        1. Bagi x oleh 2
        2. Tambahkan a dengan b
        3. Kembali ke langkah 4.2
  5. Hasil akhir algoritma adalah a

Berikut penulis sajikan pseudo-code yang lebih formal :

Pseudo Code Binary Logarithm

Implementasi

Java : Ideone, PDF
C++ : Sabar subur
Python : Logarithm Function

Contoh eksekusi algoritma :

1. Contoh menghitung log_2(0.3)

Nilai x=0.3

Ambil err=10^{-2}=0.01

Periksa rentang :

\begin{array}{rr}\mbox{[TRUE]}&0<0.3<1\\\mbox{[FALSE]}&1\leq 0.3<2\\\mbox{[FALSE]}&2\leq 0.3\end{array}

Menghitung bagian bulat

Nilai a=0

\begin{array}{rrrllll}\mbox{[TRUE]}&0<0.3<1&x&=&2.(0.3)&=&0.6\\&&a&=&0-1&=&-1\\\\\mbox{[TRUE]}&0<0.6<1&x&=&2.(0.6)&=&1.2\\&&a&=&-1-1&=&-2\\\\\mbox{[FALSE]}&0<1.2<1\end{array}

Menghitung bagian tidak bulat

Nilai b=1

\begin{array}{rrrllll}\mbox{[FALSE]}&2\leq 1<4\\\mbox{[TRUE]}&1>0.01&x&=&1.2^2&=&1.44\\&&b&=&\frac{1}{2}&=&0.5\\\\\mbox{[FALSE]}&2\leq 1.44<4\\\mbox{[TRUE]}&0.5>0.01&x&=&1.44^2&=&2.0736\\&&b&=&\frac{0.5}{2}&=&0.25\\\\\mbox{[TRUE]}&2\leq 2.0736<4&x&=&\frac{2.0736}{2}&=&1.0368\\&&a&=&-2+0.25&=&-1.75\\\mbox{[TRUE]}&0.25>0.01&x&=&1.0368^2&=&1.0749542\\&&b&=&\frac{0.25}{2}&=&0.125\\\\\mbox{[FALSE]}&2\leq 1.0749542<4\\\mbox{[TRUE]}&0.125>0.01&x&=&1.0749542^2&=&1.1555266\\&&b&=&\frac{0.125}{2}&=&0.0625\\\\\mbox{[FALSE]}&2\leq 1.1555266<4\\\mbox{[TRUE]}&0.0625>0.01&x&=&1.1555266^2&=&1.3352417\\&&b&=&\frac{0.0625}{2}&=&0.03125\\\\\mbox{[FALSE]}&2\leq 1.3352417<4\\\mbox{[TRUE]}&0.03125>0.01&x&=&1.3352417^2&=&1.7828705\\&&b&=&\frac{0.0625}{2}&=&0.015625\\\\\mbox{[FALSE]}&2\leq 1.7828705<4\\\mbox{[TRUE]}&0.015625>0.01&x&=&1.7828705^2&=&3.1786274\\&&b&=&\frac{0.015625}{2}&=&0.0078125\\\\\mbox{[TRUE]}&2\leq 3.1786274<4&x&=&\frac{3.1786274}{2}&=&1.5893137\\&&a&=&-1.75+0.0078125&=&-1.7421875\\\mbox{[FALSE][STOP]}&0.0078125>0.01\end{array}

Hasil akhir

Dengan demikian log_2(0.3)\approx -1.7421875

2. Contoh menghitung log_2(1.4)

Nilai x=1.4

Ambil err=10^{-2}=0.01

Periksa rentang :

\begin{array}{rr}\text{[FALSE]}&0<1.4<1\\\text{[TRUE]}&1\leq 1.4<2\\\text{[FALSE]}&2\leq 1.4\end{array}

Menghitung bagian bulat

Nilai a=0

Menghitung bagian tidak bulat

Nilai b=1

\begin{array}{rrrllll}\text{[FALSE]}&2\leq 1<4\\\text{[TRUE]}&1>0.01&x&=&1.4^2&=&1.96\\&&b&=&\frac{1}{2}&=&0.5\\\\\text{[FALSE]}&2\leq 1.96<4\\\text{[TRUE]}&0.5>0.01&x&=&1.96^2&=&3.8416\\&&b&=&\frac{0.5}{2}&=&0.25\\\\\text{[TRUE]}&2\leq 3.8416<4&x&=&\frac{3.8416}{2}&=&1.9208\\&&a&=&0+0.25&=&0.25\\\text{[TRUE]}&0.25>0.01&x&=&1.9208^2&=&3.6894726\\&&b&=&\frac{0.25}{2}&=&0.125\\\\\text{[TRUE]}&2\leq 3.6894726<4&x&=&\frac{3.6894726}{2}&=&1.8447363\\&&a&=&0.25+0.125&=&0.375\\\text{[TRUE]}&0.125>0.01&x&=&1.8447363^2&=&3.403052\\&&b&=&\frac{0.125}{2}&=&0.0625\\\\\text{[TRUE]}&2\leq 3.403052<4&x&=&\frac{3.403052}{2}&=&1.701526\\&&a&=&0.375+0.0625&=&0.4375\\\text{[TRUE]}&0.0625>0.01&x&=&1.701526^2&=&2.8951908\\&&b&=&\frac{0.0625}{2}&=&0.03125\\\\\text{[TRUE]}&2\leq 2.8951908<4&x&=&\frac{2.8951908}{2}&=&1.4475954\\&&a&=&0.4375+0.03125&=&0.46875\\\text{[TRUE]}&0.03125>0.01&x&=&1.4475954^2&=&2.0955325\\&&b&=&\frac{0.0625}{2}&=&0.015625\\\\\text{[TRUE]}&2\leq 2.0955325<4&x&=&\frac{2.0955325}{2}&=&1.0477662\\&&a&=&0.46875+0.015625&=&0.484375\\\text{[TRUE]}&0.015625>0.01&x&=&1.0477662^2&=&1.0978141\\&&b&=&\frac{0.015625}{2}&=&0.0078125\\\\\text{[FALSE]}&2\leq 1.0978141<4\\\text{[FALSE][STOP]}&0.0078125>0.01\end{array}

Hasil akhir

Dengan demikian log_2(1.4)\approx 0.484375

3. Contoh menghitung log_2(11)

Nilai x=11

Ambil err=10^{-2}=0.01

Periksa rentang :

\begin{array}{rr}\text{[FALSE]}&0<11<1\\\text{[FALSE]}&1\leq 11<2\\\text{[TRUE]}&2\leq 11\end{array}

Menghitung bagian bulat :

Nilai a=0

\begin{array}{rrrllll}\text{[TRUE]}&11\geq 2&x&=&\frac{11}{2}&=&5.5\\&&a&=&0+1&=&1\\\\\text{[TRUE]}&5.5\geq 2&x&=&\frac{5.5}{2}&=&2.75\\&&a&=&1+1&=&2\\\\\text{[TRUE]}&2.75\geq 2&x&=&\frac{2.75}{2}&=&1.375\\&&a&=&2+1&=&3\\\\\text{[FALSE]}&1.375\geq 2\end{array}

Menghitung bagian tidak bulat :

Nilai b=1

\begin{array}{rrrllll}\text{[FALSE]}&2\leq 1<4\\\text{[TRUE]}&1>0.01&x&=&1.375^2&=&1.890625\\&&b&=&\frac{1}{2}&=&0.5\\\\\text{[FALSE]}&2\leq 1.890625<4\\\text{[TRUE]}&0.5>0.01&x&=&1.890625^2&=&3.5744628\\&&b&=&\frac{0.5}{2}&=&0.25\\\\\text{[TRUE]}&2\leq 3.5744628<4&x&=&\frac{3.5744628}{2}&=&1.7872314\\&&a&=&3+0.25&=&3.25\\\text{[TRUE]}&0.25>0.01&x&=&1.7872314^2&=&3.1941962\\&&b&=&\frac{0.25}{2}&=&0.125\\\\\text{[TRUE]}&2\leq 3.1941962<4&x&=&\frac{3.1941962}{2}&=&1.5970981\\&&a&=&3.25+0.125&=&3.375\\\text{[TRUE]}&0.125>0.01&x&=&1.5970981^2&=&2.5507224\\&&b&=&\frac{0.125}{2}&=&0.0625\\\\\text{[TRUE]}&2\leq 2.5507224<4&x&=&\frac{2.5507224}{2}&=&1.2753612\\&&a&=&3.375+0.0625&=&3.4375\\\text{[TRUE]}&0.0625>0.01&x&=&1.2753612^2&=&1.6265461\\&&b&=&\frac{0.0625}{2}&=&0.03125\\\\\text{[FALSE]}&2\leq 1.6265461<4\\\text{[TRUE]}&0.03125>0.01&x&=&1.6265461^2&=&2.6456525\\&&b&=&\frac{0.0625}{2}&=&0.015625\\\\\text{[TRUE]}&2\leq 2.6456525<4&x&=&\frac{2.6456525}{2}&=&1.3228262\\&&a&=&3.4375+0.015625&=&3.453125\\\text{[TRUE]}&0.015625>0.01&x&=&1.3228262^2&=&1.7498693\\&&b&=&\frac{0.015625}{2}&=&0.0078125\\\\\text{[FALSE]}&2\leq 1.7498693<4\\\text{[FALSE][STOP]}&0.0078125>0.01\end{array}

Hasil akhir :

Dengan demikian log_2(11)\approx 3.453125

Atas nama kerapihan, angka-angka pada perhitungan di atas telah “dipotong” dari angka yang sebenarnya. Pembaca mungkin akan mendapatkan angka yang berbeda jika meng-implementasi dan menjalnkan algoritma ini di dalam komputer ataupun kalkulator.

Hasil perhitungan-perhitungan di atas menggunakan ketelitian 0.01 dari hasil sebenarnya, sehingga ketika di-cross check akan memberikan angka yang tidak terlalu tepat.

Sebagai masukan, penulis biasanya menggunakan ketelitian 10^{-20} agar mendapatkan hasil yang cukup dekat dengan hasil yang sebenarnya. Selain itu, ketelitian tersebut masih sangat mungkin dilakukan pada tipe data “floating point” pada komputer 32 bit yang sehari-harinya penulis gunakan. Di dalam artikel ini, penulis secara sengaja menggunakan ketelitian 10^{-2} agar contoh eksekusi algoritma tidak terlalu panjang.

Sekali lagi, untuk mencari logaritma dalam basis lain dapat menggunakan invarian log_a(b)=\frac{log_2(b)}{log_2(a)}. Selamat mencoba.

Real Programmers Code in Binary

Oktober 23, 2010

Obat Ngantuk Barisan Bilangan 1

Filed under: Barisan Bilangan, Matematika, Puzzle — Hendra Jaya @ 8:37 am

Problem 1

Bintang Carilah rumus suku ke-n (U_n) pada barisan-barisan bilangan di bawah ini dan jelaskan mengapa mereka bukan barisan bilangan aritmatika.

  • Barisan pertama : 1, 4, 9, 16, 25, 36, 49, 64, 81, ….
  • Barisan kedua : 0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, …
  • Barisan ketiga : 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ….
  • Barisan keempat : 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, …

Pembahasan

  • Barisan pertama adalah barisan bilangan kuadrat, yaitu n^2 dengan n\geq 1 dan n\in\mathbb{Z}.
    Barisan ini bukan barisan aritmatika karena jarak tiap suku (d) tidak konstan. Sebagai contoh U_2-U_1=3 sementara U_3-U_2=5
  • Barisan kedua adalah barisan bilangan kubik, yaitu n^3 dengan n\geq 0 dan n\in\mathbb{Z}.
    Barisan ini bukan barisan aritmatika karena jarak tiap suku (d) tidak konstan. Sebagai contoh U_2-U_1=1 sementara U_3-U_2=19
  • Barisan ketiga adalah barisan bilangan segitiga, yaitu \frac{n.(n+1)}{2} dengan n\geq 1 dan n\in\mathbb{Z}.
    Barisan ini bukan barisan aritmatika karena jarak tiap suku (d) tidak konstan. Sebagai contoh U_2-U_1=2 sementara U_3-U_2=3
  • Barisan keempat adalah barisan bilangan segiempat, yaitu \frac{n.(n+1).(n+2)}{6} dengan n\geq 1 dan n\in\mathbb{Z}.
    Barisan ini bukan barisan aritmatika karena jarak tiap suku (d) tidak konstan. Sebagai contoh U_2-U_1=3 sementara U_3-U_2=6

Bilangan segitiga, segiempat, segilima dan seterusnya dikenal sebagai bilangan gambar/polyhedral (figurate number).
Untuk lebih jelasnya silahkan baca di sini.

Sebagai obat ngantuk berikutnya :

  • Buktikan bahwa bilangan segitiga, yaitu \frac{n.(n+1)}{2} dengan n\geq 1 dan n\in\mathbb{Z}, selalu merupakan bilangan bulat.
  • Buktikan bahwa bilangan segiempat, yaitu \frac{n.(n+1).(n+2)}{6} dengan n\geq 1 dan n\in\mathbb{Z}, selalu merupakan bilangan bulat.
  • dst…
  • BintangBintang Buktikan bahwa bilangan polyhedral, yaitu \frac{n.(n+1).(n+2).(n+3)+...+(n+k-1)}{1.2.3.4...k} dengan n\geq 1,k\geq 1 dan n,k\in\mathbb{Z}, selalu merupakan bilangan bulat.

Problem 2

Bintang Misalkan U_1,U_2,U_3,...,U_k adalah sebuah barisan bilangan aritmatik.

Diketahui U_4+U_7+U_{10}=17 dan U_4+U_5+U_6+...+U_{12}+U_{13}+U_{14}=77

Carilah nilai k dimana U_k=13

Sumber : American High School Mathematics Examination

Pembahasan

Dalam setiap deret aritmatik, berlaku Arithmatic Mean, yaitu 2.U_m=U_{m-n}+U_{m+n}

atau secara umum :

\begin{array}{l}(2n+1).U_m=U_{m-n}+U_{m-n+1}+U_{m-n+2}+...+U_{m-2}+U_{m-1}+U_m+U_{m+1}+U_{m+2}+...+U_{m+n-2}+U_{m+n-1}+U_{m+n}\end{array}

Solusi 1, menggunakan rataan aritmatika (Arithmatic Mean) sederhana :

\begin{array}{lllllllllr}2&.&U_{7}&=&U_{4}&+&U_{10}\\&&U_{7}&=&U_{7}\\-&-&-&-&--&-&--&-&--&+\\3&.&U_{7}&=&U_{4}&+&U_{7}&+&U_{10}\\3&.&U_{7}&=&17\\&&U_{7}&=&\frac{17}{3}\end{array}

\begin{array}{llllllll}2&.&U_{9}&=&U_{4}&+&U_{14}\\2&.&U_{9}&=&U_{5}&+&U_{13}\\2&.&U_{9}&=&U_{6}&+&U_{12}\\2&.&U_{9}&=&U_{7}&+&U_{11}\\2&.&U_{9}&=&U_{8}&+&U_{10}\\&&U_{9}&=&U_{9}\\-&-&-&-&-&-&-&+\\11&.&U_{9}&=&77\\&&U_{9}&=&7\end{array}

Sekarang karena U_7=a+6d dan U_9=a+8d, maka :

\begin{array}{lllllr}a&+&8d&=&7\\a&+&6d&=&\frac{17}{3}\\-&-&-&-&-&-\\&&2d&=&\frac{4}{3}\\&&d&=&\frac{2}{3}\end{array}

Karena U_k=a+(k-1)d, maka :

\begin{array}{llrllr}a&+&(k-1)d&=&13\\a&+&6d&=&\frac{17}{3}\\-&-&----&-&-&-\\&&(k-7)d&=&\frac{22}{3}\\&&(k-7)\frac{2}{3}&=&\frac{22}{3}\\&&k-7&=&11\\&&k&=&18\end{array}

Dengan demikian suku ke-k yang memenuhi U_k=13 adalah suku ke-18.

Solusi 2, menggunakan rataan aritmatika (Arithmatic Mean) umum :

\begin{array}{lllclll}U_4&+&U_7&+&U_{10}&=&17\\&&(2.1+1)&.&U_{7}&=&17\\&&3&.&U_{7}&=&17\\&&&&U_{7}&=&\frac{17}{3}\end{array}

\begin{array}{lllllllllllllll}U_4&+&U_5&+&U_6&+&...&+&U_{12}&+&U_{13}&+&U_{14}&=&77\\&&&&&&&&&&(2.5+1)&.&U_{9}&=&77\\&&&&&&&&&&11&.&U_{9}&=&77\\&&&&&&&&&&&&U_{9}&=&7\end{array}

Selanjutnya tinggal menyelesaikan persamaan U_7=\frac{17}{3} dan persamaan U_9=7. Hal ini diserahkan kepada pembaca.

Problem 3

BintangBintang Hitunglah nilai dari \frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+...+\frac{1}{98.99}+\frac{1}{99.100}

Pembahasan

Sebelum mencari jawaban, ada baiknya kita telusuri lebih jauh bentuk tersebut.

Misalkan nilai dari bentuk di atas adalah S, maka S dapat dituliskan sebagai : S=\sum_{n=1}^{99}\frac{1}{n.(n+1)}

Apakah kita bisa meng-eksploitasi sesuatu dari sini? Apakah kita melupakan sesuatu di sini?

Tampaknya memang ada sesuatu yang bisa kita eksploitasi tetapi kita lupakan.

Perhatikan persamaan di bawah ini :

\begin{array}{lllllll}\frac{1}{a}&-&\frac{1}{b}&=&\frac{b}{ab}&-&\frac{a}{ab}\\\\\frac{1}{a}&-&\frac{1}{b}&=&\frac{b-a}{ab}\end{array}

Jika b-a=1, apa yang akan terjadi? Mari kita lihat

\begin{array}{lllllll}b&-&a&=&1\\&&b&=&a&+&1\end{array}

Makna dari persamaan di atas adalah jika a dan b keduanya adalah bilangan bulat, maka a dan b adalah dua buah bilangan bulat yang berturutan. Sepertinya sesuai dengan yang kita inginkan. Mari kita uji.

\begin{array}{lllllll}\frac{1}{n}&-&\frac{1}{n+1}&=&\frac{n+1}{n.(n+1)}&-&\frac{n}{n.(n+1)}\\\\\frac{1}{n}&-&\frac{1}{n+1}&=&\frac{n+1-n}{n.(n+1)}\\\\\frac{1}{n}&-&\frac{1}{n+1}&=&\frac{1}{n.(n+1)}\end{array}

Yap! Persis dengan yang kita inginkan. Sekarang kita eksploitasi.

\begin{array}{llclclclclclclc}S&=&\frac{1}{1.2}&+&\frac{1}{2.3}&+&\frac{1}{3.4}&+&...&+&\frac{1}{98.99}&+&\frac{1}{99.100}\\\\&=&\frac{1}{1}-\frac{1}{2}&+&\frac{1}{2}-\frac{1}{3}&+&\frac{1}{3}-\frac{1}{4}&+&...&+&\frac{1}{98}-\frac{1}{99}&+&\frac{1}{99}-\frac{1}{100}\\\\&=&\frac{1}{1}&+&\frac{1}{2}-\frac{1}{2}&+&\frac{1}{3}-\frac{1}{3}&+&...&+&\frac{1}{98}-\frac{1}{98}&+&\frac{1}{99}-\frac{1}{99}&-&\frac{1}{100}\\\\&=&\frac{1}{1}&-&\frac{1}{100}\\\\S&=&\frac{99}{100}\end{array}

Persamaan S=\sum_{n=1}^{k}\frac{1}{n.(n+1)} ini sendiri secara umum bernilai \frac{k}{k+1}.

Atau jika dituliskan secara utuh menjadi S=\sum_{n=1}^{k}\frac{1}{n.(n+1)}=\frac{k}{k+1}

Problem 4

Bintang Untuk T\in\mathbb{R}, diketahui tiga buah suku pertama pada barisan aritmatik adalah 2T, 5T-1 dan 6T+2. Berapakah nilai suku ke-4?

Pembahasan

\begin{array}{rcl}U_2-U_1&=&U_3-U_2\\(5T-1)-(2T)&=&(6T+2)-(5T-1)\\5T-1-2T&=&6T+2-5T+1\\3T-1&=&T+3\\2T&=&4\\T&=&2\end{array}

Selanjutnya,

\begin{array}{rclr}U_4+U_2&=&2.U_3\\U_4+(5T-1)&=&2.(6T+2)\\U_4+5T-1&=&12T+4\\U_4&=&7T+5\\U_4&=&7.2+5&\text{Substitusikan nilai }T\\U_4&=&19\end{array}

Problem 5

Bintang Diketahui \frac{b+c-a}{a}, \frac{c+a-b}{b} dan \frac{a+b-c}{c} adalah tiga buah suku berurutan pada sebuah barisan aritmatik.

Buktikan bahwa \frac{1}{a}, \frac{1}{b} dan \frac{1}{c} juga merupakan tiga buah suku berurutan pada sebuah barisan aritmatik (tidak harus barisan yang sama).

Pembahasan

Dalam sebuah barisan aritmatik berlaku rataan aritmatik 2.U_{n}=U_{n-k}+U_{n+k}.

Untuk tiga suku yang berturutan, nilai k adalah 1.

Yaitu 2.U_{n}=U_{n-1}+U_{n+1} atau dalam bentuk lain 2.U_{n+1}=U_{n}+U_{n+2}.

Menurut sifat ini, jika \{\frac{1}{a},\frac{1}{b},\frac{1}{c}\} adalah tiga suku berturutan pada sebuah barisan aritmatik maka akan terpenuhi rataan aritmatik 2.\frac{1}{b}=\frac{1}{a}+\frac{1}{c}

Sekarang, misalkan :

U_k=\frac{b+c-a}{a}

U_{k+1}=\frac{c+a-b}{b}

U_{k+2}=\frac{a+b-c}{c}

Dengan menggunakan sifat U_{n+1}-U_n=U_{m+1}-U_m, maka

\begin{array}{rcll}U_{k+1}-U_k&=&U_{k+2}-U_{k+1}\\\\\frac{c+a-b}{b}-\frac{b+c-a}{a}&=&\frac{a+b-c}{c}-\frac{c+a-b}{b}\\\\(\frac{c}{b}+\frac{a}{b}-\frac{b}{b})-(\frac{b}{a}+\frac{c}{a}-\frac{a}{a})&=&(\frac{a}{c}+\frac{b}{c}-\frac{c}{c})-(\frac{c}{b}+\frac{a}{b}-\frac{b}{b})\\\\\frac{c}{b}+\frac{a}{b}-\frac{b}{b}-\frac{b}{a}-\frac{c}{a}+\frac{a}{a}&=&\frac{a}{c}+\frac{b}{c}-\frac{c}{c}-\frac{c}{b}-\frac{a}{b}+\frac{b}{b}&\text{Sifat distributif perkalian}\\\\\frac{c}{b}+\frac{a}{b}-1-\frac{b}{a}-\frac{c}{a}+1&=&\frac{a}{c}+\frac{b}{c}-1-\frac{c}{b}-\frac{a}{b}+1&\text{Sederhanakan (Identitas pembagian)}\\\\\frac{c}{b}+\frac{a}{b}-\frac{b}{a}-\frac{c}{a}&=&\frac{a}{c}+\frac{b}{c}-\frac{c}{b}-\frac{a}{b}\\\\\frac{c}{b}+\frac{a}{b}+1-\frac{b}{a}-\frac{c}{a}-1&=&\frac{a}{c}+\frac{b}{c}+1-\frac{c}{b}-\frac{a}{b}-1&\text{Tambahkan }0\text{ pada kedua sisi (Identitas penjumlahan)}\\\\\frac{c}{b}+\frac{a}{b}+\frac{b}{b}-\frac{b}{a}-\frac{c}{a}-\frac{a}{a}&=&\frac{a}{c}+\frac{b}{c}+\frac{c}{c}-\frac{c}{b}-\frac{a}{b}-\frac{b}{b}&\text{Identitas pembagian}\\\\\frac{c+a+b}{b}-\frac{b+c+a}{a}&=&\frac{a+b+c}{c}-\frac{c+a+b}{b}&\text{Kelompokkan berdasarkan penyebut (Sifat distributif pembagian)}\\\\\frac{a+b+c}{b}-\frac{a+b+c}{a}&=&\frac{a+b+c}{c}-\frac{a+b+c}{b}&\text{Susun ulang pembilang (Sifat komutatif penjumlahan)}\\\\\frac{1}{b}-\frac{1}{a}&=&\frac{1}{c}-\frac{1}{b}&\text{Asumsikan }a+b+c\neq 0\text{. Kalikan kedua sisi dengan }\frac{1}{a+b+c}\text{ (Identitas perkalian)}\\\\\frac{2}{b}&=&\frac{1}{a}+\frac{1}{c}\end{array}

Perhatikan bahwa keterbuktian persamaan \frac{2}{b}=\frac{1}{a}+\frac{1}{c} sebenarnya tidak mengimplikasikan bahwa \frac{1}{a}, \frac{1}{b} dan \frac{1}{c} merupakan tiga suku yang berturutan pada sebuah deret aritmatik. Hal ini karena wajar karena property rataan aritmatik ini tidak biimplikatif (jika dan hanya jika).

Untuk membuktikan bahwa \frac{1}{a}, \frac{1}{b} dan \frac{1}{c} merupakan tiga suku yang berturutan pada sebuah deret aritmatik, kita perlu melakukan uji jarak/difference (d) pada ketiga suku ini. yaitu :

\begin{array}{rlllrll}U_{k+2}&-&U_{k+1}&=&U_{k+1}&-&U_{k}\\\frac{1}{c}&-&\frac{1}{b}&=&\frac{1}{b}&-&\frac{1}{a}\end{array}

Hal itu dapat dilakukan dengan metode kontradiktif. Yaitu, dengan mengasumsikan ketiga bilangan ini tidak tersusun dalam deret aritmatika. Atau secara matematis dengan membuktikan

\frac{1}{c}-\frac{1}{b}\neq\frac{1}{b}-\frac{1}{a}

Sayangnya, asumsi ini gagal karena

\begin{array}{llllllll}&\frac{1}{c}&-&\frac{1}{b}&\neq&\frac{1}{b}&-&\frac{1}{a}\\\Leftrightarrow&\frac{1}{a}&+&\frac{1}{c}&\neq&\frac{2}{b}\end{array}

Suatu kontradiksi yang mengakibatkan asumsi kita salah. Dengan demikian benarlah bahwa \frac{1}{a}, \frac{1}{b} dan \frac{1}{c} merupakan tiga suku yang berturutan pada sebuah deret aritmatik.

Forget All You Have Learned

Problem 6

Bintang Ada berapa banyak nilai n sedemikian rupa sehingga 1+2+3+4+...+n habis membagi 6n.

Sumber : American Mathematics Competition 12^{th} grade

Pembahasan

Karena 1+2+3+...+n=\frac{n.(n+1)}{2}, maka :

\begin{array}{lllllllllll}6n&=&\frac{n.(n+1)}{2}&.&p\\6&=&\frac{n+1}{2}&.&p\\12&=&(n+1)&.&p\end{array}

Karena baik n maupun p adalah bilangan bulat positif dan himpunan faktor-faktor positif dari 12 adalah A=\{1,2,3,4,6,12\}, maka nilai n dapat dicari dengan memeriksa semua faktor-faktor positif dari 12. Sebagai berikut :

n+1=1\Leftrightarrow n=0 (tidak memenuhi karena n\geq 1)

n+1=2\Leftrightarrow n=1

n+1=3\Leftrightarrow n=2

n+1=4\Leftrightarrow n=3

n+1=6\Leftrightarrow n=5

n+1=12\Leftrightarrow n=11

Dengan demikian, himpunan nilai n yang memenuhi sifat ini adalah N=\{1,2,3,5,11\} yang banyaknya ada 5 buah.

Problem 7

Bintang Dalam sebuah barisan aritmatika U_1,U_2,U_3..., diketahui U_8=2001.

Jika jarak antar suku satu dengan suku yang lain (d) adalah sebuah bilangan bulat, berapa nilai minimum d agar U_{17}>10000?

Sumber : Introduction to Algebra

Pembahasan

Diketahui : U_8=a+7d=2001 dengan d\in\mathbb{Z}

Ditanya : Nilai d minimum agar U_{17}=a+16d>10000

Jawab :

\begin{array}{rlrll}a&+&16d&>&10000\\(a+7d)&+&9d&>&10000\\2001&+&9d&>&10000\\&&9d&>&7999\\&&d&>&888.777\end{array}

Karena d\in\mathbb{Z}, maka :

\begin{array}{lll}d_{min}&=&\lceil 888.777\rceil\\d_{min}&=&889\end{array}

Problem 8

BintangBintang Hitunglah nilai dari \frac{1}{1}+\frac{1}{3}+\frac{1}{6}+\frac{1}{10}+...+\frac{1}{5050}.

Pembahasan

Sebelum memulai pembahasan ada baiknya kita cari tahu pola barisan bilangan yang diberikan.

Catatan : Ilmu mencari pola memang sangat sulit untuk diajarkan. Sepertinya ilmu ini datang dari jam terbang. Pembaca tidak perlu berkecil hati karenanya.

Barisan 1,3,6,10,...,5050 adalah barisan dengan pola \frac{n.(n+1)}{2}.  Yaitu barisan bilangan segitiga. Atau jika ingin sedikit lebih jelas perhatikan persamaan-persamaan di bawah ini :

\begin{array}{lrlllllllllllll}&1&=&1&&&&&&&&&&=&\frac{1.2}{2}\\\\&3&=&1&+&2&&&&&&&&=&\frac{2.3}{2}\\\\&6&=&1&+&2&+&3&&&&&&=&\frac{3.4}{2}\\\\&10&=&1&+&2&+&3&+&4&&&&=&\frac{4.5}{2}\\\\dst...\\\\&5050&=&1&+&2&+&3&+&4&+&...&+100&=&\frac{100.101}{2}\end{array}

Kembali ke persoalan. Dengan demikian barisan bilangan pada soal berpola \frac{1}{\frac{n.(n+1)}{2}} atau setara dengan \frac{2}{n.(n+1)}.

Sama seperti pada problem 3, kita bisa melakukan trik sederhana dengan mengubah bentuknya menjadi \frac{2}{n}-\frac{2}{n+1}. Suatu bentuk yang ideal untuk kita manfaatkan.

\begin{array}{llclclclclclclc}S&=&\frac{1}{1}&+&\frac{1}{3}&+&\frac{1}{6}&+&\frac{1}{10}&+&...&+&\frac{1}{5050}\\\\S&=&\frac{2}{2}&+&\frac{2}{6}&+&\frac{2}{12}&+&\frac{2}{20}&+&...&+&\frac{2}{10100}\\\\S&=&\frac{2}{1.2}&+&\frac{2}{2.3}&+&\frac{2}{3.4}&+&\frac{2}{4.5}&+&...&+&\frac{2}{100.101}\\\\&=&\frac{2}{1}-\frac{2}{2}&+&\frac{2}{2}-\frac{2}{3}&+&\frac{2}{3}-\frac{2}{4}&+&\frac{2}{4}-\frac{2}{5}&+&...&+&\frac{2}{100}-\frac{2}{101}\\\\&=&\frac{2}{1}&+&\frac{2}{2}-\frac{2}{2}&+&\frac{2}{3}-\frac{2}{3}&+&\frac{2}{4}-\frac{2}{4}&+&...&+&\frac{2}{100}-\frac{2}{100}&-&\frac{2}{101}\\\\&=&\frac{2}{1}&-&\frac{2}{101}\\\\S&=&\frac{200}{101}\end{array}

Problem 9

BintangBintangBintang Diketahui bahwa :

  1. Setiap serangga tampan membelah diri menjadi seekor serangga buruk rupa dan seekor serangga bodoh.
  2. Setiap serangga buruk rupa membelah diri menjadi dua ekor serangga tampan.
  3. Setiap serangga bodoh membelah diri menjadi seekor serangga buruk rupa dan seekor serangga tampan.
  4. Serangga hanya membelah diri ketika dia mati.
  5. Masa hidup setiap serangga (tidak perduli jenisnya) adalah sama.
  6. Pada awalnya hanya ada seekor serangga tampan (origin of species). Serangga ini disebut sebagai serangga generasi pertama.

Berapa jumlah:

  1. Total seluruh serangga generasi ke-5?
  2. Serangga (masing-masing jenis) generasi ke-5?
  3. Total seluruh serangga generasi ke-n?
  4. Serangga (masing-masing jenis) generasi ke-n?

Pembahasan

Draft

Problem 10

Bintang Dalam sebuah deret aritmatika, diketahui fakta-fakta berikut :

  • U_1+U_2+U_3+...+U_{100}=100

dan

  • U_{101}+U_{102}+U_{103}+...+U_{200}=200

Berapakah nilai dari U_1?

Pembahasan

Dari rataan aritmatika kita ketahui bahwa :

\begin{array}{lllllr}&U_2&+&U_{100}&=&2.U_{51}\\&U_3&+&U_{99}&=&2.U_{51}\\dst...\\&U_{49}&+&U_{53}&=&2.U_{51}\\&U_{50}&+&U_{52}&=&2.U_{51}\end{array}

Selanjutnya, dengan menggabungkan konsep rataan aritmatika dan fakta pertama kita peroleh persamaan 1 :

\begin{array}{lllllllllll}U_1&+&U_2&+&U_3&+&...&+&U_{100}&=&100\\&&&&&&U_1&+&99.U_{51}&=&100\\&&&&&&a&+&99.(a+50d)&=&100\\&&&&&&a&+&99a+4950d&=&100\\&&&&&&&&100a+4950d&=&100\end{array}

Lalu kita peroleh persamaan 2 dari konsep rataan aritmatika dan fakta kedua :

\begin{array}{lllllllllll}U_{101}&+&U_{102}&+&U_{103}&+&...&+&U_{200}&=&200\\&&&&&&U_{101}&+&99.U_{151}&=&200\\&&&&&&(a+100d)&+&99.(a+150d)&=&200\\&&&&&&a+100d&+&99a+14850d&=&200\\&&&&&&&&100a+14950d&=&200\end{array}

Sekarang kita selesaikan persamaan 1 dan persamaan 2 :

\begin{array}{rlrllr}100a&+&14950d&=&200\\100a&+&4950d&=&100\\---&-&----&-&---&-\\&&10000d&=&100\\&&d&=&\frac{1}{100}\end{array}

Dari sini kita peroleh nilai d, yaitu d=\frac{1}{100}

Berikutnya nilai d kita substitusikan ke persamaan 1 untuk mencari nilai a. Ingat bahwa dalam deret aritmatika U_1=a.

\begin{array}{lllll}100a&+&4950d&=&100\\100a&+&4950.\frac{1}{100}&=&100\\100a&+&49,5&=&100\\&&100a&=&50,5\\&&a&=&0,505\end{array}

Obscene Math Phone Call

Oktober 20, 2010

Pertidaksamaan Garam

Filed under: Brain Teaser, Matematika, Pertidaksamaan — Hendra Jaya @ 5:16 am

wadah

Cerita

Wadah 1, dengan kapasitas b liter, diisi dengan garam sebanyak a sendok.
Wadah 2, dengan kapasitas d liter, diisi dengan garam sebanyak c sendok.
Kedua wadah terisi penuh dengan air lalu diaduk sehingga garam larut.

Kadar ke-asin-an air di wadah 1 dinyatakan dengan K_1=\frac{a}{b} dan ke-asin-an air di wadah 2 dinyatakan dengan K_2=\frac{c}{d}.
Keduanya dalam satuan yang sama, yaitu \frac{\text{sendok}}{\text{liter}}.

Asumsikan air di wadah 2 lebih asin air di wadah 2, yakni K_1<K_2.

Wadah 3, dengan kapasitas b+d liter, cukup untuk menampung air di wadah 1 dan wadah 2.

Air di wadah 1 dan di wadah 2 keduanya dituangkan ke wadah 3 lalu diaduk hingga rata. Sekarang, kita dapatkan konsentrat (kadar ke-asin-an) garam yang baru, yaitu K_3.

Pertanyaan

  1. Nyatakan konsentrat K_3 dalam variabel-variabel a, b, c dan d.
  2. Bagaimana relasi K_3 terhadap K_1 dan K_2?
  3. Carilah bilangan rasional \frac{a}{b} yang memenuhi \frac{1}{4}<\frac{a}{b}<\frac{1}{3} dengan syarat b<10. Tentu saja a,b\in\mathbb{Z}.
  4. Carilah bilangan rasional \frac{m}{n} yang memenuhi \frac{7}{10}<\frac{m}{n}<\frac{5}{7} dengan syarat n<20. Tentu saja m,n\in\mathbb{Z}.

Pembahasan

  1. Konsentrat yang baru K_3 berasal dari air sebanyak b+d liter dan garam sebanyak a+c sendok. Sehingga K_3=\frac{a+c}{b+d}.
  2. Secara intuitif, karena konsentrat 2 lebih asin dari konsentrat 1, yaitu K_1<K_2, maka konsentrat 3 (campuran) akan lebih asin dari konsentrat 1 tetapi kalah asin dari konsentrat 2. Secara matematis K_1<K_3<K_2.
    Jika kita tampilkan pertidaksamaan dalam bentuk a, b, c dan d akan kita peroleh \frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}.
    Perhatikan baik-baik pembilang dan penyebut dari setiap bagian pertidaksamaan. Menarik bukan?
  3. Bilangan rasional yang “diapit” oleh \frac{1}{4} dan \frac{1}{3} dapat dicari dengan cara menjumlahkan pembilang dan menjumlahkan penyebut.
    Sehingga \frac{a}{b}=\frac{1+1}{4+3}=\frac{2}{7}.
    Tentu saja pertidaksamaan \frac{1}{4}<\frac{2}{7}<\frac{1}{3} ini benar.
  4. Dengan cara yang sama, kita peroleh \frac{m}{n}=\frac{7+5}{10+7}=\frac{12}{17}.
    Tentu saja pertidaksamaan \frac{7}{10}<\frac{12}{17}<\frac{5}{7} valid.

Pertidaksamaan \frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d} berlaku umum dengan syarat a,b,c,d>0 dan a,b,c,d\in\mathbb{R}. Pembuktiannya diserahkan kepada pembaca. Selamat mencoba.

Sex Discrimination

Oktober 19, 2010

Faktor Persekutuan Terbesar (FPB) & Kelipatan Persekutuan Terkecil (KPK)

Filed under: Algoritma, Matematika, Teori Bilangan — Hendra Jaya @ 7:34 am

Faktor Persekutuan Terbesar

Faktor Persekutuan Terbesar (FPB) di dalam bahasa Inggris disebut dengan Greatest Common Divisor (GCD). Untuk membiasakan pembaca dengan istilah yang umum dipakai di dalam matematika, artikel ini akan menggunakan GCD alih-alih FPB.

Definisi : GCD dari dua buah bilangan bulat tidak nol a dan b adalah bilangan bulat positif terbesar d yang habis membagi baik a maupun b.
Secara matematis : gcd(a,b)=max\{d|a\text{ dan }d|b,d\in\mathbb{Z_+}\}
Secara komputatif : gcd(a,b)=d

Contoh 1 :
Faktor-faktor positif (positive divisors) dari 12 adalah : 1, 2, 3, 4, 6, 12
Faktor-faktor positif (positive divisors) dari 18 adalah : 1, 2, 3, 6, 9, 18
Faktor bersama (common divisors) dari 12 dan 18 adalah : 1, 2, 3, 6.
Faktor bersama yang paling besar (Greatest Common Divisor) dari 12 dan 18 adalah : 6.
gcd(12,18)=6
gcd(18,12)=6

Pada contoh di atas, 12 dan 18 memiliki beberapa faktor yang sama. Faktor-faktor tersebut adalah 1, 2, 3, dan 6. Dari ke-empat faktor bersama ini, tentu saja ada yang terbesar. Yang terbesar adalah 6. Faktor bersama yang terbesar inilah yang disebut dengan Greatest Common Divisor (GCD). Dalam contoh ini, dapat disimpulkan bahwa gcd(12,18)=6.

Contoh 2 :
Faktor-faktor positif (positive divisors) dari 15 adalah : 1, 3, 5, 15
Faktor-faktor positif (positive divisors) dari 20 adalah : 1, 2, 4, 5, 10, 20
Faktor bersama (common divisors) dari 15 dan 20 adalah : 1, 5
Faktor bersama yang paling besar (Greatest Common Divisor) dari 15 dan 20 adalah : 5.
gcd(15,20)=5
gcd(20,15)=5

Contoh 3 :
Faktor-faktor positif (positive divisors) dari 6 adalah : 1, 2, 3, 6
Faktor-faktor positif (positive divisors) dari 24 adalah : 1, 2, 3, 4, 6, 8, 12, 24
Faktor bersama (common divisors) dari 6 dan 24 adalah : 1, 2, 3, 6
Faktor bersama yang paling besar (Greatest Common Divisor) dari 6 dan 24 adalah : 6.
gcd(6,24)=6
gcd(24, 6)=6

Contoh 4 :
Faktor-faktor positif (positive divisors) dari 10 adalah : 1, 2, 5, 10
Faktor-faktor positif (positive divisors) dari 7 adalah : 1, 7
Faktor bersama (common divisors) dari 10 dan 7 adalah : 1
Faktor bersama yang paling besar (Greatest Common Divisor) dari 10 dan 7 adalah : 1.
gcd(10,7)=1
gcd(7,10)=1

Contoh 5 :
Faktor-faktor positif (positive divisors) dari 15 adalah : 1, 3, 5, 15
Faktor-faktor positif (positive divisors) dari 10 adalah : 1, 2, 5, 10
Faktor bersama (common divisors) dari 15 dan 10 adalah : 1, 5
Faktor bersama yang paling besar (Greatest Common Divisor) dari 15 dan 10 adalah : 5.
gcd(15,10)=5
gcd(10,15)=5

Contoh 6 :
Faktor-faktor positif (positive divisors) dari 4 adalah : 1, 2, 4
Faktor-faktor positif (positive divisors) dari 9 adalah : 1, 3, 9
Faktor bersama (common divisors) dari 4 dan 9 adalah : 1
Faktor bersama yang paling besar (Greatest Common Divisor) dari 4 dan 9 adalah : 1.
gcd(4,9)=1
gcd(9,4)=1

Intermezzo : Pada contoh ke-4 dan ke-6, GCD dari 10 dan 7 dan juga GCD dari 4 dan 9 adalah 1. Di dalam dunia matematika, jika GCD dari dua buah bilangan bulat a dan b bernilai 1 maka  kedua bilangan tersebut dikatakan relatif prima (relatively prime). Ada juga yang menyebutnya koprima (coprime). Blog ini menggunakan istilah koprima. Tentang “mengapa” matematikawan menggunakan istilah relatif prima/koprima, tentu ada sebabnya. Hal itu belum akan kita bahas di artikel ini. Sebagai gambaran saja, hal ini memang erat kaitannya dengan bilangan prima.

Dalam teori himpunan, a dan b dikatakan koprima jika himpunan faktor-faktor a dan himpunan faktor-faktor b saling lepas. Seperti pada gambar berikut :

coprime

Perhatikan bahwa GCD bersifat komutatif, yaitu gcd(a,b)=gcd(b,a). Penulis kira hal ini sudah cukup jelas, sehingga tidak perlu disediakan ruang khusus untuk membahasnya.

Teknik Menghitung GCD

Sebelum masuk ke dalam teknik menghitung GCD. Kita akan mundur sebentar ke dalam algoritma pembagian.

Misalkan gcd(a,b)=d. Sesuai dengan definisi, d pasti habis membagi a dan juga habis membagi b. Jika definisi ini kita tuangkan ke dalam algoritma pembagian, kita akan memperoleh :
a=x.d
b=y.d

Menurut algoritma pembagian, a dapat dituliskan sebagai a=q.b+r. Arti dari persamaan ini adalah “jika a dibagi dengan b, maka kita akan memperoleh sisa bagi (remainder) r yang memenuhi 0\leq r<|b|“.

Dengan men-substitusikan persamaan a=q.b+r, kita memperoleh q.b+r=x.d

Karena kita tahu bahwa b=y.d, kita substitusikan persamaan ini sehingga mendapatkan q.y.d+r=x.d

Tidak perlu diragukan lagi, sisi kanan dari persamaan, yaitu x.d, pasti habis dibagi dengan d. Begitu pula dengan q.y.d.

Lantas, apakah r pasti habis dibagi d? Karena “temannya” r, yaitu q.y.d sudah memberikan kepastian bahwa dia pasti habis dibagi oleh d, maka mau tidak mau r pasti habis juga dibagi d. Karena r habis dibagi oleh d, berarti d adalah divisor (faktor) dari r.

Bagaimana jika d tidak habis membagi r? Itu artinya d bukan gcd dari a dan b (kontradiktif). Habis perkara.

Di paragraf sebelumnya, secara logis kita telah menyimpulkan bahwa d adalah salah satu dari sekian banyak faktor (divisor) dari r. Pertanyaan logis berikutnya adalah “Faktor (divisor) yang mana?”. Lagi-lagi, karena kita bicara soal faktor terbesar (greatest divisor), jawabannya adalah “sebesar mungkin”.

Misalkan r memiliki sekian banyak faktor positif, sebut saja r_1,r_2,r_3,...r_n. Faktor mana yang akan kita pilih? Karena kita berusaha mencari “faktor terbesar yang mungkin”, kita akan lakukan pemeriksaan mulai dari yang paling kanan, yaitu r_n,r_{n-1},...r_3,r_2,r_1. Kita akan memeriksa apakah sebuah faktor, sebut saja r_i, habis membagi b.

Pemeriksaan berakhir jika r_i alias d terbukti habis membagi b.

Mengapa hanya b? Mengapa a tidak? Kita hanya memeriksa b karena itu sudah cukup (syarat cukup) untuk menjamin bahwa a juga pasti habis dibagi oleh d. Penjelasannya adalah sebagai berikut :

Perhatikan persamaan q.b+r=a.

Karena r_i adalah faktor dari r, maka kita boleh menulis persamaan di atas menjadi q.b+n.r_i=a. Tidak perlu pusing dengan variabel-variabel “dummy” seperti q dan n. Kita tidak tertarik untuk membahasnya.

Sekarang, jika r_i habis membagi b, maka persamaan dapat kita tulis ulang menjadi q.m.r_i+n.r_i=a. Sekali lagi, abaikan semua variabel-variabel tidak penting seperti q, m dan n.

Dengan memanfaatkan sifat distributif perkalian, kita memperoleh r_i.(q.m+n)=a.

Nah, sekarang jelas terlihat bahwa a juga pasti habis dibagi oleh r_i. Dengan demikian, pemeriksaan terhadap b sudah cukup (syarat cukup) untuk meyakinkan kita bahwa a tidak perlu diperiksa lagi.

Hal ini sangat menarik. Pemeriksaan yang kita lakukan di beberapa paragraf sebelumnya sebenarnya mencari faktor bersama (common divisor) yang habis membagi baik r, maupun b. Karena pemeriksaan dilakukan dari “kanan”, maka r_i yang memenuhi kriteria ini pastilah faktor bersama yang terbesar (greatest common divisor) yang dimiliki baik oleh r, maupun oleh b.

Apa yang sebenarnya kita lakukan di beberapa paragraf sebelumnya adalah mencari GCD dari r dan b. Aneh bukan? Memang benar bahwa di awal sekali, kita ingin mencari GCD dari a dan b. Tetapi, analisa matematika membuktikan bahwa GCD dari a dan b sebenarnya sama dengan GCD dari r dan b. Dimana r adalah sisa bagi a oleh b :

\begin{array}{ccl} gcd(a, b)& =& gcd(r, b) \\ gcd(a, b)& =& gcd(b, r) \\ gcd(a, b)& =& gcd(b, mod(a, b)) \end{array}

Fenomena ini pertama kali diamati oleh Euclid sekitar 2300 tahun yang lalu dan sampai saat ini masih dipelajari di sekolah-sekolah dan kampus-kampus di seluruh dunia.

Teknik pencarian GCD dari a dan b yang diajukan oleh Euclid adalah sebagai berikut :

  1. Jika b=0, maka GCD dari a dan b adalah a.
  2. Jika b\neq 0, maka :
    1. Carilah r, yaitu sisa bagi a oleh b.
    2. Anggap b sebagai a dan r sebagai b.
    3. Kembali ke step 1

Contoh 1 (lagi) : Menghitung gcd(12,18)

  • a = 12, b = 18.
  • Karena 18 \neq 0, maka :
  • 12 = 0.18 + 12, sehingga r = 12.
    • a = 18, b = 12
    • Karena 12 \neq 0, maka :
    • 18 = 1.12 + 6, sehingga r = 6
      • a = 12, b = 6
      • Karena 6 \neq 0, maka :
      • 12 = 2.6 + 0, sehingga r = 0
        • a = 6, b = 0
        • Karena 0 = 0, maka hasilnya adalah 6.

Secara grafis :

gcd

Contoh 2 (lagi) : Menghitung gcd(15, 20)

  • a = 15, b = 20.
  • Karena 20 \neq 0, maka :
  • 15 = 0.20 + 15, sehingga r = 15.
    • a = 20, b = 15
    • Karena 15 \neq 0, maka :
    • 20 = 1.15 + 5, sehingga r = 5
      • a = 15, b = 5
      • Karena 5 \neq 0, maka :
      • 15 = 3.5 + 0, sehingga r = 0
        • a = 5, b = 0
        • Karena 0 = 0, maka hasilnya adalah 5.

Secara grafis :

gcd

Contoh 3 (lagi) : Menghitung gcd(6, 24)

  • a = 6, b = 24.
  • Karena 24 \neq 0, maka :
  • 6 = 0.24 + 6, sehingga r = 6.
    • a = 24, b = 6
    • Karena 6 \neq 0, maka :
    • 24 = 4.6 + 0, sehingga r = 0
      • a = 6, b = 0
      • Karena 0 = 0, maka hasilnya adalah 6.

Secara grafis :

gcd

Contoh 4 (lagi) : Menghitung gcd(10, 7)

  • a = 10, b = 7.
  • Karena 7 \neq 0, maka :
  • 10 = 1.7 + 3, sehingga r = 3.
    • a = 7, b = 3
    • Karena 3 \neq 0, maka :
    • 7 = 2.3 + 1, sehingga r = 1
      • a = 3, b = 1
      • Karena 1 \neq 0, maka :
      • 3 = 3.1 + 0, sehingga r = 0
        • a = 1, b = 0
        • Karena 0 = 0, maka hasilnya adalah 1.

Secara grafis :

gcd

Contoh 5 (lagi) : Menghitung gcd(15, 10)

  • a = 15, b = 10.
  • Karena 10 \neq 0, maka :
  • 15 = 1.10 + 5, sehingga r = 5.
    • a = 10, b = 5
    • Karena 5 \neq 0, maka :
    • 10 = 2.5 + 0, sehingga r = 0
      • a = 5, b = 0
      • Karena 0 = 0, maka hasilnya adalah 5.

Secara grafis :

gcd

Contoh 6 (lagi) : Menghitung gcd(4, 9)

  • a = 4, b = 9.
  • Karena 9 \neq 0, maka :
  • 4 = 0.9 + 4, sehingga r = 4.
    • a = 9, b = 4
    • Karena 4 \neq 0, maka :
    • 9 = 2.4 + 1, sehingga r = 1
      • a = 4, b = 1
      • Karena 1 \neq 0, maka :
      • 4 = 4.1 + 0, sehingga r = 0
        • a = 1, b = 0
        • Karena 0 = 0, maka hasilnya adalah 1.

Secara grafis :

gcd

Better Luck Next Year

Satu pertanyaan yang paling sering dilontarkan adalah : “Mengapa b dianggap a dan r dianggap b?”.

Sebenarnya, teknik asli yang dilontarkan oleh Euclid mengharuskan a \geq b. Jika ternyata ditemukan bahwa a < b, maka Euclid mengharuskan kedua bilangan itu dipertukarkan. Ingat bahwa gcd adalah sebuah fungsi yang komutatif dimana gcd(a,b)=gcd(b,a) sehingga mempertukarkan posisi a dengan b tidak akan mengubah hasil perhitungan.

Akan tetapi, dengan majunya ilmu komputasi, “penganggapan” b sebagai a dan r sebagai b, terbukti lebih efisien karena kita tidak perlu pusing-pusing memeriksa apakah a \geq b.
Hal ini dapat dijelaskan melalui algoritma pembagian yang telah memberikan kepastian bahwa 0\leq r<|b|. Sehingga, step untuk memeriksa invarian (relasi) a\geq b tidak perlu dilakukan lagi.

Bagaimana jika salah satu atau keduanya dari a dan b adalah bilangan negatif?

Hal ini juga sangat sering ditanyakan. Pembahasan tentang pertanyaan ini akan kita tunda dulu. Pembahasan lengkapnya akan kita bahas di artikel “Sifat-sifat GCD dan LCM”. Ide utamanya adalah bilangan negatif merupakan suatu perkalian bilangan positif dengan -1.

Kelipatan Persekutuan Terkecil

Kelipatan Persekutuan Terkecil (KPK) di dalam bahasa Inggris dikenal dengan nama Least Common Multiple (LCM). Sama seperti GCD, blog ini akan membiasakan pembaca untuk menggunakan istilah yang lazim dipakai. Oleh karena itu blog ini akan menggunakan istilah LCM.

Definisi : LCM dari dua buah bilangan bulat a dan b adalah bilangan bulat positif terkecil yang merupakan kelipatan bersama dari a dan b.
Secara matematis : lcm(a,b)=\frac{|a.b|}{gcd(a, b)}
Secara komputatif : lcm(a, b)=\frac{abs(a.b)}{gcd(a, b)}
Catatan : definisi asli dari LCM menggunakan “bilangan rasional”. Artikel ini menyederhanakan definisi tersebut ke dalam “bilangan bulat” agar lebih mudah dipahami.

Contoh 1 :
Kelipatan (multiple) dari 12 adalah : 12, 24, 36, 48, 60, 72, 84, 96, 108, …
Kelipatan (multiple) dari 18 adalah : 18, 36, 54, 72, 90, 108, …
Kelipatan bersama (common multiple) dari 12 dan 18 adalah : 36, 72, 108, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 12 dan 18 adalah : 36.
lcm(12,18)=36
lcm(18,12)=36

Pada contoh di atas, 12 dan 18 memiliki banyak kelipatan yang sama. Kelipatan-kelipatan tersebut adalah 36, 72, 108, …. Dari semua kelipatan-kelipatan ini, yang terkecil adalah 36. Kelipatan bersama yang terkecil inilah yang disebut dengan Least Common Multiple (LCM). Dalam contoh ini, terlihat bahwa lcm(12,18)=36.

Contoh 2 :
Kelipatan (multiple) dari 15 adalah : 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, …
Kelipatan (multiple) dari 20 adalah : 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, …
Kelipatan bersama (common multiple) dari 15 dan 20 adalah : 60, 120, 180, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 15 dan 20 adalah : 60.
lcm(15,20)=60
lcm(20,15)=60

Contoh 3 :
Kelipatan (multiple) dari 6 adalah : 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, …
Kelipatan (multiple) dari 24 adalah : 24, 48, 72, 96, 120, 144, 168, 192, …
Kelipatan bersama (common multiple) dari 6 dan 24 adalah : 24, 48, 72, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 6 dan 24 adalah : 24.
lcm(6,24)=24
lcm(24,6)=24

Contoh 4 :
Kelipatan (multiple) dari 10 adalah : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 160, 170, 180, 190, 200, 210, …
Kelipatan (multiple) dari 7 adalah : 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 126, 133, 140, 147, …
Kelipatan bersama (common multiple) dari 10 dan 7 adalah : 70, 140, 210, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 10 dan 7 adalah : 70.
lcm(10,7)=70
lcm(7,10)=70

Contoh 5 :
Kelipatan (multiple) dari 15 adalah : 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, …
Kelipatan (multiple) dari 10 adalah : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, …
Kelipatan bersama (common multiple) dari 15 dan 10 adalah : 30, 60, 90, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 15 dan 10 adalah : 30.
lcm(15,10)=30
lcm(10,15)=30

Contoh 6 :
Kelipatan (multiple) dari 4 adalah : 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, …
Kelipatan (multiple) dari 9 adalah : 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, …
Kelipatan bersama (common multiple) dari 4 dan 9 adalah : 36, 72, 108, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 4 dan 9 adalah : 36.
lcm(4,9)=36
lcm(9,4)=36

Sama seperti GCD, LCM juga bersifat komutatif (dapat dipertukarkan tanpa mengurangi kebenarannya). Yaitu lcm(a,b)=lcm(b,a).

Secara matematis, untuk menghitung LCM dari dua buah bilangan bulat a dan b dapat dilakukan dengan mengikuti rumus lcm(a,b)=\frac{|a.b|}{gcd(a,b)}
Hal ini sangat mudah dilakukan karena sebelumnya kita telah mengetahui teknik pencarian gcd(a,b) ala Euclid.

Secara komputatif, untuk menghitung LCM dilakukan dengan invarian lcm(a,b)=\frac{abs(a.b)}{gcd(a,b)}

Contoh 1 (lagi) :
lcm(12,18)=\frac{|12.18|}{gcd(12,18)}=\frac{216}{6}=36

Contoh 2 (lagi) :
lcm(15,20)=\frac{|15.20|}{gcd(15,20)}=\frac{300}{5}=60

Contoh 3 (lagi) :
lcm(6,24)=\frac{|6.24|}{gcd(6,24)}=\frac{144}{6}=24

Contoh 4 (lagi) :
lcm(10,7)=\frac{|10.7|}{gcd(10,7)}=\frac{70}{1}=70

Contoh 5 (lagi) :
lcm(15,10)=\frac{|15.10|}{gcd(15,10)}=\frac{150}{5}=30

Contoh 6 (lagi) :
lcm(4,9)=\frac{|4.9|}{gcd(4,9)}=\frac{36}{1}=36

Sebenarnya penulis tidak terlalu tertarik untuk membahas asal muasal datangnya rumus LCM ini. Tetapi, untuk mengantisipasi keingintahuan pembaca. Berikut akan dipaparkan asal muasal rumus LCM.

Misalkan gcd(a,b)=d dan lcm(a,b)=e.
Maka a dan b bisa ditulis ulang menjadi :

a=x.d

b=y.d

gcd(x,y)=1

Intermezzo : Mengapa gcd(x,y)=1?
Untuk menjawabnya, penulis akan membuktikan dengan metode kontradiktif. Asumsikan gcd(x,y)=n, dimana n>1. Sehingga :

x=t.n

y=u.n

akibatnya,

a=x.d=t.n.d

b=y.d=u.n.d

dan dengan demikian, gcd(a,b)=n.d

Kalimat di atas secara langsung mengatakan bahwa GCD dari a dan b bukanlah d, melainkan n.d. Dimana n.d>d karena n>1.
Suatu kontradiktif yang mengakibatkan asumsi kita salah.

Dengan demikian gcd(x,y) haruslah 1. Dalam diagram venn dinyatakan sebagai himpunan yang saling lepas.

Sekarang kita lanjutkan ke pembahasan asal muasal rumus LCM…

Nilai e terkecil yang habis membagi x.d dan y.d adalah x.y.d. Mengapa x.y.d? Sukar untuk dijelaskan dengan kata-kata. Biarkan diagram venn di bawah ini yang berbicara 😀

x adalah yang berwarna cyan (telor asin)

d adalah yang berwarna pink (merah jambu)

y adalah yang berwarna purple (ungu)

lcm

Nilai e setidak-tidaknya harus dapat membagi x, y, dan d. Sehingga e haruslah merupakan perkalian ketiganya, yaitu x.y.d

\begin{array}{lll}lcm(a,b)&=&x.y.d\\&=&\frac{x.y.d^2}{d}\\&=&\frac{x.d.y.d}{gcd(a,b)}\\&=&\frac{a.b}{gcd(a,b)}\end{array}

Mengingat lcm(a,b) adalah bilangan bulat positif, maka sisi kanan haruslah positif juga.

Karena penyebut dari sisi kanan, yaitu gcd(a,b), pasti bilangan positif, maka ke-positif-an pembilangnya harus dipastikan dengan fungsi abs(x).

\therefore lcm(a,b)=\frac{abs(a.b)}{gcd(a,b)}

Obat Ngantuk

  1. BintangBintang Rancanglah algoritma untuk mencari GCD dari himpunan bilangan bulat S={a,b,c,d,...}, dimana |S|\geq 2.
    Notasi |S| menyatakan kardinalitas (jumlah elemen) dari himpunan.
  2. BintangBintang Rancanglah algoritma untuk mencari LCM dari himpunan bilangan bulat S={a,b,c,d,...}, dimana |S|\geq 2.
    Notasi |S| menyatakan kardinalitas (jumlah elemen) dari himpunan.

You Don't Trust Management

Menghitung Digit

Filed under: Matematika, Puzzle — Hendra Jaya @ 5:26 am

Problem

Bilangan 2^{123456} adalah bilangan yang sangat besar. Berapa digit-kah panjang bilangan ini?

Pra-pembahasan 1 (Penyederhanaan Bentuk)

Misalkan \overline{abcd} adalah sebuah bilangan 4 digit. Maka berlaku pertidaksamaan berikut

\begin{array}{rllll}1000&\leq&\overline{abcd}&\leq&9999\\1000&\leq&\overline{abcd}&<&10000\\10^3&\leq&\overline{abcd}&<&10^4\end{array}

Atau secara umum, jika \overline{NUMBER} adalah bilangan n digit, maka berlaku 10^{n-1}\leq\overline{NUMBER}<10^n dimana n\geq 1\text{, }n\in \mathbb{Z}

Lebih jauh lagi, karena kita tahu bahwa log(x) adalah sebuah fungsi yang monoton naik, maka berlaku :

\begin{array}{rlllrllll}&&10^{n-1}&\leq&\overline{NUMBER}&<&10^n\\&&log(10^{n-1})&\leq&log(\overline{NUMBER})&<&log(10^n)\\(n-1)&.&log(10)&\leq&log(\overline{NUMBER})&<&n&.&log(10)\\(n-1)&.&1&\leq&log(\overline{NUMBER})&<&n&.&1\\&&n-1&\leq&log(\overline{NUMBER})&<&n\end{array}

Pra-Pembahasan 2 : (Fungsi Lain yang Serupa)

Kita tahu ada sebuah fungsi yang definisi-nya persis dengan pertidaksamaan di atas, yaitu fungsi floor(x)

Definisi : floor(x) di-definisikan sebagai \lfloor x\rfloor=m\leftrightarrow m\leq x<m+1

Atau jika dimodifikasi sedikit dengan melakukan operasi pengurangan, definisi menjadi \lfloor x-1\rfloor=m-1\leftrightarrow m-1\leq x-1<m

Jika kita misalkan x-1=\overline{NUMBER}.

Maka kita peroleh : \lfloor log(\overline{NUMBER})\rfloor=n-1\leftrightarrow n-1\leq log(\overline{NUMBER})<n

Atau sederhananya \lfloor log(\overline{NUMBER})\rfloor=n-1

Pembahasan

Diketahui : \overline{NUMBER}=2^{123456}

Ditanya : n

Jawab :

\begin{array}{rll}n-1&=&\lfloor log(2^{123456})\rfloor\\&=&\lfloor 123456.log(2)\rfloor\\&=&\lfloor 123456.(0.30102999)\rfloor\\&=&\lfloor 37163.95914469\rfloor\\n-1&=&37163\\n&=&37164\end{array}

Untuk mengatasi rasa tidak percaya dari pembaca yang kurang “beriman” terhadap logika dan matematika, berikut ini penulis sediakan hasil perhitungan yang sebenarnya dari 2^{123456}. Silahkan hitung sendiri banyaknya digit pada angka tersebut. Pelan-pelan saja, tidak usah terburu-buru :)

Memorizing PI

Oktober 18, 2010

Obat Ngantuk Konsep Modulus 1

Filed under: Matematika, Puzzle, Teori Bilangan — Hendra Jaya @ 5:29 am

Problem

Buktikan bahwa {2222}^{5555}+{5555}^{2222} habis dibagi 7.

Sumber : Seleksi Tim Olimpiade Matematika Indonesia 1997

Pra-Pembahasan 1

Menurut algoritma pembagian, a=d.q+r dengan 0\leq r<|d|
Jika kita nyatakan sisa pembagian a oleh d sebagai mod(a,d) maka r=mod(a,d)

Salah satu sifat dalam fungsi mod(a, d) adalah sifat distributif-asosiatif, sebagai berikut:

\begin{array}{clllclcr}a&=&d&.&q_1&+&r_1\\b&=&d&.&q_2&+&r_2\\---&-&-&-&----&-&----&+\\a+b&=&d&.&(q_1+q_2)&+&(r_1+r_2)\end{array}

Karena r_1+r_2 mungkin lebih besar dari d, maka :

r_1+r_2=d.q_3+r_3

Sehingga

\begin{array}{lllllll}a+b&=&d&.&(q_1+q_2)&+&(r_1+r_2)\\a+b&=&d&.&(q_1+q_2)&+&d.q_3+r_3\\a+b&=&d&.&(q_1+q_2+q_3)&+&r_3\end{array}

Sekarang, karena

r_1=mod(a,d)
r_2=mod(b,d)
r_3=mod(a+b,d) dan
r_3=mod(r_1+r_2,d)

Maka mod(a+b,d)=mod(mod(a,d)+mod(b,d), d)
Dengan cara yang sama juga kita peroleh mod(a.b,d)=mod(mod(a,d).mod(b,d), d).

Perhatikan bahwa dalam algoritma pembagian, a dikatakan habis dibagi oleh d jika dan hanya jika r=0 atau mod(a,d)=0.

Pra-Pembahasan 2

Menurut Binomial Newton :

\begin{array}{lll}a&=&d.q+r\\a^b&=&(d.q+r)^b\\a^b&=&k_0.d^b.q^b.r^0+k_1.d^{b-1}.q^{b-1}.r^1+k_2.d^{b-2}.q^{b-2}.r^2+...+k_{b-2}.d^2.q^2.r^{b-2}+k_{b-1}.d^1.q^1.r^{b-1}.q+k_b.d^0.q^0.r^b\\a^b&=&k_0.d^b.q^b.r^0+k_1.d^{b-1}.q^{b-1}.r^1+k_2.d^{b-2}.q^{b-2}.r^2+...+k_{b-2}.d^2.q^2.r^{b-2}+k_{b-1}.d^1.q^1.r^{b-1}.q+k_b.r^b\end{array}

Semua suku, kecuali suku ke-b (terakhir), memiliki d sebagai faktor.
Ini memberikan kita kesimpulan bahwa semua suku, kecuali suku ke-b, habis dibagi oleh d.

Karena semua suku, kecuali suku ke-b, habis dibagi oleh d, maka sisa pembagian a^b oleh d bergantung sepenuhnya kepada suku ke-b.

Nilai dari suku ke-b adalah :

\begin{array}{llll}U(b)&=&k_b.r^b\\U(b)&=&C(b,b).r^b\\U(b)&=&1.r^b\\U(b)&=&r^b\end{array}

Dengan demikian sisa bagi a^b oleh d bergantung sepenuhnya kepada r^b dimana r adalah sisa bagi a oleh d. Secara matematis :

\begin{array}{lllclllr}a&=&d.q_1+r&\text{ alias }&a&\equiv&r&\text{(modulo d)}\\a^b&=&d.q_2+r^b&\text{ alias }&a^b&\equiv&r^b&\text{(modulo d)}\end{array}

Pembahasan

Sisa bagi {2222}^{5555}+{5555}^{2222} oleh 7 dapat dinyatakan sebagai :

mod({2222}^{5555}+{5555}^{2222},7)=mod(mod({2222}^{5555},7)+mod({5555}^{2222},7),7)

Bagian 1 : Mencari nilai mod({2222}^{5555},7) :

Karena

{2222}^{5555}={(7.317+3)}^{5555}

Maka

mod({2222}^{5555},7)=mod({3}^{5555},7)

Karena

\begin{array}{lll}{3}^{5555}&=&3.{3}^{5554}\\&=&3.{(3^2)}^{2777}\\&=&3.{9}^{2777}\\&=&3.{(7.1+2)}^{2777}\end{array}

Maka

mod({3}^{5555},7)=mod(3.mod({2}^{2777},7),7)

Karena

\begin{array}{lll}{2}^{2777}&=&{2}^{2}.{2}^{2775}\\&=&4.{(2^3)}^{925}\\&=&4.{(2^3)}^{925}\\&=&4.{8}^{925}\\&=&4.{(7.1+1)}^{925}\end{array}

Maka

\begin{array}{lll}mod({2}^{2777},7)&=&mod(4.mod({1}^{925},7),7)\\&=&mod(4.mod(1,7),7)\\&=&mod(4.1,7)\\&=&mod(4,7))\\&=&4\end{array}

Sehingga

\begin{array}{lll}mod({3}^{5555},7)&=&mod(3.mod({2}^{2777},7),7)\\&=&mod(3.4,7)\\&=&mod(12,7)\\&=&5\end{array}

Sehingga

\begin{array}{lll}mod({2222}^{5555},7)&=&mod({3}^{5555},7)\\&=&5\end{array}

Bagian 2 : Mencari nilai mod({5555}^{2222},7) :

Karena

{5555}^{2222}={(7.793+4)}^{2222}

maka

mod({5555}^{2222},7)=mod({4}^{2222},7)

Karena

\begin{array}{lll}{4}^{2222}&=&4^2.{4}^{2220}\\&=&16.{(4^3)}^{740}\\&=&16.{64}^{740}\\&=&16.{(7.9+1)}^{740}\end{array}

maka

\begin{array}{lll}mod({4}^{2222},7)&=&mod(16.mod({1}^{740},7),7)\\&=&mod(16.mod(1,7),7)\\&=&mod(16.1,7)\\&=&mod(16,7)\\&=&2\end{array}

Sehingga

\begin{array}{lll}mod({5555}^{2222},7)&=&mod({4}^{2222},7)\\&=&2\end{array}

Kesimpulan

\begin{array}{lll}mod({2222}^{5555}+{5555}^{2222},7)&=&mod(mod({2222}^{5555},7)+mod({5555}^{2222},7),7)\\&=&mod(5+2,7)\\&=&mod(7,7)\\&=&0\end{array}

Dengan demikian sisa bagi dari {2222}^{5555}+{5555}^{2222} oleh 7 adalah 0. Alias {2222}^{5555}+{5555}^{2222} habis dibagi oleh 7.

Mathematician Steroids

Older Posts »

Blog di WordPress.com.