2010 Oktober « Catatan si Jay

Oktober 23, 2010

Obat Ngantuk Barisan Bilangan 1

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

Problem 1

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…

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

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

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

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

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

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

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

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

Diketahui bahwa :

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

Berapa jumlah:

Total seluruh serangga generasi ke-5?
Serangga (masing-masing jenis) generasi ke-5?
Total seluruh serangga generasi ke-n?
Serangga (masing-masing jenis) generasi ke-n?

Pembahasan

Draft

Problem 10

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$

Tinggalkan sebuah Komentar

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

Nyatakan konsentrat $K_3$ dalam variabel-variabel $a$ , $b$ , $c$ dan $d$ .
Bagaimana relasi $K_3$ terhadap $K_1$ dan $K_2$ ?
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}$ .
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

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}$ .
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?
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.
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

Tinggalkan sebuah Komentar

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 :

Jika $b=0$ , maka GCD dari $a$ dan $b$ adalah $a$ .
Jika , 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

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.
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

Komentar (3)

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

Tinggalkan sebuah Komentar

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

Tinggalkan sebuah Komentar

Berani Taruhan?

Filed under: Brain Teaser, Matematika, Peluang — Hendra Jaya @ 3:53 am

Problem

Di dalam sebuah kelompok yang terdiri dari 50 orang secara acak.
Berapa peluang, minimal 2 orang, dari anggota kelompok ini memiliki tanggal dan bulan lahir yang sama (abaikan tahun lahir)?

Di-dedikasikan untuk : Dedek tercinta , Nurul Retno Nurwulan yang ulang tahun tepat satu hari sebelum artikel ini ditulis.

Pembahasan

Jika $A$ = “Tidak ada dari ke-50 orang ini yang tanggal lahirnya kembar”
Maka $B$ = “Ada, minimal dua orang, dari 50 orang ini yang tanggal lahirnya kembar”
Relasi antara $A$ dan $B$ adalah : $B=\neg A$ . Baca : $B$ adalah negasi dari $A$ .

Perhatikan bahwa Brain Teaser ini meminta kita untuk mencari peluang $B$ , bukan peluang $A$ .

Sekarang, jika :

$P_{50}$ : “Peluang 50 dari ke-50 orang ini tanggal lahirnya kembar”
$P_{49}$ : “Peluang 49 dari ke-50 orang ini tanggal lahirnya kembar”
$P_{48}$ : “Peluang 48 dari ke-50 orang ini tanggal lahirnya kembar”
…
$P_{2}$ : “Peluang 2 dari ke-50 orang ini tanggal lahirnya kembar”
$P_{1}$ : “Peluang 1 dari ke-50 orang ini tanggal lahirnya kembar” alias “tidak ada yang tanggal lahirnya kembar”

Maka $P_{1}+P_{2}+P_{3}+...+P_{48}+P_{49}+P_{50}=1$ .

Lebih jauh lagi :

$\begin{array}{lll}A&=&P_{1}\\B&=&P_{2}+P_{3}+...+P_{48}+P_{49}+P_{50}\\&=&1-A\end{array}$

Jika kita asumsikan 1 tahun = 365 hari.
Isi kelompok = 0 orang. Peluang tanggal lahir orang pertama belum “muncul” adalah $\frac{365}{365}$
Isi kelompok = 1 orang. Peluang tanggal lahir orang kedua belum “muncul” adalah $\frac{364}{365}$
Isi kelompok = 2 orang. Peluang tanggal lahir orang ketiga belum “muncul” adalah $\frac{363}{365}$
Isi kelompok = 3 orang. Peluang tanggal lahir orang keempat belum “muncul” adalah $\frac{362}{365}$
…
Isi kelompok = 48 orang. Peluang tanggal lahir orang ke-empatpuluhsembilan belum “muncul” adalah $\frac{317}{365}$
Isi kelompok = 49 orang. Peluang tanggal lahir orang ke-limapuluh belum “muncul” adalah $\frac{316}{365}$

Peluang kejadian ini ( $A$ ) terjadi adalah $\frac{365}{365}.\frac{364}{365}.\frac{363}{365}.\frac{362}{365}...\frac{317}{365}.\frac{316}{365}=0.02962642042201160$

Dengan demikian peluang munculnya kejadian $B$ adalah : $B=1-A=1-0.02962642042201160=0.97037357957798840$
Atau jika dinyatakan dalam persentase, peluang munculnya kejadian $B$ adalah 97.04%
Atau jika dinyatakan dalam istilah sehari-hari : “Dalam 100 kali taruhan, saya akan menang sekitar 97 kali!”.

Intermezzo

Jika pembaca bertaruh sebanyak 100 kali setiap harinya, dengan besaran Rp. 1.000 tiap putaran. Maka pembaca sangat mungkin membawa pulang uang sekitar 90 ribu tiap harinya (anggap saja kalah 5 kali). Jika kegiatan ini pembaca lakukan setiap harinya, maka dalam satu bulan pembaca akan menghasilkan uang sekitar Rp. 2.700.000. Angka ini – setahu penulis – lebih besar dari gaji PNS golongan 3A di daerah manapun departemen apapun di Indonesia.

Sangat sulit dipercaya. Tetapi angka-angka ini tidak direkayasa dan murni matematika. Tanpa trik.

Peringatan Penulis : Berjudi itu dilarang oleh pemerintah dan agama.

Lottery

Komentar (2)

Oktober 16, 2010

Pulau Rambut

Filed under: Brain Teaser — Hendra Jaya @ 2:26 pm

Problem

Alkisah ada seorang ahli statistik terdampar di sebuah pulau. Namanya pulau rambut.
Setelah beberapa lama hidup bersama warga di pulau tersebut, beliau melakukan survey terhadap seluruh penduduk pulau dan menemukan fakta-fakta sebagai berikut :

Banyaknya rambut setiap penduduk berbeda-beda.
Sebagai contoh, banyaknya rambut Ali ada 40, banyaknya rambut Badu ada 17 dan banyaknya rambut Cokro 26.
Tidak ada penduduk dengan rambut sebanyak 178. Lebih boleh, kurang juga boleh.
Jumlah penduduk lebih banyak daripada rambut siapapun di pulau itu.
Sebagai contoh, jika diketahui rambut Ali ada 40, maka jumlah penduduk pasti lebih dari 40.
Contoh lainnya, jika diketahui rambut Badu ada 17, maka jumlah penduduk pasti lebih dari 17.

Pertanyaan : Berapakah jumlah penduduk maksimal di pulau tersebut?

Pembahasan

Kita mulai dari mengurutkan banyaknya rambut setiap penduduk, mulai dari yang paling sedikit sampai yang paling banyak (well-order).

Misalkan urutan rambut penduduk adalah sebagai berikut : 7, 29, 49, 51, 60, 65, 66, 67, …

Dengan menerima permisalan ini, maka pembaca yang jeli seharusnya menyadari bahwa terjadi kejar-mengejar antara rambut dan jumlah penduduk, dimana jumlah penduduk tidak mungkin menang. Penjelasannya adalah sebagai berikut :

Pada saat kita nyatakan bilangan pertama adalah 7, jumlah penduduk adalah 1.
Selanjutnya, pada bilangan kedua, yaitu 29, jumlah penduduk adalah 2.
Sementara warga ketiga memiliki jumlah rambut 49 dan seterusnya….

Hal ini menyalahi fakta ketiga bahwa “jumlah penduduk lebih banyak daripada rambut siapapun”.

Mengapa “balapan” antara jumlah penduduk dan rambut tidak mungkin dimenangkan oleh jumlah penduduk? Karena, untuk mencapai kemenangan, jumlah penduduk harus ditambah dan konsekuensinya, deret pun akan semakin dipenuhi oleh angka-angka yang semakin membesar. Ingat, bahwa deret di atas diurutkan mulai dari yang terkecil dan banyaknya rambut tiap-tiap penduduk berbeda-beda.

Sekarang, permasalahannya telah berganti menjadi “Bagaimana memenangkan jumlah penduduk pada balapan?” Sederhana saja, deret rambut harus “mengalah” dalam balapan.

Bagaimana caranya jumlah rambut “mengalah”? Dengan memberikan angka sekecil mungkin agar dapat dikalahkan oleh deret jumlah penduduk. Ingat, bahwa dalam balapan, deret jumlah penduduk pasti berupa angka 1, 2, 3, 4, 5, 6, …, yaitu deret hitung.

Karena deret jumlah penduduk telah fixed berupa deret hitung, maka deret rambut haruslah deret lain yang “lebih kecil” dari deret hitung, yaitu 0, 1, 2, 3, 4, 5… Yaitu deret bilangan cacah.

Setelah mengetahui bahwa deret rambut penduduk pasti berupa deret bilangan cacah, yaitu 0, 1, 2, 3, …N. Maka langkah berikutnya menjadi jauh lebih mudah. Sesuai fakta, karena tidak ada penduduk yang memiliki rambut sebanyak 178, maka deret bilangan cacah tersebut pasti berakhir di $N < 178$ . Dimana nilai N maksimum yang mungkin terjadi adalah 177.

Pada saat N = 177, maka jumlah penduduk adalah 178 (deret dimulai dari 0, demi memenangkan deret jumlah penduduk dalam balapan). Dan dengan demikian, jumlah penduduk di pulau tidak mungkin lebih besar dari 178.

Just The Way You Like It

Tinggalkan sebuah Komentar

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\}$ .

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.
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
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.

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$
Untuk :
$\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>\}$

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.
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

Tinggalkan sebuah Komentar

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

Tinggalkan sebuah Komentar

Oktober 23, 2010

Problem 1

Pembahasan

Problem 2

Pembahasan

Problem 3

Pembahasan

Problem 4

Pembahasan

Problem 5

Pembahasan

Problem 6

Pembahasan

Problem 7

Pembahasan

Problem 8

Pembahasan

Problem 9

Pembahasan

Problem 10

Pembahasan

Oktober 20, 2010

Cerita

Pertanyaan

Pembahasan

Oktober 19, 2010

Faktor Persekutuan Terbesar

Teknik Menghitung GCD

Kelipatan Persekutuan Terkecil

Problem

Pra-pembahasan 1 (Penyederhanaan Bentuk)

Pra-Pembahasan 2 : (Fungsi Lain yang Serupa)

Pembahasan

Oktober 18, 2010

Problem

Pra-Pembahasan 1

Pra-Pembahasan 2

Pembahasan

Problem

Pembahasan

Intermezzo

Oktober 16, 2010

Problem

Pembahasan

Problem :

Curahan Hati :

Pra-pembahasan :

Pembahasan

Oktober 13, 2010

Soal

Pembahasan

Follow “Catatan si Jay”