Catatan si Jay

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

Iklan

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

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 19, 2010

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

Oktober 16, 2010

FORTY + TEN + TEN = SIXTY

Filed under: Puzzle — Hendra Jaya @ 9:12 am

Problem :

\begin{array}{lllllr}F&O&R&T&Y\\&&T&E&N\\&&T&E&N\\-&-&-&-&-&+\\S&I&X&T&Y\end{array}

Curahan Hati :

Penulis berusaha sebisa mungkin untuk menghindari penggunaan programming ketika menyelesaikan teka-teki ini. Untuk itu penulis memanfaatkan sebesar-besarnya teknik pertidaksamaan dan teori bilangan, khususnya algoritma pembagian dan kekongruenan bilangan. Penulis mengasumsikan pembaca sudah cukup paham mengenai pertidaksamaan. Jika pembaca menemui kesulitan dalam algoritma pembagian ataupun kekongruenan bilangan, penulis menyarankan untuk membaca tulisan tentang algoritma pembagian dan kekongruenan bilangan terlebih dahulu.

Pra-pembahasan :

Secara umum, di dalam setiap variabel berlaku pertidaksamaan 0\leq A\leq 9.

Jika kita asumsikan A<B maka berlaku pertidaksamaan 0\leq A<B\leq 9. Pertidaksamaan ini dapat dipecah menjadi 0\leq A\leq 8 dan 1\leq B\leq 9. Akibatnya nilai A+B akan berada di rentang 1\leq A+B\leq 17.

Sekarang, karena A<B, maka :

\begin{array}{rlrllll}&&A&<&B\\(A+B)&+&A&<&B&+&(A+B)\\2A&+&B&<&2B&+&A\\2A&+&B&<&A&+&2B\end{array}

Nilai 2A+B berada di rentang 1\leq 2A+B\leq 25.
Nilai A+2B berada di rentang 2\leq A+2B\leq 26.

Jika kita lupakan asumsi awal A<B, maka nilai A+2B akan berada di rentang 1\leq A+2B\leq 26.
Perhatikan bahwa persamaan A+2B=1 hanya mungkin terjadi jika B<A.
Sebaliknya, persamaan A+2B=26 hanya mungkin terjadi jika A<B.

Dengan demikian carry yang mungkin dihasilkan oleh bentuk A+2B adalah C=\{0,1,2\}

Pembahasan

Sekarang, perhatikan bahwa Y kongruen dengan Y+2N dalam modulo 10. Secara matematis : Y\equiv Y+2N\text{(modulo 10)}

Dengan memanfaatkan sifat :

\begin{array}{lrlll}&a&\equiv& b&\text{(modulo\ n)}\\&p&\equiv& q&\text{(modulo\ n)}\\\rightarrow&a+p&\equiv& b+q&\text{(modulo\ n)}\end{array}

Kita peroleh 0\equiv 2N\text{(modulo\ 10)} atau jika dinyatakan dalam algoritma pembagian menjadi 2N = 10.p

Mengingat 0\leq N\leq 9 dan 0\leq 2N\leq 18 maka himpunan nilai yang mungkin untuk p adalah P=\{0,1\}. Alhasil, nilai 2N yang mungkin adalah \{0,10\}. Sehingga himpunan nilai yang mungkin untuk N adalah \{0,5\}. Lebih jauh lagi, duplet yang memungkinkan untuk N dan carry adalah <N, carry>=\{<0, 0>,<5,1>\}

Selanjutnya, berlaku pula kekongruenan T\equiv carry+T+2E\text{(modulo\ 10)} yang mengakibatkan 0\equiv carry+2E\text{(modulo\ 10)}. Atau jika dinyatakan dalam algoritma pembagian menjadi carry + 2E = 10.q.

Perhatikan bahwa sisi kanan dari persamaan adalah genap. Dengan demikian, sisi kiri juga harus genap. Karena bentuk 2E adalah genap, maka genap atau ganjilnya sisi kiri hanya tergantung kepada carry. Fakta ini memaksa kita untuk meng-eliminasi duplet <5, 1>. Kabar yang baik tentunya. Karena dengan demikian kita bisa memastikan bahwa N=0 dan tidak ada carry yang dibawa.

\begin{array}{lllllr}F&O&R&T&Y\\&&T&E&0\\&&T&E&0\\-&-&-&-&-&+\\S&I&X&T&Y\end{array}

Sebelumnya sudah dibahas bahwa carry + 2E = 10.q dan 0\equiv carry+2E\text{(modulo\ 10)}. Dengan men-substitusikan nilai 0 ke dalam carry kita peroleh 2E = 10.q dan 0\equiv 2E\text{(modulo\ 10)}.

Berapa nilai E yang mungkin? Alih-alih “tembak langsung” ke nilai E, kita akan berputar melalui senjata awal kita, yaitu pertidaksamaan dan kekongruenan bilangan.

Seperti yang sudah-sudah, nilai 2E berada di rentang 0\leq 2E\leq 18. Di rentang ini, hanya ada dua buah nilai yang kongruen dengan 0 dalam modulo 10, yaitu 0 dan 10. Kedua nilai ini membantu kita untuk menyimpulkan bahwa nilai yang mungkin untuk E adalah \{0, 5\}. Mengingat 0 sudah dipakai, maka nilai E yang mungkin hanyalah \{5\} dan dengan demikian kita peroleh E=5 dan q=1.

\begin{array}{lllllr}&&1&&\\F&O&R&T&Y\\&&T&5&0\\&&T&5&0\\-&-&-&-&-&+\\S&I&X&T&Y\end{array}

Seperti sudah dibahas pada pra-pembahasan bahwa 0\leq A+B\leq 17, kita dapat menarik kesimpulan bahwa penjumlahan dua buah variabel yang berbeda akan menghasilkan carry 0 ataupun carry 1.

Sebagai konsekuensinya, penjumlahan O dan I pun dapat menghasilkan carry 0 ataupun carry 1. Jika tidak menghasilkan carry (yakni carry 0), akan mengakibatkan F=S yang tentu saja tidak valid karena F dan S adalah dua buah variabel yang berbeda

Dengan demikian penjumlahan O dan I pasti memberikan carry 1. Sehingga berlaku persamaan F+1=S

\begin{array}{lllllr}1&&1&&\\F&O&R&T&Y\\&&T&5&0\\&&T&5&0\\-&-&-&-&-&+\\S&I&X&T&Y\end{array}

Selanjutnya, kita akan coba “taklukkan” variabel O dan I.

Pada pra-pembahasan sudah dibahas bahwa bentuk A + 2B berada di rentang 1\leq A+2B\leq 26 atau dengan menambahkan 1 kepada setiap bagian pertidaksamaan kita peroleh 2\leq 1+A+2B\leq 27. Fakta ini menolong kita untuk “menebak” carry yang mungkin dibawa pada nilai 1+R+2T.

Saat ini, kita hanya bisa menyimpulkan bahwa carry yang mungkin dibawa pada penjumlahan 1+R+2T adalah C = \{0,1,2\}.

  1. Jika carry=0, maka :

    \begin{array}{lllllll}0&+&O&=&10&+&I\\&&O&=&10&+&I\end{array}.

    Persamaan di atas menyatakan bahwa O kongruen dengan I dalam modulo 10, secara matematis O\equiv I(modulo\ n). Hal ini tidak bisa kita terima karena artinya variabel O “kembar” dengan variabel I.

  2. Jika carry=1, maka :

    \begin{array}{lllllll}1&+&O&=&10&+&I\\&&O&=&9&+&I\end{array}

    (Lagi-lagi) Pertidaksamaan akan kita gunakan untuk memeriksa :

    \begin{array}{llrl}0&\leq&O\leq&9 \\ 0& \leq&9+I\leq&9\\-9&\leq&I\leq&0\end{array}

    Pertidaksamaan berhasil membantu kita “mempersempit” kemungkinan dan menyimpulkan bahwa nilai I yang mungkin adalah I=0. Mengingat 0 sudah dipakai, maka kasus ini pun tidak bisa kita terima

  3. Jika carry=2, maka :

    \begin{array}{lllllll}2&+&O&=&10&+&I\\&&O&=&8&+&I\end{array}

    Biarkan pertidaksamaan beraksi :

    \begin{array}{llrl}0&\leq&O\leq&9 \\ 0& \leq &8+I\leq&9\\-8&\leq&I\leq&1\end{array}

    Akhirnya. Kasus carry=2 memberikan hasil yang dapat diterima, yaitu I=1. Dengan demikian variabel O pun dapat dipecahkan, yaitu O=9.

Dari sini, kita peroleh :

\begin{array}{lllllr}1&2&1&&\\F&9&R&T&Y\\&&T&5&0\\&&T&5&0\\-&-&-&-&-&+\\S&1&X&T&Y\end{array}

Kesimpulan carry=2 dan O=9 ini sangat mempermudah kita untuk memecahkan variabel T. Mari kita bergerak dengan pertidaksamaan (lagi…)

Karena nilai 9 sudah diambil oleh O, maka berlaku B\leq 8
Karena nilai 8 sudah diambil oleh B, maka berlaku A\leq 7
Kedua premis di atas membawa kita kepada A+2B\leq 23 atau, dengan menambahkan 1 pada kedua sisi, kita peroleh 1+A+2B\leq 24

Bagaimana dengan batas bawah (lower bound) dari nilai 1+R+2T? Karena sebelumnya sudah kita pastikan bahwa nilai 1+R+2T akan menelurkan carry=2, maka batas bawah untuk nilai 1+R+2T adalah 20. Secara matematis 20\leq 1+R+2T\leq 24.

Ingat bahwa X kongruen dengan 1+R+2T di dalam modulo 10. Dengan mengambil pertidaksamaan 20\leq 1+R+2T\leq 24, secara implisit kita menyatakan bahwa 0\leq X\leq 4. Rentang nilai X sebenarnya dapat kita persempit dengan mengingat bahwa 0 dan 1 sudah tidak bisa dipakai. Sehingga rentang nilai yang lebih tepat untuk X adalah 2\leq X\leq 4

Rentang nilai X yang sudah dipersempit itu meng-implikasikan bahwa rentang nilai 1+R+2T pun dapat dipersempit menjadi 22\leq 1+R+2T\leq 24. Atau jika disederhanakan menjadi 21\leq R+2T\leq 23

Sekarang, karena nilai 0, 1, 5 dan 9 sudah tidak bisa dipakai, maka berlaku 2\leq R\leq 8 dimana R\neq 5.
Secara komputatif, min(R) = 2 dan max(R) = 8.

Mari kita lihat apa yang akan terjadi kepada pertidaksamaan jika kita mengambil nilai R minimum dan maksimum

  • Untuk R minimum, yaitu R=2 :

    \begin{array}{llrll}21&\leq&R+2T&\leq&23\\21&\leq&2+2T&\leq&23\\19&\leq&2T&\leq&21\end{array}

  • Untuk R maximum, yaitu R=8 :

    \begin{array}{llrll}21&\leq&R+2T&\leq&23\\21&\leq&8+2T&\leq&23\\13&\leq&2T&\leq&15\end{array}

Dari sini dapat disimpulkan bahwa 2T berada di rentang 13\leq 2T\leq 21.

Dengan hanya memandang bilangan-bilangan genap kita pertajam sedikit pertidaksamaannya menjadi 14\leq 2T\leq 20. Selanjutnya pertidaksamaan dapat disederhanakan menjadi 7\leq T\leq 10. Mengingat nilai 9 dan 10 tidak bisa dipakai, pertidaksamaan dapat dipertajam lagi menjadi 7\leq T\leq 8.

Pertidaksamaan ini sangat menolong kita untuk menyimpulkan bahwa himpunan nilai yang mungkin untuk T adalah \{7,8\}.

Berikutnya kita akan periksa setiap kasus untuk T.

  1. Untuk T=7 :

    \begin{array}{lllllr}21&\leq&R+2T&\leq&23\\21&\leq&R+14&\leq&23\\7&\leq&R&\leq&9\\7&\leq&R&\leq&8&\text{Angka 9 sudah tidak bisa dipakai}\end{array}

    Karena T=7, maka nilai yang mungkin untuk R hanyalah 8.

    Jika kedua nilai ini kita substitusikan, kita peroleh 1+R+2T=21. Nilai ini akan menyebabkan X=1 yang tidak valid karena 1 sudah dipakai. Hal ini termaktub dalam pertidaksamaan. Ingat bahwa tadi kita sudah mempersempit rentang X menjadi 2\leq X\leq 4

  2. Untuk T=8 :

    \begin{array}{lllllr}21&\leq&R+2T&\leq&23\\21&\leq&R+16&\leq&23\\5&\leq&R&\leq&7\\6&\leq&R&\leq&7&\text{Angka 5 sudah tidak bisa dipakai}\end{array}

    Dua nilai yang memungkinkan untuk R adalah \{6,7\}.

    1. Untuk R=6 kita peroleh 1+R+2T=23. Artinya X=3. Logis.
    2. Untuk R=7 kita peroleh 1+R+2T=24. Artinya X=4. Logis.

Saat ini, kita punya dua triplet yang mungkin untuk <R,T,X>, yaitu \{<6,8,3>,<7,8,4>\}

  1. Triplet <6,8,3> :

    \begin{array}{lllllr}1&2&1&&\\F&9&6&8&Y\\&&8&5&0\\&&8&5&0\\-&-&-&-&-&+\\S&1&3&8&Y\end{array}

    Triplet ini menyisakan tiga bilangan yang belum dipakai, yaitu \{2,4,7\}. Sayangnya, ketiga nilai yang tersisa ini tidak ada yang dapat dipergunakan untuk memenuhi persamaan F+1=S. Sehingga triplet ini gagal memberikan solusi.

  2. Triplet <7,8,4> :

    \begin{array}{lllllr}1&2&1&&\\F&9&7&8&Y\\&&8&5&0\\&&8&5&0\\-&-&-&-&-&+\\S&1&4&8&Y\end{array}

    Triplet ini menyisakan tiga bilangan yang belum dipakai, yaitu \{2,3,6\}. Nilai yang “masuk” untuk persamaan F+1=S adalah 2+1=3. Dengan demikian triplet ini memberikan solusi dimana F=2, S=3 dan Y=6.

Hasil akhir untuk alphamatic ini adalah :

\begin{array}{lllllr}1&2&1&&\\2&9&7&8&6\\&&8&5&0\\&&8&5&0\\-&-&-&-&-&+\\3&1&4&8&6\end{array}

Yaitu N = 0, I = 1, F = 2, S = 3, X = 4, E = 5, Y = 6, R = 7, T = 8, O = 9

Yesterday x=3

Oktober 13, 2010

Diophantine Sangat Sederhana Sekali

Filed under: Matematika, Puzzle — Hendra Jaya @ 8:12 am

Soal

Tunjukkan bahwa persamaan x^2 - y^2 = a^3 selalu memiliki solusi bilangan bulat x dan y untuk sembarang bilangan bulat positif a. Sebagai contoh, untuk a = 5 kita menemukan solusi x = 15 dan y = 10 yang memenuhi persamaan di atas.

Pembahasan

Kita jabarkan persamaan ini menjadi :

\begin{array}{cccllll} x^2& -& y^2& =& a^3 \\ (x-y)& .& (x+y)& =& a^3 \\ (x-y)& .& (x+y)& =& a& .& a^2 \end{array}

Asumsikan x - y = a sehingga x + y = a^2

Catatan 1 : Ada masukan dari seorang teman bahwa terdapat missing link di sekitar sini. Masukan yang sangat berharga tentunya. Missing link yang dimaksud adalah sebagai berikut :
Untuk setiap bilangan bulat positif n, kita memiliki sejumlah faktor/divisor dari bilangan tersebut. Secara matematis dikatakan himpunan bilangan bulat positif yang merupakan faktor dari n adalah N=\{n_1,n_2,n_3,...,n_k\}.
Sebagai contoh himpunan bilangan bulat positif yang merupaka faktor dari 12 adalah N=\{1,2,3,4,6,12\}.
Kita tidak bisa tahu secara lengkap apa saja faktor-faktor dari a^3, dimana a adalah bilangan bulat positif. Tetapi kita yakin bahwa \{1,a,a^2,a^3\} adalah sebagian dari faktor-faktor tersebut (himpunan bagian dari N).

Asumsi ini boleh dilakukan karena setiap bilangan bulat positif a (tentu saja) dapat dibentuk dari hasil pengurangan dua buah bilangan bulat yang lain, yaitu x dan y. Sekarang kita akan mencari tahu apakah mungkin penjumlahan x dan y menghasilkan nilai a^2. Jika tidak mungkin, di dalam penjabaran kita akan menemukan sesuatu yang kontradiktif. Jika penjabaran tidak menemukan sesuatu yang kontradiktif, maka asumsi kita berlaku.

\begin{array}{llllcr} x& -& y& =& a \\ x& +& y& =& a^2 \\ -& -& -& -& ---& + \\ & & 2x& =& a^2 + a \\ & & 2x& =& a(a + 1) \\ & & x& =& \frac{a(a + 1)}{2} \end{array}

Sekarang, apakah x adalah bilangan bulat? Mari kita periksa pembilang dan penyebut dari sisi kanan persamaan. Kita tahu pasti bahwa a adalah bilangan bulat positif sehingga a + 1 juga merupakan bilangan bulat positif. Dengan demikian pembilang adalah bilangan bulat positif dan penyebut (yaitu 2, jelas sekali) adalah bilangan bulat positif. Tetapi, apakah penyebut habis membagi pembilang? Sebenarnya, salah satu dari dua buah bilangan bulat yang berturutan seperti a dan a + 1 pasti merupakan bilangan genap dan lainnya ganjil. Sebagai contoh, 5 dan 6 adalah ganjil dan genap. Contoh lainnya adalah 6 dan 7, yaitu genap dan ganjil. Penjelasan secara matematisnya adalah dengan berdasarkan algoritma pembagian dan modulo sebagai berikut :

Misalkan a adalah ganjil, dalam bentuk a = 2p + 1. Dengan demikian kita peroleh a + 1 adalah bilangan genap melalui penjabaran berikut :

\begin{array}{lllll} a& & & =& 2p + 1 \\ a& +& 1& =& 2p + 1 + 1 \\ a& +& 1& =& 2p + 2 \\ a& +& 1& =& 2(p + 1) \end{array}.

Perkalian dari a dan a + 1 dapat dinyatakan sebagai :

\begin{array}{cll} a.(a+1)& =& (2p + 1).2(p + 1)\\ a.(a+1)& =& 2.(2p + 1)(p + 1)\\ \frac{a.(a+1)}{2}& =& (2p + 1)(p + 1) \end{array}

Dengan demikian perkalian dari a dan a + 1 pasti habis dibagi oleh 2.

Sebaliknya jika a adalah genap, maka a + 1 ganjil. Tidak perlu dijabarkan lagi. Pasti perkalian a dan a + 1 habis dibagi oleh 2.

Karena a.(a + 1) pasti habis dibagi oleh 2, maka \frac{a(a + 1)}{2} pasti menghasilkan bilangan bulat. Dengan demikian nilai x adalah bilangan bulat (valid).

Dengan men-substitusikan nilai x yang valid ini kita peroleh :
\begin{array}{cllll} x& +& y& =& a^2 \\ \frac{a(a+1)}{2}& +& y& =& a^2 \\ a(a+1)& +& 2y& =& 2a^2 \\ a^2 + a& +& 2y& =& 2a^2 \\ a& +& 2y& =& a^2 \\ & & 2y& =& a^2 - a \\ & & 2y& =& a(a - 1) \\ & & y& =& \frac{a(a - 1)}{2} \end{array}

Apakah y adalah bilangan bulat? Sekali lagi, karena a – 1 dan a adalah dua buah bilangan bulat yang berturutan maka salah satu dari a – 1 ataupun a adalah genap dan yang lainnya ganjil. Dengan demikian perkalian antara a – 1 dan a pasti habis dibagi oleh 2. Alhasil, nilai y pun pasti berupa bilangan bulat.

Dengan demikian, persamaan x^2 - y^2 = a^3 selalu memiliki minimal satu solusi bilangan bulat x dan y.
Yaitu dengan mengambil nilai x = \frac{a(a + 1)}{2} dan mengambil nilai y = \frac{a(a - 1)}{2}.

Catatan 2 : Perhatikan bahwa penulis mencetak tebal frase “minimal satu” pada paragraf di atas. Ini dimaksudkan untuk menekankan kepada pembaca bahwa solusi yang memenuhi mungkin saja lebih dari satu. Ingat bahwa kita hanya mengambil sepasang faktor/divisor dari a^3. Walaupun solusi mungkin tidak lengkap, tetapi satu solusi sudah cukup (syarat cukup) untuk meyakinkan diri bahwa persamaan x^2 - y^2 = a^3 selalu memiliki solusi untuk x dan y.

Satu pertanyaan yang mengganjal adalah “Apakah boleh kita mengambil asumsi x - y = a^2 dan x + y = a?” Boleh-boleh saja. Asalkan tidak kontradiktif. Untuk penjabarannya diserahkan kepada pembaca. Selamat mencoba

Homework

September 29, 2010

WISNU + OPS = KEREN

Filed under: Puzzle — Hendra Jaya @ 12:41 pm

Pertama-tama.. perlu saya tegaskan bahwa nama saya bukan Wisnu. Jadi jauhkan praduga tak bersalah “narsis”. Walaupun demikian, pengarang teka-teki memang bernama Wisnu OPS.

Soalnya begini :

\begin{array} {llllll} W & I & S & N & U \\ & & O & P & S  \\ - & - & - & - & - & + \\ K & E & R & E & N \end{array}

  1. Carilah nilai (W – K) . (I – E).
  2. Carilah nilai variabel E, K, I, N, O, P, R, S, U, W yang memenuhi. Nilai tiap variabel berada di rentang 0 \leq X \leq 9, X \in \mathbb{Z}. Perhatikan bahwa nilai setiap variabel berbeda dengan variabel lainnya dan (tentu saja) setiap variabel konsisten

Sumber : Wisnu OPS

Pra-Pembahasan

Karena nilai variabel yang satu berbeda dengan yang lain, atau secara matematis X \neq Y, maka kita asumsikan saja X < Y yang memberikan kita sebuah pertidaksamaan :

0 \leq X < Y \leq 9

Perhatikan bahwa pertidaksamaan di atas secara implisit berbunyi “Nilai 0 hanya mungkin diambil oleh X” dan “Nilai 9 hanya mungkin diambil oleh Y”. Atau secara matematis

\begin{array}{cccccr} 0& \leq& X& \leq& 8 \\ 1& \leq& Y& \leq& 9 \\ -& -& ---& -& -& +\\ 1& \leq& X + Y& \leq& 17 \\ \end{array}

Pertidaksamaan terakhir menyatakan bahwa jumlah dua buah variabel X dan Y pasti lebih kecil dari 20. Pertidaksamaan ini menggaransi kita bahwa “carry” – jika ada – nilainya pasti 1.

Pembahasan Pertanyaan 1

Sekarang,

  • Mengapa tiba-tiba W berubah menjadi K walaupun tidak dijumlahkan dengan siapapun
  • Mengapa tiba-tiba I berubah menjadi E walaupun tidak dijumlahkan dengan siapapun?

Perubahan mendadak pada W dan I ini hanya bisa terjadi karena adanya “carry” dari penjumlahan sebelumnya. Penalaran ini membawa kita ke beberapa persamaan :

\begin{array}{lcccccc} \text{Persamaan 1 :}\hspace{1cm} W& +& 1& =& K \\ \hspace{35mm} W& -& K& =& -1 \\ \text{Persamaan 2 :}\hspace{1cm} I& +& 1& =& 10& +& E \\ \hspace{35mm} I& -& E& =& 9 \end{array}

Keterangan : Angka 10 datang karena penjumlahan ini menghasilkan carry.

Pertanyaan pertama bisa dijawab sekarang.

(W - K).(I - E) = -1.9 = -9

Pembahasan Pertanyaan 2

Lebih jauh lagi, karena 0 \leq I \leq 9, maka 1 \leq I + 1 \leq 10. Dari rentang 1 sampai 10, hanya ada satu nilai “overflow” yang menyebabkan carry. Yaitu 10. Pada saat I + 1 = 10, nilai I pastilah 9. Dengan demikian satu variabel pun terselesaikan. Yaitu I = 9.

Karena I + 1 = 10 + E, maka variabel kedua pun dapat diselesaikan dengan men-substitusikan I dengan 9. Kita peroleh  E = 0. Berikut kita tuliskan lagi semua variabel-variabel yang ada.

\begin{array} {llllll} _{1} & _{1} \\ W & 9 & S & N & U \\ & & O & P & S  \\ - & - & - & - & - & + \\ K & 0 & R & 0 & N \end{array}

Sekarang, karena N dan P keduanya jelas bukan 0, maka bisa disimpulkan terjadi overflow pada saat penjumlahan N dan P. Sehingga :

\begin{array} {llllll} _{1} & _{1} & _{1} \\ W & 9 & S & N & U \\ & & O & P & S  \\ - & - & - & - & - & + \\ K & 0 & R & 0 & N \end{array}

Bagaimana dengan U + S? Penjumlahan U dan S bisa overflow, bisa juga tidak. Oleh karena itu akan kita telaah kasus per kasus.

Kasus tidak overflow

Dalam kasus ini, kita bisa tuliskan beberapa persamaan yang kita ketahui :

\begin{array}{lccccccccccc} \text{Persamaan 3 :}\hspace{1cm} & & U& +& S& =& N \\ \text{Persamaan 4 :}\hspace{1cm} & & N& +& P& =& 10 \\ \text{Persamaan 5 :}\hspace{1cm} 1& +& S& +& O& =& 10& +& R \\ \hspace{35mm} & & S& +& O& =& 9& +& R \end{array}

Karena 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45, maka kita bisa memperoleh persamaan berikutnya (6):

\begin{array}{ccccccccccccccccccccc} E& +& I& +& K& +& N& +& O& +& P& +& R& +& S& +& U& +& W& =& 45 \\ 0& +& 9& +& K& +& N& +& O& +& P& +& R& +& S& +& U& +& W& =& 45 \\& & & & K& +& N& +& O& +& P& +& R& +& S& +& U& +& W& =& 36 \end{array}

Sekarang, dengan menyelesaikan persamaan 3 dan 4, kita peroleh :

\begin{array}{lccccccccccc} \text{Persamaan 3 :}\hspace{1cm} & & U& +& S& =& N \\ \text{Persamaan 4 :}\hspace{1cm} & & N& +& P& =& 10 \\ \hspace{35mm} -& -& -& -& -& -& -& -& -& + \\ \text{Persamaan 7 :}\hspace{1cm} U& +& P& +& S& =& 10 \end{array}

Selanjutnya, kita selesaikan persamaan 3 dan 5 :

\begin{array}{lcccccccccccc} \text{Persamaan 3 :}\hspace{1cm} & & & & N& =& U& +& S& \\ \text{Persamaan 5 :}\hspace{1cm} & & S& +& O& =& 9& +& R \\ \hspace{35mm} & & -& -& -& -& -& -& -& -& -& + \\ \text{Persamaan 8 :}\hspace{1cm} & & N& +& O& =& 9& +& R& +& U \end{array}

Berikutnya, kita lihat apa yang bisa kita peroleh dengan mensubstitusikan beberapa persamaan ke persamaan 4.

Substitusi persamaan 1 ke persamaan 4 :

\begin{array}{ccccccccccccccccccccc} & & & & K& +& N& +& O& +& P& +& R& +& S& +& U& +& W& =& 36 \\ & & W& +& 1& +& N& +& O& +& P& +& R& +& S& +& U& +& W& =& 36 \\ & & & & & & N& +& O& +& P& +& R& +& S& +& U& +& 2W& =& 35  \end{array}

Ada kemajuan. Satu variabel, yaitu K, hilang.

Berikutnya, kita substitusi persamaan 7 ke persamaan 4

\begin{array}{ccccccccccccccccccccc} & & & & & & N& +& O& +& P& +& R& +& S& +& U& +& 2W& =& 35 \\ & & & & & & & & & & N& +& O& +& R& +& 10& +& 2W& =& 35 \\ & & & & & & & & & & & & N& +& O& +& R& +& 2W& =& 25 \end{array}

Triple kill. Tiga variabel hilang sekaligus. Kemajuan yang sangat berarti.

Berikutnya kita lihat peruntungan kita dengan men-substitusi persamaan 8 ke persamaan 4.

\begin{array}{ccccccccccccccccccccc} & & & & & & & & & & & & N& +& O& +& R& +& 2W& =& 25 \\ & & & & & & & & & & 9& +& R& +& U& +& R& +& 2W& =& 25 \\ & & & & & & & & & & & & & & U& +& 2R& +& 2W& =& 16 \end{array}

Yak. Tampaknya bentuk terakhir ini sangat membantu. Jelas sekali terlihat bahwa U haruslah bernilai genap.

Saya menggunakan programming untuk mempermudah pencarian. Walaupun demikian, tanpa bantuan programming pun kita bisa mencari kemungkinan-kemungkinan yang ada, asal sabar :)Sekarang, hanya ada tiga buah kuartet yang memenuhi “invarian-invarian” di atas, yaitu :

quartet

Sekarang, akan kita uji semua quartet di atas.

  1. Quartet 1 <2, 3, 5, 7> jika disubstitusikan ke dalam soal akan menghasilkan :
    \begin{array}{llllll} _{1} & _{1} & _{1} \\ W & 9 & 5 & 7 & 2 \\ & & O & 3 & 5 \\ - & - & - & - & - & + \\ K & 0 & R & 0 & 7 \end{array}
    Agar overflow, variabel O harus bernilai 4 \leq O \leq 9 . Yaitu {4, 5, 6, 7, 8, 9}. Karena 5, 7, dan 9 sudah dipakai, maka nilai O yang mungkin hanya {4, 6, 8}. Ketiga nilai ini akan memetakan R ke nilai {0, 2, 4}. Mengingat bahwa nilai 0 sudah dipakai oleh E dan 2 dipakai oleh U, maka duplet <O, R> yang memenuhi adalah <8, 4>.
    Dari 10 angka yang tersedia, yang tersisa tinggal angka 1 dan 6. Yang manapun dipilih, tidak akan ada yang bisa memenuhi persamaan 1. Quartet ini kita nyatakan gugur.
  2. Quartet 2 <2, 7, 1, 3> jika disubstitusikan ke dalam soal akan menghasilkan :
    \begin{array}{llllll} _{1} & _{1} & _{1} \\ W & 9 & 1 & 3 & 2 \\ & & O & 7 & 1 \\ - & - & - & - & - & + \\ K & 0 & R & 0 & 3 \end{array}
    Agar overflow, variabel O harus bernilai 8 \leq O \leq 9 . Yaitu {8, 9}. Karena 9 sudah dipakai, maka nilai O yang mungkin hanya {8}. Sayang seribu sayang, nilai ini akan memetakan R ke nilai {0}. Karena nilai 0 sudah dipakai oleh E, maka tidak ada nilai O yang memenuhi dan quartet ini pun gugur.
  3. Quartet 3 <6, 3, 1, 7> jika disubstitusikan ke dalam soal akan menghasilkan :
    \begin{array}{llllll} _{1} & _{1} & _{1} \\ W & 9 & 1 & 7 & 6 \\ & & O & 3 & 1 \\ - & - & - & - & - & + \\ K & 0 & R & 0 & 7 \end{array}
    Tampaknya, quartet ini juga akan gagal membentuk duplet <O, R>. Mari kita periksa. Agar overflow, variabel O harus bernilai 8 \leq O \leq 9 . Yaitu {8, 9}. Karena 9 sudah dipakai, maka nilai O yang mungkin hanya {8}. Sama seperti quartet yang sebelumnya, nilai 8 untuk O akan memetakan R ke nilai {0}. Karena nilai 0 sudah dipakai oleh E, maka tidak ada nilai O yang memenuhi dan quartet ini kita nyatakan gagal.

Tiga kuartet yang dihasilkan oleh asumsi “tidak Overflow” gugur semua. Hal ini menjamin kita untuk menyatakan bahwa asumsi “tidak overflow” bernilai salah. Saatnya pindah ke asumsi lain, yaitu “terjadi overflow”.

Kasus overflow

Kita tuliskan ulang persamaan-persamaan sebelumnya ke dalam versi “overflow”.

\begin{array} {llllll} _{1} & _{1} & _{1} & _{1} \\ W & 9 & S & N & U \\ & & O & P & S \\ - & - & - & - & - & + \\ K & 0 & R & 0 & N \end{array}

Persamaan-persamaan dasar :

\begin{array}{lccccccccccc} \text{Persamaan 3 :}\hspace{1cm} & & U& +& S& =& 10& +& N \\ \text{Persamaan 4 :}\hspace{1cm} 1& +& N& +& P& =& 10 \\ \hspace{35mm} & & N& +& P& =& 9 \\ \text{Persamaan 5 :}\hspace{1cm} 1& +& S& +& O& =& 10& +& R \\ \hspace{35mm} & & S& +& O& =& 9& +& R \end{array}

Jumlahkan persamaan 3 dan 4 :

\begin{array}{lccccccccccc} \text{Persamaan 3 :}\hspace{1cm} & & U& +& S& =& 10& +& N \\ \text{Persamaan 4 :}\hspace{1cm} & & N& +& P& =& 9 \\ \hspace{35mm} -& -& -& -& -& -& -& -& -& + \\ \text{Persamaan 7 :}\hspace{1cm} U& +& P& +& S& =& 19 \end{array}

Jumlahkan persamaan 3 dan 5 :

\begin{array}{lcccccccccccc} \text{Persamaan 3 :}\hspace{1cm} & & 10& +& N& =& U& +& S& \\ \text{Persamaan 5 :}\hspace{1cm} & & S& +& O& =& 9& +& R \\ \hspace{35mm} -& -& -& -& -& -& -& -& -& + \\ \text{Persamaan 8 :}\hspace{1cm} 1& +& N& +& O& =& R& +& U \end{array}

Substitusi persamaan 8 ke dalam persamaan 4 :

\begin{array}{ccccccccccccccccccccc} & & & & & & N& +& O& +& P& +& R& +& S& +& U& +& 2W& =& 35 \\ & & & & & & & & & & N& +& O& +& R& +& 19& +& 2W& =& 35 \\ & & & & & & & & & & & & N& +& O& +& R& +& 2W& =& 16 \end{array}

Substitusi persamaan 5 ke persamaan 4 :

\begin{array}{ccccccccccccccccccccc} & & & & & & & & & & & & N& +& O& +& R& +& 2W& =& 16 \\ & & & & & & & & & & 1& +& N& +& O& +& R& +& 2W& =& 17 \\ & & & & & & & & & & & & R& +& U& +& R& +& 2W& =& 17 \\ & & & & & & & & & & & & & & U& +& 2R& +& 2W& =& 17 \end{array}

Dari sini, jelas terlihat bahwa U haruslah ganjil. Seperti sebelumnya, saya akan permudah pencarian dengan menggunakan programming. Hasil pencarian saya memberikan empat buah quartet yang memungkinkan :

quartet

Sama seperti pada asumsi “tidak overflow”. Sekarang, kita akan periksa setiap quartet :

  1. Quartet 1 <5, 6, 8, 3> jika disubstitusikan ke dalam soal akan memberikan :
    \begin{array}{llllll} _{1} & _{1} & _{1} &_{1} \\ W & 9 & 8 & 3 & 5 \\ & & O & 6 & 8 \\ - & - & - & - & - & + \\ K & 0 & R & 0 & 3 \end{array}
    Agar overflow, variabel O harus berada di rentang 1 \leq O \leq 9 . Yaitu {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Karena 0, 3, 5, 6, 8, dan 9 sudah dipakai, maka nilai O yang mungkin adalah {1, 2, 4, 7}. Keempat nilai ini akan memetakan R ke nilai {0, 1, 3, 6}. Mengingat bahwa nilai 0, 3 dan 6 sudah dipakai oleh variabel-variabel lain, maka duplet <O, R> yang memenuhi adalah <2, 1>.
    Dari 10 angka yang tersedia, yang tersisa tinggal angka 4 dan 7. Yang manapun dipilih, tidak akan ada yang bisa memenuhi persamaan 1. Quartet ini kita nyatakan gugur.
  2. Quartet 2 <5, 8, 6, 1> jika disubstitusikan ke dalam soal akan memberikan :
    \begin{array}{llllll} _{1} & _{1} & _{1} &_{1} \\ W & 9 & 6 & 1 & 5 \\ & & O & 8 & 6 \\ - & - & - & - & - & + \\ K & 0 & R & 0 & 1 \end{array}
    Agar overflow, variabel O harus berada di rentang 3 \leq O \leq 9. Yaitu {3, 4, 5, 6, 7, 8, 9}. Karena 5, 6, 8, dan 9 sudah dipakai, maka nilai O yang mungkin adalah {3, 4, 7}. Nilai-nilai ini akan memetakan R ke dalam domain {0, 1, 4}. Mengingat 0 sudah dipakai oleh I dan 1 sudah dipakai oleh N, maka duplet <O, R> yang mungkin hanyalah <7, 4>. Dengan mengambil duplet ini, maka angka yang tersisa tinggal 2 dan 3. Nilai yang sempurna dengan persamaan 1. Dengan mengambil nilai W = 2, maka K = 3. Cocok. Satu solusi berhasil ditemukan, yaitu E = 0, I = 9, K = 3, N = 1, O = 7, P = 8, R = 4, S = 6, U = 5, W = 2.
  3. Quartet 3 <7, 4, 8, 5> jika disubstitusikan ke dalam soal akan menghasilkan :
    \begin{array}{llllll} _{1} & _{1} & _{1} &_{1} \\ W & 9 & 8 & 5 & 7 \\ & & O & 4 & 8 \\ - & - & - & - & - & + \\ K & 0 & R & 0 & 5 \end{array}
    Seperti yang sudah-sudah, agar menghasilkan suatu overflow, nilai O harus berada di rentang 1 \leq O \leq 9 . Yaitu {1, 2, 3, 4, 5, 6, 7, 8, 9}. Karena 4, 5, 7, 8, dan 9 sudah diambil oleh variabel lain, maka nilai O yang mungkin adalah {1, 2, 3, 6}.  Nilai-nilai ini akan memetakan R ke dalam nilai {0, 1, 2, 5}. Lagi-lagi, karena 0 dan 5 sudah dipakai oleh variabel lain, maka ada dua duplet <O, R> yang mungkin. Yaitu <2, 1> dan <3, 2>.
    Duplet <2, 1> akan menyisakan 3 dan 6 untuk W dan R. Tidak sesuai dengan keinginan kita, yaitu dua angka yang berturutan.
    Serupa dengan yang sebelumnya, duplet <3, 2> akan menyisakan 1 dan 6 untuk W dan R. Bukan dua angka yang berturutan seperti dinyatakan dalam persamaan 1.
  4. Quartet 4 <7, 8, 4, 1> jika disubstitusikan ke dalam soal akan memberi :
    \begin{array}{llllll} _{1} & _{1} & _{1} &_{1} \\ W & 9 & 4 & 1 & 7 \\ & & O & 8 & 4 \\ - & - & - & - & - & + \\ K & 0 & R & 0 & 1 \end{array}
    Untuk menghasilkan suatu overflow, maka O harus berada di rentang 5 \leq O \leq 9. Yaitu {5, 6, 7, 8, 9}. Sekarang, karena 7, 8, dan 9 sudah diklaim oleh variabel lain. Maka nilai O yang mungkin adalah {5, 6}. Masing-masing nilai O ini akan memetakan R ke dalam domain {0, 1}. Angka 0 sudah dipakai oleh I dan angka 1 sudah dipakai oleh N. Tidak ada duplet <O, R> yang memungkinkan dan dengan demikian quartet ini pun tidak bisa memberikan solusi.

Dari keempat quartet yang ada, hanya satu solusi yang bisa kita dapatkan, yaitu E = 0, I = 9, K = 3, N = 1, O = 7, P = 8, R = 4, S = 6, U = 5, W = 2. Dengan mensubstitusikan variabel-variabel ini kita memperoleh hasil akhir yang diinginkan :

\begin{array} {cccccc} 2& 9& 6& 1& 5 \\ & & 7& 8& 6 \\ -& -& -& -& -& + \\ 3& 0& 4& 0& 1 \end{array}

Trivial

  1. Wisnu mengklaim bahwa hanya ada satu solusi yang memenuhi. Wisnu benar.
  2. Wisnu mengklaim bahwa dirinya tidak narsis. Sepertinya Wisnu salah 🙂

You're Wonderful

September 20, 2010

Algoritma Pembagian 2 : Pembahasan FakPos

Filed under: Algoritma, Matematika, Puzzle, Teori Bilangan — Hendra Jaya @ 6:53 am

Obat ngantuk 1

Jika dituliskan ke dalam bentuk perkalian faktor (a . b), 24 dapat dituliskan sebagai :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&24\\2&|&2&.&12\\3&|&3&.&8\\4&|&4&.&6\end{array}

Perhatikan bahwa dalam bentuk perkalian di atas (a . b),  terdapat beberapa pola :

  1. a\leq b
  2. a_1<a_2<a_3<a_4 ...
  3. b_1>b_2>b_3>b_4 ...

Dan jika dihitung, maka pada data di atas terdapat 4 buah baris dan 2 buah kolom. Sehingga siapapun dapat menghitung dengan cepat banyaknya elemen dalam “tabel”. Tinggal kalikan jumlah baris dan jumlah kolom maka akan diperoleh banyaknya elemen, yaitu 8.

Dengan cara yang sama, 84 juga dapat dituliskan ke dalam bentuk perkalian faktor (a . b) :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&84\\2&|&2&.&42\\3&|&3&.&28\\4&|&4&.&21\\5&|&6&.&14\\6&|&7&.&12\end{array}

Sehingga banyaknya elemen dalam “tabel” juga dapat diperoleh dengan mengalikan jumlah baris dan jumlah kolom. Untuk 84, terdapat 6 baris dan “so pasti” 2 kolom. Sehingga banyaknya elemen yang ada di dalam “tabel” adalah 12.

Karena “2 kolom” adalah suatu keterjadian (hal yang mutlak), maka – jika direpresentasikan ke dalam bentuk tabel perkalian faktor semua bilangan pasti memiliki jumlah elemen dalam bentuk 2 . baris, yaitu suatu bilangan genap. Sayangnya, jumlah elemen di dalam tabel tidak merepresentasikan jumlah faktor yang sebenarnya. Karena, tabel “perkalian faktor” ini tidak menjamin keunikan/uniqueness dari elemen-elemen yang ada.

“Mengapa setiap faktor harus unik?”
Untuk memahaminya, silahkan bayangkan jika anda diperbolehkan untuk menuliskan faktor secara tidak unik. Untuk angka 24, anda dapat menuliskan faktornya sebagai 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, …. 24. Totalnya ada tidak terhingga banyaknya faktor.

Setelah memahami sifat “unik” dari setiap faktor dengan faktor lainnya, sebuah pertanyaan kritis akan muncul.

“Apakah mungkin elemen-elemen pada tabel perkalian faktor tidak unik?”
Mungkin saja, yaitu ketika a=b. Sebagai contoh, angka 25, jika direpresentasikan ke dalam tabel perkalian faktor adalah sebagai berikut :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&25\\2&|&5&.&5\end{array}

Jumlah elemen pada tabel perkalian faktor adalah 4 (genap dan akan selalu genap) sementara jumlah faktor yang sebenarnya adalah 3, yaitu 1, 5, dan 25.

Pertanyaan berikutnya yang mungkin muncul adalah “Berapa kali kasus a = b muncul?”
Konstrain a_1<a_2<a_3<a_4<... secara implisit mengatakan bahwa b_1>b_2>b_3>b_4...  Sekarang, misalkan kasus a=b pertama kali terjadi di baris ke-lima, yaitu pada a_5=b_5 .

Apakah mungkin di baris-baris berikutnya kasus a=b terulang kembali?
Setelah baris ke-lima kita tentu menemui baris ke-enam. Di baris ke-enam akan muncul a_6 yang lebih besar dari a_5, yakni a_6>a_5. Dan akan muncul pula b_6 yang lebih kecil dari b_5, yakni b_5>b_6.

Karena a_5=b_5=m , maka a_6>m>b_6. Suatu hal yang tidak boleh kita lakukan karena di setiap baris kita sudah menyepakati bahwa a\leq b. Dengan demikian, jika kasus a=b terjadi di baris ke-lima dapat dipastikan tidak akan ada baris lagi di bawah baris ke-lima. Atau secara umum dapat kita katakan kasus a=b hanya bisa terjadi maksimal satu kali, dan jika hal itu terjadi di baris ke-n maka pasti n adalah baris terbawah.

Dengan demikian, dapat disimpulkan bahwa kasus ketidak-unikan elemen yang menyebabkan keganjilan jumlah faktor hanya akan muncul di saat baris terbawah dari tabel perkalian faktor-nya dalam bentuk a=b.

Sekarang, apa makna dari a=b? Makna dari a=b adalah bilangan yang dimaksud (c) dapat dituliskan ke dalam bentuk c=a.b=a.a=b.b=a^2=b^2 . Yaitu sebuah bilangan kuadrat. Dengan demikian, kasus keganjilan jumlah faktor hanya akan muncul pada saat c adalah sebuah bilangan kuadrat.

Tour Accounting

Obat Ngantuk 2

Faktor-faktor untuk 1 dapat dituliskan sebagai :

1 = 1

Faktor-faktor untuk 2, yakni 2^1, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\end{array}

Faktor-faktor untuk 4, yakni {2}^{2}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\end{array}

Faktor-faktor untuk 8, yakni {2}^{3}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\end{array}

Faktor-faktor untuk 24, yakni 2^3.3^1, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\\3&=&1.3^1\\6&=&1.2^1.3^1\\12&=&1.2^2.3^1\\24&=&1.2^3.3^1\end{array}

Faktor-faktor untuk 72, yakni {2}^{3}.{3}^{2}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\\3&=&1.3^1\\6&=&1.2^1.3^1\\12&=&1.2^2.3^1\\24&=&1.2^3.3^1\\9&=&1.3^2\\18&=&1.2^1.3^2\\36&=&1.2^2.3^2\\72&=&1.2^3.3^2\end{array}

Catatan : Penulisan faktor di atas dilakukan terurut berdasarkan “kedatangan” faktor prima dan pangkatnya.

Apakah ada pola-nya?
Ada, yaitu :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2^1
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2^1 ataupun 2^2
  • Ketika 3^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3^1
  • dst..

Tanpa mengurangi kebenarannya, kita modifikasi sedikit menjadi :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 3^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan bilangan yang mengandung 3
  • dst..

Sekarang, kita tambahkan sedikit logika.

Ketika 2^1 datang (step 2), belum ada bilangan yang mengandung 2. Begitu juga ketika 3^1 datang (step 4), belum ada bilangan yang mengandung 3. Sehingga, tanpa mengurangi kebenarannya, pola yang terbentuk dapat kita tulis ulang lagi menjadi :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 2
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 3^1 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
  • dst..

Nah akhirnya terbentuk satu pola yang sangat mudah dibaca. Ketika 2^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung 2. Begitu juga ketika 3^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung 3.

Sehingga, secara umum, ketika p^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung p.

Sekarang kita tulis lagi pola kita :

  • Tentukan 1 sebagai awalan.
  • Ketika 2 (atau keluarganya) datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 2.
  • Ketika 3 (atau keluarganya) datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 3.
  • dst..

Misalkan “anggota keluarga” 2 ada k buah, maka :

  • Ketika 1 ditentukan sebagai awalan, jumlah faktor = 1
  • Ketika 2^1 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^2 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^3 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^k datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1

Mengapa semua “anggota keluarga” 2 hanya mau dikalikan dengan satu buah faktor, yaitu 1? Karena mereka takut terjadi “incest”, yaitu perkawinan dengan bilangan “sedarah”, yaitu bilangan yang mengandung angka 2. Hanya ada 1 faktor yang pasti tidak “sedarah” dengan mereka, yaitu 1. Karena perkawinan ini terjadi sebanyak k kali, maka total faktor sekarang ada k+1.

Misalkan “anggota keluarga” 3 ada l buah. Serupa dengan 2, semua bilangan “berdarah” 3 mengharamkan “incest” dan dengan demikian :

  • Ketika 3^1 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^2 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^3 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^l datang, dia hanya mau dikawinkan dengan k+1 buah bilangan

Karena terjadi l kali perkawinan, maka total bilangan baru adalah l.(k+1). Dan jika ditambahkan dengan yang sebelumnya, yaitu k+1. Maka total bilangan (faktor) sekarang adalah l.(k+1)+(k+1)=(l+1).(k+1)

Jika dituliskan ulang polanya menjadi :

  • 1 (awalan)
  • k.1+1=(k+1)
  • l.(k+1)+(k+1)=(l+1).(k+1)
  • m.(l+1).(k+1)+(l+1).(k+1)=(m+1).(l+1).(k+1)
  • dst..

Kesimpulan :

  1. Banyaknya faktor dapat dihitung dengan tepat tanpa harus mengetahui faktor-faktornya.
  2. Banyaknya faktor tidak tergantung kepada faktor prima-nya. Alih-alih, tergantung kepada “pangkat” dari faktor prima-nya.

Technical Jibba-Jabba :

Pseudo-Code :

function FakPos([exp], lower, upper)
  result = 1
  for each i in lower to upper exclusive
    result = result * (1 + exp[i])
  return result

Implementasi Java : Ideone
Implementasi C++ : Sabar subur

Validitas algoritma ini cocok dengan fungsi d(n) seperti dijelaskan pada divisor function.

Secara matematis, FakPos(n) atau d(n) dirumuskan sebagai : d(n)=\prod_{i=1}^{r}(e_i + 1) dimana e_i adalah pangkat/eksponen dari faktor prima ke-i dari n.

Number Order

Blog di WordPress.com.