Catatan si Jay

September 30, 2010

Surti & Tejo

Filed under: Brain Teaser — Hendra Jaya @ 4:57 am

Soal

Surti dan Tejo adalah kakak beradik. Agar lebih fasih dalam berbahasa Inggris, Surti mengikuti kursus Bahasa Inggris di LINA. Setiap harinya, kursus dimulai pukul 18.00 dan berakhir pukul 21.00. Karena Tejo tidak suka melihat Surti naik kendaraan umum malam-malam, Tejo berjanji untuk menjemput Surti setiap harinya.

Agar bisa menjemput Surti tepat waktu (pukul 21.00), Tejo harus berangkat dari rumah pukul 20.00. Sama seperti berangkat, perjalanan pulang dari LINA sampai ke rumah pun membutuhkan waktu 1 jam. Sehingga Surti & Tejo baru akan tiba kembali di rumah pukul 22.00. Rutinitas ini dilakukan Tejo tanpa mengeluh sedikitpun. Benar-benar kakak yang baik.

Suatu hari, kursus berakhir lebih cepat dari biasanya, yaitu pukul 19.30. Karena enggan menunggu sampai dijemput Tejo (pukul 21.00), Surti memutuskan untuk pulang dengan berjalan kaki. Di tengah jalan, Surti dan Tejo berpapasan. Ya tentu saja, Surti langsung diangkut Tejo lalu putar balik dan pulang ke rumah. Kakak beradik ini pun tiba di rumah lebih cepat dari biasanya, yaitu pukul 21.40.

  1. Berapa lama Surti berjalan kaki?
  2. (Out of the box) Berapa jauh kira-kira jarak rumah dan LINA?

Sumber : Wisnu OPS

Pembahasan Pertanyaan 1

Waktu yang ditempuh Tejo berkendara sampai bertemu dengan Surti = T
Waktu yang ditempuh surti berjalan kaki = S

Waktu yang ditempuh Surti untuk berjalan kaki dapat dipecah menjadi dua bagian :

  • Dari pukul 19.30 sampai pukul 20.00, Surti berjalan selama 30 menit.
  • Dari pukul 20.00 sampai pertemuan, Surti berjalan selama T menit.
    Mengapa T menit? Karena Tejo berangkat dari rumah pukul 20.00 dan membutuhkan waktu T menit untuk berpapasan dengan Surti. Pada saat itu, jam tangan Surti dan Tejo pasti sama-sama menunjukkan pukul 20.00 + T. Yang artinya Surti telah berjalan selama T menit (dari pukul 20.00).

Akibatnya, kita memperoleh persamaan S = 30 + T.

Sekarang, karena kakak beradik ini tiba di rumah pukul 21.40, berarti Tejo telah mengendarai kendaraannya selama 100 menit. Karena Tejo mengendarai kendaraannya pulang pergi, maka persamaan berikutnya adalah T + T = 100. Dengan demikian T = 50. Selanjutnya S = 80. Pertanyaan pertama pun terjawab.

Pembahasan Pertanyaan 2

Untuk pertanyaan kedua, kita membutuhkan fakta lain yang tidak ada di dalam cerita. Faktanya adalah : “Manusia normal dalam keaadaan sehat dan tanpa rintangan yang berarti membutuhkan waktu 1 jam untuk menempuh jarak 5 Km”.

Kita asumsikan Surti adalah manusia normal dalam keadaan sehat dan perjalanannya tidak menemui rintangan yang berarti. Sungguh suatu asumsi yang sangat berani. Tetapi ini pertanyaan “Out of the box” untuk memberikan prediksi kasar. Akurasi tidak terlalu dipermasalahkan.

Tejo hari ini berkendara selama 50 menit, sementara waktu normalnya adalah 60 menit. Secara kasar dapat dikatakan bahwa jarak yang ditempuh Tejo adalah \frac{5}{6} dari jarak rumah-LINA. Sementara sisanya, yang \frac{1}{6}, ditempuh oleh Surti selama 80 menit.

Lagi-lagi, dapat diperkirakan secara kasar bahwa Surti membutuhkan waktu 480 menit untuk menempuh keseluruhan jarak dari LINA ke rumah. Waktu 480 menit adalah waktu yang lama, yaitu 8 jam! Dengan demikian, kita dapat mem-prediksi secara kasar jarak dari rumah ke LINA adalah 8 x 5Km = 40 Km!

Sebagai informasi tambahan, Selat Sunda yang memisahkan pulau Sumatera dan Jawa jaraknya “hanya” sekitar 25 Km 🙂
Tekad Surti untuk fasih berbahasa Inggris benar-benar luar biasa dan layak untuk mendapat acungan jempol.

Make Up Number

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

Konsep Modulus dan Kekongruenan Bilangan

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

Di setiap jam dinding yang normal, ada terdapat 12 angka. Yaitu 1, 2, 3, 4, … 12. Pada jam digital, angka 12 diganti dengan angka 0. Sehingga angka-angka yang tersedia adalah 0, 1, 2, 3 … 11. Walaupun jam digital bisa di-setting sehingga menunjukkan angka 0, 1, 2, 3 … 23, banyak orang lebih memilih memakai setting 12-jam, yaitu 0, 1, 2, 3, .. 11. Begitu pula para matematikawan. Mereka lebih suka memakai angka 0, 1, 2, 3, … 11. Jangan tanya kenapa.

Di dalam artikel ini, semua jam akan mengikuti sistem 12-jam ala matematikawan, yaitu jam dinding dengan angka 0, 1, 2, 3 … 11. Angka 0 berada di posisi angka 12. Agara lebih mudah dipahami, perhatikan gambar berikut :

jam dinding

  1. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dalam 8 jam mendatang, ke angka berapakah jarum jam akan menunjuk?
  2. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dalam 20 jam mendatang, ke angka berapakah jarum jam akan menunjuk?
  3. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dalam 32 jam mendatang, ke angka berapakah jarum jam akan menunjuk?
  4. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Empat jam yang lalu, di angka berapakah jarum jam menunjuk?
  5. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Enam belas jam yang lalu, di angka berapakah jarum jam menunjuk?
  6. Bila sekarang jarum jam tepat menunjukkan pada angka 0. Dua puluh delapan jam yang lalu, di angka berapakah jarum jam menunjuk?

Jawaban atas seluruh pertanyaan di atas adalah di angka 8. Sekarang akan kita cari tahu kenapa hal ini bisa terjadi.

Identitas dan Simbol

Kita tahu bahwa dalam 12 jam, jarum jam akan kembali ke posisinya semula, yaitu 0. Kita katakan bahwa jarum jam akan membutuhkan 12 jam untuk melakukan satu “putaran penuh”. Dengan kata lain, satu putaran penuh = 12 jam.

Sekarang, seperti layaknya kebiasaan di dunia matematika yang membosankan, akan kita lakukan ritual simbolisasi.
a menyatakan waktu. Untuk masa lalu diberi tanda negatif (-) dan untuk masa yang akan datang tidak diberi tanda, alias positif (+).
q menyatakan banyaknya putaran
d menyatakan waktu yang diperlukan untuk melakukan satu “putaran penuh”. Dengan demikian d = 12.
r menyatakan sisa waktu setelah berputar-putar.

Pembahasan

  1. Waktu yang dimiliki adalah 8 jam (di masa yang akan datang). Dengan demikian a = 8.
    Dalam 8 jam, jarum jam belum melakukan satu kalipun putaran penuh. Dengan demikian q = 0.
    Karena dalam 8 jam si jarum belum berputar sama sekali, maka sisa waktunya tetap 8 jam. Dengan demikian r = 8.
    Secara matematis dapat dituliskan 8 = 0.12 + 8
  2. Waktu yang dimiliki adalah 20 jam (di masa yang akan datang). Dengan demikian a = 20.
    Dalam 20 jam, jarum jam melakukan satu kali putaran penuh. Dengan demikian q = 1.
    Karena jarum jam berputar satu kali, maka waktu yang sudah dikonsumsi untuk berputar adalah 12 jam. Sisanya adalah 8 jam. Dengan demikian r = 8.
    Secara matematis dapat dituliskan 20 = 1.12 + 8
  3. Waktu yang dimiliki adalah 32 jam (di masa yang akan datang). Dengan demikian a = 32.
    Dalam 32 jam, jarum jam melakukan dua kali putaran penuh. Dengan demikian q = 2.
    Karena jarum jam berputar dua kali, maka waktu yang habis untuk berputar-putar adalah 24 jam. Sisanya adalah 8 jam. Dengan demikian r = 8.
    Secara matematis dapat dituliskan 32 = 2.12 + 8
  4. Waktu yang dimiliki adalah 4 jam (di masa lampau). Dengan demikian a = -4.
    Dalam 4 jam (ke belakang), jarum jam belum melakukan satu kalipun putaran penuh. Dengan demikian q = 0.
    Karena dalam 4 jam (ke belakang) si jarum belum berputar sama sekali, maka sisa waktunya tetap 4 jam. Dengan demikian r = -4 (perhatikan tanda negatif).
    Secara matematis dapat dituliskan -4 = 0.12 + -4
    Karena jam kita tidak memiliki angka -4, maka kita harus mengubahnya menjadi suatu angka yang “dikenali” oleh jam kita. Karena kita tahu dalam 12 jam, si jarum pasti akan kembali ke posisinya semula, maka jam -4 akan menunjukkan angka yang sama dengan jam -4 + 12 alias 8. Dengan demikian, jarum jam di pukul -4.00 akan menunjukkan angka 8.
  5. Waktu yang dimiliki adalah 16 jam (di masa lampau). Dengan demikian a = -16.
    Dalam 16 jam (yang lalu), jarum jam telah berputar sebanyak satu kali. Dengan demikian q = -1 (perhatikan tanda negatif).
    Karena dalam 16 jam silam si jarum telah berputar sebanyak satu kali, maka sisa waktu yang dimilikinya adalah 4 jam. Dengan demikian r = -4 (perhatikan tanda negatif).
    Secara matematis dapat dituliskan -16 = -1.12 + -4
    Sama seperti di soal sebelumnya, kita harus mengubah angka -4 menjadi suatu angka yang “dikenali” oleh jam kita, yaitu dengan menambahkan 12 jam “khayal”. Setelah ditambahkan 12 jam “khayal” ini, jarum jam akan menunjukkan pukul 8.
  6. Waktu yang dimiliki adalah 28 jam (di masa lampau). Dengan demikian a = -28.
    Dalam tempo 28 jam (yang lalu), jarum jam telah berputar sebanyak dua kali. Dengan demikian q = -2 (perhatikan tanda negatif).
    Karena dalam 28 jam yang lalu si jarum telah berputar sebanyak dua kali, maka sisa waktu yang dimilikinya adalah 4 jam. Dengan demikian r = -4 (perhatikan tanda negatif).
    Secara matematis dapat dituliskan -28 = -2.12 + -4
    Sama seperti sebelum-sebelumnya, kita harus mengubah angka -4 menjadi suatu angka yang “dikenali” oleh jam kita, yaitu dengan menambahkan 12 jam “khayal”. Setelah ditambahkan 12 jam “khayal” ini, jarum jam akan menunjukkan pukul 8.

Kekongruenan Bilangan

Hal yang menarik dari kasus ini adalah : Dalam 8 jam ataupun 20 jam ataupun 32 jam ke depan, maupun dalam 4 jam ataupun 16 jam ataupun 28 jam ke belakang, semuanya akan menunjuk ke angka yang sama. Yaitu angka 8.

Fenomena ini, di dalam dunia matematika, diberi nama kongruen.
Definisi 1 : Bilangan bulat a dan bilangan bulat b dikatakan kongruen dalam modulo n jika dan hanya jika keduanya memberikan sisa bagi yang sama ketika dibagi dengan n, dimana a, b, n \in \mathbb{Z}. Secara simbolik dinyatakan dengan a \equiv b \ (mod \ n).

Sekarang, karena a = {q}_{1}.n + r dan b = {q}_{2}.n + r, maka dengan melakukan operasi pengurangan kita memperoleh a - b = {q}_{1}.n - {q}_{2}.n. Dengan memanfaatkan sifat distributif pada perkalian, kita mendapatkan a - b = ({q}_{1} - {q}_{2}).n. Sampai disini, kita dapat menyimpulkan bahwa a – b pasti habis dibagi oleh n. Atau secara simbolis dinyatakan dengan n | a - b.

Dari penjabaran di atas, kekongruenan pun dapat diberi definisi yang lain.
Definisi 2 : Bilangan bulat a dan bilangan bulat b dikatakan kongruen dalam modulo n jika dan hanya jika a – b habis dibagi oleh n. Secara matematis : a \equiv b\ (mod \ n) \leftrightarrow n | a - b.

Menurut definisi 1 dari kekongruenan : 8, 20, 32, -4, -16, -28 adalah kongruen dalam modulo 12 karena semuanya memberikan sisa bagi yang sama. Sisa bagi dalam keenam soal di atas ditandai dengan “kemana jarum jam menunjuk”.
Menurut definisi 2 dari kekongruenan : Ambil dua buah bilangan, terserah yang mana, di antara 8, 20, 32, -4, -16 dan -28. Selisih kedua bilangan tersebut pasti habis dibagi oleh 12.

Jika kita tinjau lagi identitas “jam khayal” pada pembahasan di atas, sebenarnya secara implisit kita telah menyatakan bahwa a \equiv q.12 + a\ (mod\ 12) . Untuk sembarang a, q \in \mathbb{Z}

Di dalam teori bilangan matematika, modulus adalah “bilangan pembagi”. Pada bilangan jam, modulus-nya adalah 12. Dan “mod” bukanlah sebuah fungsi ataupun operator, tetapi menyatakan “di modulus berapa dua buah bilangan dinyatakan kongruen”.

Konsep ini agak abstrak. Tetapi bayangkan jika kita memiliki jam dinding yang hanya memiliki angka 0, 1, dan 2. Jam dinding ini secara matematis dikatakan modulus 3. Selanjutnya, jika kita mulai dari 0, maka 17 dan 11 dalam jam dinding “yang aneh ini” sama-sama akan menunjuk angka 2. Dan (lagi-lagi) secara matematis dikatakan 17 \equiv 11 \ (mod \ 3), yaitu 17 dan 11 kongruen di dalam modulus 3.

Di dalam ilmu komputasi, fungsi mod(x, y) ataupun operator binary mod, dapat dikatakan (walaupun kurang tepat) sebagai fungsi yang mencari sisa pembagian x oleh y. Tolong diingat baik-baik bahwa algoritma pembagian euclid adalah algoritma yang matematis, bukan komputatif. Sehingga mungkin memberikan hasil yang berbeda dengan hasil perhitungan (kalkulasi) komputatif.

Untuk memperjelas maksud saya, perhatikan contoh ini :
Menurut kalkulator : \frac {-17}{12} = -1.41666 = -15/12
Menurut algoritma pembagian : -17 = -2.12 + 7

Mengapa hasil pembagian oleh algoritma pembagian berbeda dengan hasil yang sebenarnya? Jawaban yang paling mudah adalah dengan menyalahkan tanda negatif (-) yang membingungkan. Tetapi ada penjelasan yang lain.

Jika mengikuti hasil perhitungan kalkulator, maka algoritma pembagian dapat menyatakan -17 \div 12 sebagai -17 = -1.12 -5. Hasil ini benar (secara komputatif) tetapi tidak masuk akal di dalam matematika. Mengapa tidak masuk akal? Karena di dalam jam dinding 12-jam seperti yang ada di rumah-rumah, tidak ada angka -5. Hal ini sejalan dengan algoritma pembagian yang memberikan syarat 0 \leq r < |d|.

Sama seperti soal-soal sebelumnya, trik yang kita lakukan untuk mengubah angka -5 menjadi angka yang benar adalah dengan menambahkan “putaran-putaran khayal”. Sehingga, -17 = -1.12 -5 + 1212.
Yang biru adalah putaran khayal.
Yang merah adalah “pengimpas”. Hal ini harus dilakukan agar tidak mengubah dividen (dividen : bilangan yang dibagi). Ingat bahwa 12 – 12 = 0.

Sekarang, dengan menggabungkan -5 dan 12 serta menggabungkan 12 dengan -1.12 kita peroleh
-17 = -1.12 – 12 + (-5 + 12)
-17 = -2.12 + 7

Di dalam bentuk ini, dapat dikatakan bahwa -17 (17 jam yang lalu) dalam jam dinding menunjuk angka 7. Angka 7 ini pula-lah yang dimaksud dengan remainder (sisa bagi) r pada algoritma pembagian euclid. Perhatikan bahwa sekarang r telah memenuhi konstrain 0 \leq r < |d|.

Ada penjelasannya mengapa para matematikawan tidak terlalu tertarik dengan quotient (hasil bagi) q. Mereka jauh lebih tertarik dengan r. Penjelasan itu nanti akan kita pahami pada saat berdiskusi tentang teori bilangan yang lainnya. Sebagai konsekuensi atas “ketidaktertarikan” mereka, angka -2 yang keliru ini diabaikan begitu saja 🙂

Ingat baik-baik bahwa algoritma pembagian euclid bukan untuk menghitung (to compute) hasil akhir. Melainkan sebagai senjata untuk menyelesaikan persoalan di teori bilangan yang lain.

Sifat-sifat Dasar Kekongruenan

Jika diketahui : a \equiv b \ (mod \ n) dan p \equiv q \ (mod \ n)
Berlaku (semacam operasi pembagian) : a + p \equiv b + q \ (mod \ n)
Berlaku (semacam operasi perkalian) : ap \equiv bq \ (mod \ n)

Asal muasal datangnya kedua sifat tersebut adalah sebagai berikut :

Karena a \equiv b \ (mod \ n), maka n | a - b. Dalam bentuk yang lain dapat dituliskan : a - b = n.x.

Begitu pula  p \equiv q \ (mod \ n). Kekongruenan p dan q ini dapat dituliskan ke dalam bentuk p - q = n.y

Jika dikenakan operasi penjumlahan :

\begin{array}{lcccr} & a - b& =& n.x \\ & p - q& =& n.y \\ & ------& &------& +\\ & (a - b) + (p - q)& =& n.x + n.y \\ & (a + p) - (b + q)& =& n(x + y) \\ \therefore& a+p& \equiv& b+q \ (mod \ n) \end{array}

Sekarang, karena :

\begin{array}{cccr} a - b& =& n.x \\ q(a - b)& =& q.n.x& \text{dimana } q \neq 0 \end{array}

Begitu juga :

\begin{array}{cccr} p - q& =& n.y \\ a(p - q)& =& a.n.y& \text{dimana } a \neq 0 \end{array}

Jika kedua persamaan di atas dikenai operasi penjumlahan :

\begin{array}{lcccr} & q(a - b)& =& q.n.x \\ & a(p - q)& =& a.n.y \\ & ---------& &-------& +\\ & aq - bq + ap - aq& =& q.n.x + a.n.y \\ & ap - bq& =& n(q.x + a.y) \\ \therefore& ap& \equiv& bq \ (mod \ n) \end{array}

Jika salah satu (atau keduanya) dari a atau q bernilai 0, sifat ap \equiv bq \ (mod \ n) pun jelas terpenuhi.

Obat ngantuk

  1. Bintang Berapa sisa pembagian {19}^{1000} \div {3} ?
  2. Bintang Berapa sisa pembagian {2}^{100} \div {3} ?
  3. BintangBintang Berapa sisa pembagian ({22}^{55}+{55}^{22}) \div {7} ?
  4. BintangBintangBintang Buktikan bahwa {2222}^{5555}+{5555}^{2222} habis dibagi 7. (Seleksi Tim Olimpiade Matematika Indonesia 1997). Pembahasan bisa dilihat di sini.
  5. BintangBintangBintang Kira-kira saja, berapa digit-kah {2}^{123456} ? Pembaca hanya diminta memberikan tebakan se-akurat mungkin. Jika pembaca bisa memberikan jawaban persisnya tentu sangat bagus. Pembahasan bisa dilihat di sini.

Seperti yang sudah-sudah, pembahasan terhadap obat-obat ngantuk ini akan diberikan pada post berikutnya.

I punched my boss

Artikel Terkait :

September 23, 2010

Beberapa Fungsi Dasar : absolute, floor, ceil dan mod

Filed under: Matematika, Teori Bilangan — Hendra Jaya @ 9:07 am

Fungsi abs(x)

Definisi : abs(x) adalah fungsi yang akan mengembalikan bentuk tidak negatif dari sebuah bilangan real (\mathbb{R}) x.
Secara matematis dinyatakan dengan |x| = \begin{cases} x, & \mbox{jika } x \geq 0 \\ -x, & \mbox{jika } x<0 \end{cases}
Secara komputatif dinyatakan dengan : abs(x)

Fungsi floor(x)

Definisi : floor(x) adalah fungsi yang akan mengembalikan bilangan bulat (\mathbb{Z}) terbesar yang tidak lebih besar dari bilangan real (\mathbb{R}) x.
Secara matematis dinyatakan dengan : \lfloor x \rfloor = max\{m \in \mathbb{Z}, m \leq x\}
Secara komputatif dinyatakan dengan floor(x)

Secara logis, persamaan \lfloor x \rfloor = m , ekivalen (jika dan hanya jika) dengan pertidaksamaan-pertidaksamaan di bawah ini :

\begin{array}{lllllllll} \lfloor x \rfloor = m & \leftrightarrow & x - 1 & < &  m & \leq & x \\ \lfloor x \rfloor = m & \leftrightarrow & & & m & \leq & x & < & m + 1 \\ \lfloor x \rfloor = m & \leftrightarrow & x - 1 & < &  m & \leq & x & < & m + 1 \end{array}

Gunakan garis bilangan untuk memahami pertidaksamaan-pertidaksamaan di atas.

Fungsi ceil(x)

Definisi : ceil(x) adalah fungsi yang akan mengembalikan bilangan bulat (\mathbb{Z}) terkecil yang tidak lebih kecil dari bilangan real (\mathbb{R}) x.
Secara matematis dinyatakan dengan : \lceil x \rceil = min\{n \in \mathbb{Z}, n \geq x\}
Secara komputatif dinyatakan dengan ceil(x)

Secara logis, persamaan \lceil x \rceil = n , ekivalen (jika dan hanya jika) dengan pertidaksamaan-pertidaksamaan di bawah ini :

\begin{array}{lllllllll} \lceil x \rceil = n & \leftrightarrow & n - 1 & < &  x & \leq & n \\ \lceil x \rceil = n & \leftrightarrow & & & x & \leq & n & < & x + 1 \\ \lceil x \rceil = n & \leftrightarrow & n - 1 & < &  x & \leq & n & < & x + 1 \end{array}

Gunakan garis bilangan untuk memahami pertidaksamaan-pertidaksamaan di atas.

Relasi floor(x) dan ceil(x)

Di dalam garis bilangan floor(x) dan ceil(x) memiliki relasi ketidaksamaan sebagai berikut :

\begin{array}{llclllcll} x - 1 & < & m & \leq & x & \leq & n & < & x + 1 \\ x - 1 & < & \lfloor x \rfloor & \leq & x & \leq & \lceil x \rceil & < & x + 1 \\ x - 1 & < & floor(x) & \leq & x & \leq & ceil(x) & < & x + 1 \end{array}

Quotient (hasil bagi) dalam algoritma pembagian

Blog ini mengikuti algoritma pembagian euclidean dan mengikuti definisi q (quotient/hasil bagi) yang diajukan oleh Raymond T. Boute. Pemakaian definisi q yang ini dilakukan karena definisi yang diberikan oleh Pak Boute selaras dengan algoritma pembagian euclid. Sebagai intermezzo, ada beberapa definisi q yang diajukan. Antara lain truncated division yang populer serta floored division yang diajukan oleh Donald Knuth. Untuk lebih jelasnya, silahkan pembaca lihat di sini.

Menurut euclidean definition, quotient (q) adalah :

q = \begin{cases} \lfloor \frac{a}{d} \rfloor, & \mbox{jika } d > 0 \\ \lceil \frac{a}{d} \rceil, & \mbox{jika } d < 0 \end{cases}

Fungsi mod(x, y)

Fungsi mod(x, y) sangat erat kaitannya dengan r (remainder/sisa bagi). Walaupun demikian, mod(x, y) berbeda dengan r. Dua perbedaan yang paling mencolok adalah :

  1. Remainder (r) adalah suatu bilangan bulat tidak negatif sementara mod(x, y) boleh negatif. Ingat bahwa r harus memenuhi konstrain 0 \leq r < |d|
    Di dalam signed integer alias bilangan bertanda (+/-), perbedaan ini akan langsung terasa. Implementasi fungsi mod(x, y) antara bahasa pemrograman yang satu dengan yang lain berbeda-beda. Silahkan lihat dokumentasi bahasa pemrograman favorit anda.
  2. Remainder (r) didefinisikan sebagai sisa bagi dari dua buah bilangan bulat sementara mod(x, y) menerima bilangan real x, y \in \mathbb{R}

Definisi mod(x, y) yang dipakai dalam blog ini mengikuti definisi Donald Knuth : mod(x, y) = x - y\lfloor \frac{x}{y} \rfloor

Di dalam garis bilangan, berlaku pertidaksamaan-pertidaksamaan berikut :

Untuk y > 0 :
0 \leq mod(x, y) < y

Untuk y < 0 :
0 \geq mod(x, y) > y

Serupa dengan remainder, mod(x, y) bernilai 0 jika dan hanya jika y habis membagi x.

Catatan

Sangat mungkin terjadi perselisihan pendapat, terutama tentang quotient (q), remainder (r) dan mod(x, y). Oleh karena itu berbagai ralat, kritik, masukan dan tanggapan sangat diharapkan.

Duty Calls

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

September 16, 2010

Algoritma Pembagian

Filed under: Matematika, Teori Bilangan — Hendra Jaya @ 10:05 am

Teorema 1 : Untuk sembarang bilangan bulat a dan d, dimana d\neq 0. Pasti ada bilangan bulat q dan r yang memenuhi a=qd+r dimana 0\leq r<|d|
Secara matematis : Untuk a,d\in\mathbb{Z}, dimana d\neq 0. Pasti ada q,r\in\mathbb{Z} yang memenuhi a=qd+r dimana 0\leq r<\mid d\mid

Selanjutnya :

  • a disebut dividend (bilangan yang dibagi)
  • d disebut divisor (bilangan pembagi/faktor)
  • q disebut quotient (hasil bagi)
  • r disebut remainder (sisa bagi)

Teorema 2 : d dinyatakan habis membagi a jika dan hanya jika r=0. Sebaliknya, d dinyatakan tidak habis membagi a jika dan hanya jika r\neq 0
Secara matematis : d\mid a\Leftrightarrow r=0. Sebaliknya, d\nmid a\Leftrightarrow r\neq 0

Contoh 1 :

\begin{array}{rlrl}2&\mid&6&\text{Baca : 2 habis membagi 6}\\\\-9&\mid&36&\text{Baca : -9 habis membagi 36}\\\\25&\mid&-100&\text{Baca : 25 habis membagi -100}\\\\3&\mid&21&\text{Baca : 3 habis membagi 21}\\\\197&\mid&0&\text{Baca : 197 habis membagi 0}\\\\-11&\mid&-33&\text{Baca : -11 habis membagi -33}\end{array}

Contoh 2 :

\begin{array}{rlrl}3&\nmid&14&\text{Baca : 3 tidak habis membagi 14}\\\\8&\nmid&-53&\text{Baca : 8 tidak habis membagi -53}\\\\-9&\nmid&37&\text{Baca : -9 tidak habis membagi 37}\\\\-9&\nmid&-30&\text{Baca : -9 tidak habis membagi -30}\\\\5&\nmid&17&\text{Baca : 5 tidak habis membagi 17}\\\\13&\nmid&25&\text{Baca : 13 tidak habis membagi 25}\\\\22&\nmid&20&\text{Baca : 22 tidak habis membagi 20}\end{array}

Teorema 3 :  Untuk bilangan bulat a, b, dan c. Jika a habis membagi b dan b habis membagi c, maka a habis membagi c
Secara matematis : Untuk a,b,c\in\mathbb{Z}. Jika a\mid b dan b\mid c maka a\mid c

Teorema 4 : Untuk bilangan bulat a, b, m dan n. Jika c habis membagi a dan c habis membagi b, maka c habis membagi (ma+nb)
Secara matematis : Untuk a,b,m,n\in\mathbb{Z}. Jika c\mid a dan c\mid b maka c\mid (ma+nb)

Dalam algoritma pembagian a=qd+r, perhatikan bahwa sisa bagi/remainder (r) BUKAN hal yang sama dengan fungsi mod(a,d) pada ilmu komputasi. Memang ada hubungannya, tetapi kedua hal ini adalah hal yang berbeda. Serupa dengan algoritma pembagian, d dikatakan habis membagi a jika dan hanya jika mod(a,d)=0.

Contoh 1 (lagi) :

\begin{array}{rlrlrll}6&=&3&.&2&+&0\\\\36&=&-4&.&-9&+&0\\\\-100&=&-4&.&25&+&0\\\\21&=&7&.&3&+&0\\\\ 0 &=&0&.&197&+&0\\\\-33&=&3&.&-11&+&0\end{array}

Contoh 2 (lagi) :

\begin{array}{rlrlrll}14&=&4&.&3&+&2\\\\-53&=&-7&.&8&+&3\\\\37&=&-4&.&-9&+&1\\\\-30&=&-4&.&-9&+&6\\\\17&=&3&.&5&+&2\\\\25&=&1&.&13&+&12\\\\20&=&0&.&22&+&20\end{array}

Untuk selanjutnya, kita definisikan istilah faktor (divisor) dari bilangan bulat a adalah bilangan bulat d yang habis membagi a.
Secara matematis : Faktor/divisor dari a adalah d yang memenuhi d\mid a, dimana a,d\in\mathbb{Z}.

Contoh 3 :

  • Faktor-faktor (divisors) dari 24 : \pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 8,\pm 12,\pm 24
  • Faktor-faktor (divisors) dari 84 : \pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 7,\pm 12,\pm 14,\pm 21,\pm 28,\pm 42,\pm 84

Cobol Programmer

Obat Ngantuk

  1. Bintang Dengan hanya mempertimbangkan faktor-faktor (divisors) positif, maka faktor dari 24 adalah : 1, 2, 3, 4, 6, 8, 12, 24. Totalnya ada 8 faktor positif untuk 24. Dengan aturan yang sama, faktor-faktor positif dari 84 adalah 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84 dan banyaknya ada 12 buah. Ternyata, sebagian besar bilangan memiliki faktor positif dalam jumlah genap. Hanya ada segelintir bilangan yang memiliki faktor positif dalam jumlah ganjil. Cari tahu bilangan jenis apa yang memiliki faktor positif dalam jumlah ganjil dan jelaskan mengapa bisa begitu. Pembahasan ada di sini.
  2. BintangBintang Rancanglah suatu fungsi – sebut saja FakPos(n) – yang mengembalikan banyaknya faktor positif dari suatu bilangan bulat positif n. Sebagai contoh, FakPos(24) = 8 dan FakPos(84) = 12. Untuk mempermudah proses pemfaktoran, akan disediakan test case dalam format :
    <number> <pi>^<ei> <pj>^<ej> <pk>^<ek>…<pn>^<en>

    Contoh input :

    24 2^3 3^1
    84 2^2 3^1 7^1
    337500 2^2 3^3 5^5
    384813 3^2 11^1 13^2 23^1  

    Contoh output :
    8
    12
    72
    36

    Karakteristik input :
    1< \text{number}<10^{13}\text{, number}\in\mathbb{Z}
    p_i<p_j<p_k<...<p_n\text{ dimana }p\in\text{Bilangan Prima}
    \text{number}=p_i^{e_i}p_j^{e_j}p_k^{e_k}...p_n^{e_n}
    Setiap baris berisi satu test case.
    Jumlah test case = 100

    Time Limit
    2 detik

    Test Case(s)
    Ambil di sini.

    Pembahasan
    Problem dibahas di sini.

September 15, 2010

Prinsip Inklusi-Eksklusi

Filed under: Algoritma, Himpunan, Matematika — Hendra Jaya @ 6:41 am

September 14, 2010

Permasalahan 100 dan 99

Filed under: Brain Teaser, Logaritma, Matematika — Hendra Jaya @ 7:42 am

Problem

Mana yang lebih besar? {100}^{99} atau {99}^{100}

Pembahasan (via Logaritma)

Pendekatan yang paling mudah adalah pendekatan melalui logaritma. Sekedar napak tilas untuk menyegarkan ingatan, penulis akan menyajikan ulang dua buah identitas pada logaritma :

  1. \log a^b=b.\log a
  2. Untuk bilangan bulat positif a dan b, jika diketahui a\geq b, maka \log a\geq\log b

Sekarang, kita asumsikan bahwa {100}^{99}>{99}^{100}, sehingga diharapkan \log {100}^{99}>\log {100}^{99}

Sesuai dengan rumus logaritma, kita memperoleh bahwa \log {100}^{99}=99\log 100=198 dan sebaliknya, kita juga memperoleh \log {99}^{100}=100\log 99

Sekarang, pertanyaannya berubah menjadi “Apakah \log 99<1.98 ?” Kita tidak tahu dengan pasti berapa nilai dari \log 99, tetapi kita tahu dengan pasti bahwa \log 100 adalah 2.

Seharusnya – hanya feeling – , \log 99 nilainya sekitar 1.99xxx.

Yap. \log 99 nilainya 1.9956351945975499153 di kalkulator.

Sehingga pertidaksamaan \log 99<1.98 bernilai salah dan dengan demikian asumsi awal yang dibuat pun salah. Suatu kontradiksi yang mengakibatkan pernyataan yang benar adalah {99}^{100}>{100}^{99}

Logarithm Under My Bed

Pembahasan (via Bilangan Euler)

Jika kita misalkan A=100^{99} dan B=99^{99} maka kita peroleh

\begin{array}{lll}\frac{A}{B}&=&\frac{100^{99}}{99^{99}}\\\\\frac{A}{B}&=&(\frac{100}{99})^{99}\\\\\frac{A}{B}&=&(1+\frac{1}{99})^{99}\end{array}

Bentuk \frac{A}{B} di atas sangat mirip dengan bentuk legendaris e=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n.

Dengan memerhatikan bahwa f(n)=(1+\frac{1}{n})^n adalah sebuah fungsi yang monoton naik dan konvergen, yakni

  • Monoton naik karena f(n+1)>f(n)
  • Konvergen karena f(n+1)-f(n)>f(n+2)-f(n+1). Tes konvergensi via perbandingan rasio

Selanjutnya, walaupun 99 tidak bisa dikatakan “tak terhingga”, namun bentuk di atas dapat memberi kita keyakinan bahwa

(1+\frac{1}{99})^{99}<e<99

atau sederhananya

(1+\frac{1}{99})^{99}<99

Dengan demikian \frac{100^{99}}{99^{99}}<99

Sebagai akibatnya 100^{99}<99^{100}

Secara umum, kita dapat mengatakan bahwa (n+1)^n<n^{n+1} berlaku untuk n\geq 3\text{ , }n\in\mathbb{Z} atau dalam kelompok bilangan lain (real) pertidaksamaan berlaku dengan syarat n>e\text{ , }n\in\mathbb{R} dimana e adalah bilangan Euler.

Simplified Version

Pembahasan (via Binomial Newton)

Jika diketahui 0\leq a<k\leq n dimana n,k,a\in\mathbb{Z}

Kita peroleh pertidaksamaan 1:

\begin{array}{rcll}k&>&a\\k-a&>&0\\k-a&\geq&1&\text{ karena }k-a\text{ adalah bilangan bulat}\\\frac{1}{k-a}&\leq&1\\\end{array}

Lalu, karena a\geq 0, kita peroleh pertidaksamaan 2:

\begin{array}{rcl}a&\geq&0\\-a&\leq&0\\n-a&\leq&n\end{array}

Dengan menggabungkan kedua pertidaksamaan, kita peroleh \frac{n-a}{k-a}\leq n

Selanjutnya

\begin{array}{rcl}\frac{n-0}{k-0}&\leq&n\\\frac{n-1}{k-1}&\leq&n\\\frac{n-2}{k-2}&\leq&n\\&\ldots\\\frac{n-(k-2)}{k-(k-2)}&\leq&n\\\frac{n-(k-1)}{k-(k-1)}&\leq&n\end{array}

Sehingga

\begin{array}{rcll}\frac{n-0}{k-0}.\frac{n-1}{k-1}.\frac{n-2}{k-2}\ldots\frac{n-(k-2)}{k-(k-2)}.\frac{n-(k-1)}{k-(k-1)}&\leq&n^k\\\\\frac{n}{k}.\frac{n-1}{k-1}.\frac{n-2}{k-2}\ldots\frac{n-k+2}{2}.\frac{n-k+1}{1}&\leq&n^k\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1)}{k.(k-1).(k-2)\ldots 2.1}&\leq&n^k\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1)}{k!}&\leq&n^k&\text{Definisi faktorial, yaitu }k!=k.(k-1).(k-2)\ldots 3.2.1\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1)}{1}.\frac{1}{k!}&\leq&n^k\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1).(n-k).(n-k-1).(n-k-2)\ldots 2.1}{(n-k).(n-k-1).(n-k-2)\ldots 2.1}.\frac{1}{k!}&\leq&n^k&\text{Kalikan pembilang dan penyebut dengan }(n-k).(n-k-1).(n-k-2)\ldots 2.1\\\\\frac{n!}{(n-k)!}.\frac{1}{k!}&\leq&n^k&\text{Definisi faktorial}\\\\\frac{n!}{k!(n-k)!}&\leq&n^k\\\\\binom{n}{k}&\leq&n^k&\text{Definisi kombinasi }\binom{n}{k}=\frac{n!}{k!(n-k)!}\end{array}

Dari definisi binomial Newton kita tahu bahwa (x+1)^n=\sum_{k=0}^n\binom{n}{k}x^k

Selanjutnya, dengan mengambil x=n, kita peroleh (n+1)^n=\sum_{k=0}^n\binom{n}{k}n^k

Setelah dijabarkan kita peroleh (n+1)^n=\binom{n}{0}n^0+\binom{n}{1}n^1+\binom{n}{2}n^2+\cdots+\binom{n}{n-1}n^{n-1}+\binom{n}{n}n^n

\begin{array}{rlrlrlrlrlclrlr}(n+1)^n&=&\binom{n}{0}n^0&+&\binom{n}{1}n^1&+&\binom{n}{2}n^2&+&\binom{n}{3}n^3&+&\cdots&+&\binom{n}{n-1}n^{n-1}&+&\binom{n}{n}n^n\\\\(n+1)^n&=&1&+&n^2&+&\binom{n}{2}n^2&+&\binom{n}{3}n^3&+&\cdots&+&\binom{n}{n-1}n^{n-1}&+&\binom{n}{n}n^n\\\\(n+1)^n&\leq&1&+&n^2&+&n^n&+&n^n&+&\cdots&+&n^n&+&n^n\end{array}

Dengan mengambil asumsi berani, yaitu :

n^2+1<n^n

Kita peroleh :

\begin{array}{llllr}(n+1)^n&\leq&(n^2+1)+(n-1).n^n&<&n^n+(n-1).n^n\\\\(n+1)^n&&&<&(1+n-1).n^n\\\\(n+1)^n&&&<&n.n^n\\\\(n+1)^n&&&<&n^{n+1}\end{array}

Satu-satunya yang mengganjal pada aljabar pertidaksamaan di atas adalah asumsi berani kita, yaitu n^2+1<n^n.

Secara intuitif jelas sekali bahwa kecepatan “terbang” fungsi kuadratik n^2 akan kalah jauh dibanding n^n. Hal ini wajar karena “pangkat” dari fungsi kuadratik adalah konstan, yaitu 2. Hal ini mirip dengan notasi Big-O pada ilmu komputasi. Pembaca yang berlatar belakang pemrograman tentu sudah menyadari hal ini.

Lantas, pada n berapa, pertidaksamaan n^2+1<n^n berlaku? Pada saat n=2, sisi kiri masih lebih besar dari sisi kanan, yaitu 2^2+1>2^2. Akan tetapi pada saat n=3, sisi kiri sudah kalah (dan akan terus kalah) dari sisi kanan, yaitu 3^2+1<3^3.

Sehingga pertidaksamaan (n+1)^n<n^{n+1} berlaku untuk n\geq 3\text{ , }n\in\mathbb{Z}

Pretty Heavy Stuff

Barisan Bilangan 1 : Deret Aritmatika (Arithmetic Progression)

Filed under: Barisan Bilangan, Matematika, Teori Bilangan — Hendra Jaya @ 7:07 am

Deret

Deret : Sederhana saja, deret adalah daftar/barisan bilangan.
Definisi : Setiap bilangan pada deret disebut sebagai suku/elemen/term. Dilambangkan dengan U.

Deret Aritmatika

Definisi : Deret/barisan bilangan aritmatika adalah sekumpulan bilangan yang disusun sedemikian rupa sehingga jarak/selisih/difference antara setiap suku dengan suku berikutnya selalu tetap (konstan).
Definisi: Setiap bilangan pada deret disebut sebagai suku/element/term

Selanjutnya, jika setiap suku pada deret diberi index, maka deret dapat dituliskan sebagai berikut :
U_1,U_2,U_3,...,U_n.

Contoh-contoh deret aritmatika :

  • 1,3,5,7,10. Deret aritmatika terhingga (finite), yaitu jumlahnya terbatas. Selisih tiap suku dengan suku berikutnya adalah 2.
  • 1,2,3,4,5,6. Deret aritmatika terhingga. Selisih tiap suku dengan suku berikutnya adalah 1.
  • 1,2,3,4,5,6,.... Deret aritmatika tak terhingga (infinite), yaitu jumlahnya tidak terbatas. Selisih tiap suku dengan suku berikutnya adalah 1.
  • 3,2,1,0,-1,-2. Deret aritmatika terhingga. Selisih tiap suku dengan suku berikutnya adalah -1.
  • 4,1,-2,-5,-8,-11,.... Deret aritmatika tak terhingga. Suku pertamanya adalah 4 dan selisih tiap suku dengan suku berikutnya adalah -3.
  • 0,2.5,5,7.5,10,12.5,.... Deret aritmatika tak terhingga. Suku pertamanya adalah 0 dan selisih tiap suku dengan suku berikutnya adalah 2.5
  • \frac{5}{7},\frac{6}{7},\frac{7}{7},\frac{8}{7},\frac{9}{7},\frac{10}{7},.... Deret aritmatika tak terhingga. Suku pertamanya adalah \frac{5}{7} dan selisih tiap suku dengan suku berikutnya adalah \frac{1}{7}
  • a,a+d,a+2d,a+3d,a+4d,a+5d,.... Deret aritmatika tak terhingga. Suku pertamanya adalah a dan selisih tiap suku dengan suku berikutnya adalah d.
  • a,a+d,a+2d,a+3d,a+4d,a+5d,...,a+(n-1)d. Deret aritmatika terhingga. Suku pertamanya adalah a dan selisih tiap suku dengan suku berikutnya adalah d.

Perhatikan baik-baik contoh terakhir.

Di dalam matematika, barisan bilangan seringkali dinyatakan dengan U_1,U_2,U_3,...,U_n dimana U_1=a, U_2=a+d, U_3=a+2d, … dan U_n=a+(n-1)d. Notasi ini dalam matematika bermakna :

Suku pertama (U_1) adalah a dan suku ke-n (U_n) adalah a+(n-1)d dimana d adalah jarak/selisih antara suatu suku dengan suku berikutnya, yakni jarak antara U_m dengan U_{m+1} dimana 1\leq m\leq n. Blog mengikuti notasi ini.

Definisi formalnya :

\begin{array}{llll}U_1&=&a&U_1\text{ adalah suku ke-1}\\U_n&=&a+(n-1)d&U_n\text{ adalah suku ke-n, dengan }n\text{ adalah sembarang bilangan yang memenuhi }n>1\text{ dan }n\in\mathbb{Z}\\d&=&U_{m+1}-U_{m}&d\text{ adalah jarak antara suku ke-m (}U_m\text{) dengan suku berikutnya (}U_{m+1}\text{), dengan }m\text{ adalah sembarang bilangan yang memenuhi }m>1\text{ dan }m\in\mathbb{Z}\end{array}

Contoh barisan aritmatika yang lain :

  • Deret bilangan cacah \mathbb{N}_0 : 0, 1, 2, 3, 4, 5 …
    Tak terhingga dengan d=1, U_1=0 dan U_n=n-1
  • Deret bilangan asli \mathbb{N}_1 : 1, 2, 3, 4, 5, 6 …
    Tak terhingga dengan d=1, U_1=1 dan U_n=n.
  • Deret bilangan genap : 0, 2, 4, 6, 8, 10,…
    Tak terhingga dengan d=2, U_1=0 dan U_n=2.(n-1)
  • Deret bilangan ganjil : 1, 3, 5, 7, 9, 11, 13, 15, ….
    Tak terhingga dengan d=2, U_1=1 dan U_n=2n-1
  • Deret bilangan kelipatan 2 : 2, 4, 6, 8, 10, 12, 14, 16 … 2n
    Terhingga dengan d=2, U_1=2 dan U_n=2n
  • Deret bilangan kelipatan 3 : 3, 6, 9, 12, 15, 18, 21 … 3n
    Terhingga dengan d=3, U_1=3 dan U_n=3n
  • Deret bilangan kelipatan 3 : 0, 3, 6, 9, 12, 15, 18, 21 … 3(n-1)
    Terhingga dengan d=3, U_1=0 dan U_n=3(n-1)

Sifat-sifat Deret Aritmatik

Perhatikan aljabar di bawah ini :

\begin{array}{lllrclrr}&&U_m&=&U_1&+&(m-1)d\\&&U_n&=&U_1&+&(n-1)d\\-&-&-&-&----&-&----&-\\U_m&-&U_n&=&(m-1)d&-&(n-1)d\\U_m&-&U_n&=&(m-n)d\\&&U_m&=&U_n&+&(m-n)d\end{array}

Kita peroleh sifat pertama dari deret aritmatika, yaitu U_m=U_n+(m-n)d.

Penjabaran yang lain :

\begin{array}{rllrrllr}&&U_m&=&U_1&+&(m-1)d\\&&U_{m+2n}&=&U_1&+&(m+2n-1)d\\--&-&---&-&--&-&------------&+\\U_m&+&U_{m+2n}&=&2.U_1&+&(m-1)d+(m+2n-1)d\\U_m&+&U_{m+2n}&=&2.U_1&+&(2m+2n-2)d\\U_m&+&U_{m+2n}&=&2.U_1&+&2.(m+n-1)d\end{array}

Mengingat

\begin{array}{rlrlr}U_{m+n}&=&U_1&+&(m+n-1)d\\2.U_{m+n}&=&2.U_1&+&2.(m+n-1)d\end{array}

Maka bisa disimpulkan sifat kedua dari deret aritmatika, yaitu U_m+U_{m+2n}=2.U_{m+n}

Sifat kedua inilah yang nantinya akan menjadi dasar teori untuk rataan aritmatik (Arithmetic Mean). Sebagai gambaran saja, sifat kedua ini dapat dituliskan menjadi \frac{U_m+U_{m+2n}}{2}=U_{m+n} yang dapat diterjemahkan secara statistik : “nilai rata-rata dari U_m dan U_{m+2n} adalah U_{m+n}“.

Jumlah Semua Suku Pada Deret

Alkisah, Carl Friedrich Gauss, salah satu matematikawan terbaik dan yang paling berpengaruh sepanjang masa, menemukan metode untuk menghitung nilai dari 1+2+3+4+...+100 ketika beliau masih berusia 10 tahun. Metode yang diperkenalkan oleh Gauss di usia belia itu masih belum tergantikan hingga saat ini. Untuk menghormati jasa beliau, metode ini dinamai metode Gaussian.

Metode Gaussian adalah sebagai berikut :

\begin{array}{llllrlrlrlrlrlrlrlrlrr}&&total&=&1&+&2&+&3&+&4&+&...&+&97&+&98&+&99&+&100\\&&total&=&100&+&99&+&98&+&97&+&...&+&4&+&3&+&2&+&1\\-&-&---&=&---&-&--&-&--&-&--&-&-&-&--&-&--&-&--&-&--&+\\2&.&total&=&101&+&101&+&101&+&101&+&...&+&101&+&101&+&101&+&101\\2&.&total&=&100&.&101\\&&total&=&\frac{100.101}{2}\\&&total&=&5050\end{array}

Lantas, bagaimana caranya menghitung jumlah dari suku-suku pada sebuah deret aritmatik?

Untuk menghitung jumlah dari suku-suku pada sebuah deret aritmatik, kita akan meminjam metode Gaussian ini sebentar :

\begin{array}{llllrlrlrlrlrlrlrlrlrr}&&S_n&=&a&+&a+d&+&a+2d&+&a+3d&+&...&+&a+(n-4)d&+&a+(n-3)d&+&a+(n-2)d&+&a+(n-1)d\\&&S_n&=&a+(n-1)d&+&a+(n-2)d&+&a+(n-3)d&+&a+(n-2)d&+&...&+&a+3d&+&a+2d&+&a+d&+&a\\-&-&-&=&--------&-&--------&-&--------&-&--------&-&-&-&--------&-&--------&-&--------&-&--------&+\\2&.&S_n&=&a+a+(n-1)d&+&a+a+(n-1)d&+&a+a+(n-1)d&+&a+a+(n-1)d&+&...&+&a+a+(n-1)d&+&a+a+(n-1)d&+&a+a+(n-1)d&+&a+a+(n-1)d\\2&.&S_n&=&U_1+U_n&+&U_1+U_n&+&U_1+U_n&+&U_1+U_n&+&...&+&U_1+U_n&+&U_1+U_n&+&U_1+U_n&+&U_1+U_n\\2&.&S_n&=&n.(U_1+U_n)\\&&S_n&=&\frac{n.(U_1+U_n)}{2}\end{array}

Dengan demikian kita peroleh rumus untuk menghitung total nilai seluruh suku pada deret aritmatika, yaitu S_n=\frac{n.(U_1+U_n)}{2}. Dimana :

S_n menyimbolkan jumlah (sum) dari suku-suku pada deret.
U_1 menyimbolkan suku pertama pada deret.
U_n menyimbolkan suku terakhir pada deret.
n menyimbolkan banyaknya suku pada deret.

Karena deret aritmatika berbentuk U_1,U_2,U_3,...,U_{n-2},U_{n-1},U_n maka kita boleh saja meng-asumsikan bahwa ada suku U_m yang letaknya berada di rentang U_1\leq U_m\leq U_n (well-order principle) sehingga deret aritmatika dapat dituliskan sebagai U_1,U_2,U_3,...,U_m,U_{m+1},U_{m+2},....,U_{n-2},U_{n-1},U_n.

Sekarang jika kita pandang secara parsial (sebagian), yakni deret kita mulai dari suku ke-m, maka kita memperoleh deret baru, yaitu U_m,U_{m+1},U_{m+2},....,U_{n-2},U_{n-1},U_n.

Ada berapa banyak suku pada deret ini?

Sebelumnya, deret memiliki n suku. Tetapi karena kita hanya mengambil sepotong saja dari deret tersebut, artinya ada sebagian suku yang kita tinggalkan. Banyaknya suku yang kita tinggalkan adalah m-1 suku. Dan dengan demikian banyaknya suku yang kita “pakai” adalah n-(m-1) suku, yaitu n-m+1 suku.

Berapa jumlah nilai suku-suku pada deret baru ini?

Suku pertama pada deret ini adalah U_m dan suku terakhir adalah U_n. Banyaknya suku ada n-m+1 buah. Sesuai dengan rumus yang tadi kita peroleh, jumlah nilai suku-suku pada deret ini adalah S_{n-m+1}=\frac{(n-m+1).(U_m+U_n)}{2}

Rumus ini adalah rumus umum untuk mencari jumlah nilai suku-suku pada deret. Baik secara parsial ataupun secara utuh. Jika ingin menghitung secara utuh, gunakan m=1.

Einstein's First Equation

Rataan Aritmatika

Sesuai dengan judulnya, rataan aritmatika (Arithmetic Mean/AM) adalah nilai rata-rata pada barisan aritmatika. Baik secara parsial ataupun secara utuh.

Sebagai contoh :

  1. Nilai rata-rata dari deret 1,2,3,4,5,6,7,8,9,10 adalah \frac{1+2+3+4+5+6+7+8+9+10}{10}=\frac{55}{10}=5.5
  2. Nilai rata-rata dari deret 1,2,3,4,5,6,7,8,9 adalah \frac{1+2+3+4+5+6+7+8+9}{9}=\frac{45}{9}=5
  3. Nilai rata-rata dari deret 3,4,5,6,7,8,9 adalah \frac{3+4+5+6+7+8+9}{7}=\frac{42}{7}=6
  4. Nilai rata-rata dari deret 1,2,3,4,5,6,7 adalah \frac{1+2+3+4+5+6+7}{7}=\frac{28}{7}=4
  5. Nilai rata-rata dari deret 1,2,3,4 adalah \frac{1+2+3+4}{4}=\frac{10}{4}=2.5
  6. Nilai rata-rata dari deret 1,2,3 adalah \frac{1+2+3}{3}=\frac{6}{3}=2
  7. Nilai rata-rata dari deret 1,3 adalah \frac{1+3}{2}=\frac{4}{2}=2
  8. Nilai rata-rata dari deret 2 adalah \frac{2}{1}=2

Apakah ada pola yang menarik?

Ada. Ternyata nilai rata-rata pada berbagai deret aritmatik di atas sangat dekat atau bahkan persis dengan nilai tengah (median) dari deret tersebut.

Secara umum, rataan aritmatika dirumuskan sebagai berikut :

AM=\frac{U_1+U_2+U_3+...+U_n}{n}

Jika kita ambil kasus sederhana yaitu deret dengan tiga buah suku U_1,U_2,U_3, maka AM=\frac{U_1+U_2+U_3}{3}.

Akan tetapi, ilmu barisan bilangan tidak berhenti sampai disitu saja. Perhatikan penjabaran berikut ini :

\begin{array}{llllclclc}3&.&AM&=&U_1&+&U_2&+&U_3\\3&.&AM&=&a&+&a+d&+&a+2d\\3&.&AM&=&3a+3d\\&&AM&=&a+d\\&&AM&=&a+(2-1)d\\&&AM&=&U_2\end{array}

Hal ini menarik perhatian kita karena secara langsung penjabaran di atas menyatakan bahwa AM=\frac{U_1+U_2+U_3}{3}=U_2

Ingat bahwa di bagian atas dari artikel ini kita telah membahas sifat kedua dari barisan aritmatika, yaitu U_m+U_{m+2n}=2.U_{m+n}. Dengan mengambil m=1 dan n=1 kita peroleh :

\begin{array}{lllll}U_m&+&U_{m+2n}&=&2.U_{m+n}\\U_1&+&U_{1+2.1}&=&2.U_{1+1}\\U_1&+&U_3&=&2.U_2\end{array}

Atau dengan menuliskan ke dalam bentuk lain kita peroleh \frac{U_1+U_3}{2}=U_2.

Apa yang sebenarnya terjadi? Mengapa rataan dari tiga buah suku dan dua buah suku menghasilkan hasil yang sama?

Mari kita bahas perlahan-lahan.

Misalkan k=m dan l=m+2n. Maka \frac{k+l}{2}=m+n.

Seperti yang sudah kita ketahui melalui sifat kedua dari barisan aritmatik, U_k dan U_l akan memiliki nilai rata-rata yang sama dengan U_{\frac{k+l}{2}}, yaitu suku yang berada di tengah-tengah mereka. Hal ini berlaku umum untuk setiap suku pada barisan aritmatik.

Bagaimana jika k+l tidak habis dibagi 2?

Jika k+l tidak habis dibagi 2, maka suku ke-\frac{k+l}{2} adalah suku fiktif. Walaupun demikian, konsepnya tidak berubah. Suku fiktif ini secara logis akan berada di tengah-tengah dari U_k dan U_l.

Dengan demikian, fenomena di atas dapat dijelaskan sebagai berikut :

\begin{array}{llllllll}&&U_1&+&U_3&=&2.U_2&\text{Rata-rata dari }U_1\text{ dan }U_3\text{ adalah }U_2\\&&&&U_2&=&U_2&\text{Tambahkan dengan }U_2\\-&-&-&-&-&-&---&+\\U_1&+&U_2&+&U_3&=&3.U_2\end{array}

Terlihat jelas bahwa nilai rata-rata dari U_1, U_2 dan U_3 adalah \frac{U_1+U_2+U_3}{3}=U_2 lagi.

Mari kita perbesar kasusnya dengan mencari rata-rata dari U_1,U_2,U_3,U_4,U_5 :

\begin{array}{llllllllllll}&&&&&&U_1&+&U_5&=&2.U_3&\text{Rata-rata dari }U_1\text{ dan }U_5\text{ adalah }U_3\\&&&&&&U_2&+&U_4&=&2.U_3&\text{Rata-rata dari }U_2\text{ dan }U_4\text{ adalah }U_3\\&&&&&&&&U_3&=&U_3&\text{Tambahkan dengan }U_3\\-&-&-&-&-&-&-&-&-&-&---&+\\U_1&+&U_2&+&U_3&+&U_4&+&U_5&=&5.U_3\end{array}

Nilai-rata-rata dari U_1,U_2,U_3,U_4,U_5 adalah \frac{U_1+U_2+U_3+U+4+U_5}{5}=U_3, yaitu suku tengah (median) pada deret.

Mari kita lihat kasus parsial dengan mencari rata-rata dari U_4,U_5,U_6,U_7,U_8 :

\begin{array}{llllllllllll}&&&&&&U_4&+&U_8&=&2.U_6&\text{Rata-rata dari }U_4\text{ dan }U_8\text{ adalah }U_6\\&&&&&&U_5&+&U_7&=&2.U_6&\text{Rata-rata dari }U_5\text{ dan }U_7\text{ adalah }U_6\\&&&&&&&&U_6&=&U_6&\text{Tambahkan dengan }U_6\\-&-&-&-&-&-&-&-&-&-&---&+\\U_4&+&U_5&+&U_6&+&U_7&+&U_8&=&5.U_6\end{array}

Nilai-rata-rata dari U_4,U_5,U_6,U_7,U_8 adalah \frac{U_4+U_5+U_6+U+7+U_8}{5}=U_6, yaitu suku tengah (median) pada deret.

Secara umum, bisa disimpulkan bahwa deret U_1,U_2,U_3,...,U_n akan memiliki nilai rata-rata yang sama dengan nilai rata-rata dari U_1,U_n, yaitu AM=\frac{U_1+U_n}{2}.

Atau, untuk kasus parsial seperti deret U_m,U_{m+1},U_{m+2},...,U_n, akan memiliki nilai rata-rata yang sama dengan nilai rata-rata dari U_m,U_n, yaitu AM=\frac{U_m+U_n}{2}.

Sifat ini amat sangat membantu kita untuk mencari nilai rata-rata dari sebuah deret aritmatika. Karena tidak perduli berapa banyaknya suku pada deret, kita dapat dengan mudah mencari nilai rata-rata dengan menghitung rata-rata dari dua buah suku saja. Yaitu rata-rata dari suku pertama dan suku terakhir. Atau secara parsial, suku ke-m dan suku ke-n.

Computer Holy Wars

Obat Ngantuk

  1. Dengan mengambil rentang 1\leq n\leq 150,
    1. Ada berapa banyak bilangan kelipatan 2 di rentang tersebut?
    2. Berapa jumlah bilangan kelipatan 2 di rentang tersebut?
    3. Ada berapa banyak bilangan kelipatan 3 di rentang tersebut?
    4. Berapa jumlah bilangan kelipatan 3 di rentang tersebut?
  2. Dengan mengambil rentang 1\leq n\leq 150,
    1. Ada berapa banyak bilangan kelipatan 2 atau 3 di rentang tersebut?
    2. Berapa jumlah bilangan kelipatan 2 atau 3 di rentang tersebut?
    3. Ada berapa banyak bilangan kelipatan 3 atau 5 di rentang tersebut?
    4. Berapa jumlah bilangan kelipatan 3 atau 5 di rentang tersebut?
  3. Konsep
    1. Barisan bilangan fibonacci adalah 1, 1, 2, 3, 5, 8, 13, 21, ….
      Apakah barisan bilangan fibonacci merupakan barisan bilangan aritmatika atau bukan? Jelaskan jawaban anda.
    2. Barisan bilangan prima adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
      Apakah barisan bilangan prima adalah barisan bilangan aritmatika atau bukan? Jelaskan jawaban anda.
  4. Bintang Carilah rumus suku ke-n (U_n) pada barisan-barisan bilangan di bawah ini dan jelaskan mengapa mereka bukan barisan bilangan aritmatika. Pembahasan ada di sini.
    1. Barisan pertama : 1, 4, 9, 16, 25, 36, 49, 64, 81, ….
    2. Barisan kedua : 0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, …
    3. Barisan ketiga : 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ….
    4. Barisan keempat : 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, …
  5. 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 (American High School Mathematics Examination). Pembahasan ada di sini.
  6. 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 ada di sini.
  7. 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 ada di sini.
  8. 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. Pembahasan ada di sini.
    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 ada di sini.
  9. Bintang Ada berapa banyak nilai n sedemikian rupa sehingga 1+2+3+4+...+n habis membagi 6n. (American Mathematics Competition 12^{th} grade). Pembahasan ada di sini.
  10. 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? (Introduction to Algebra). Pembahasan ada di sini.
  11. BintangBintang Hitunglah nilai dari \frac{1}{1}+\frac{1}{3}+\frac{1}{6}+\frac{1}{10}+...+\frac{1}{5050}. Pembahasan ada di sini.
  12. Bintang Dalam sebuah deret aritmatika, diketahui fakta-fakta berikut :
    1. U_1+U_2+U_3+...+U_{100}=100
    2. U_{101}+U_{102}+U_{103}+...+U_{200}=200
    3. Berapakah nilai dari U_1? Pembahasan ada di sini.
  13. BintangBintangBintang Diketahui bahwa : (Pembahasan ada di sini)
    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?

    Dept Math & Frustration

Blog di WordPress.com.