Surti & Tejo

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 dari jarak rumah-LINA. Sementara sisanya, yang , 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.

WISNU + OPS = KEREN

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 :

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 . 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 , maka kita asumsikan saja yang memberikan kita sebuah pertidaksamaan :

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

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 :

Keterangan : Angka 10 datang karena penjumlahan ini menghasilkan carry.

Pertanyaan pertama bisa dijawab sekarang.

Pembahasan Pertanyaan 2

Lebih jauh lagi, karena , maka . 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.

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

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 :

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

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

Selanjutnya, kita selesaikan persamaan 3 dan 5 :

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

Substitusi persamaan 1 ke persamaan 4 :

Ada kemajuan. Satu variabel, yaitu K, hilang.

Berikutnya, kita substitusi persamaan 7 ke persamaan 4

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

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

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 :

Sekarang, akan kita uji semua quartet di atas.

1. Quartet 1 <2, 3, 5, 7> jika disubstitusikan ke dalam soal akan menghasilkan :
   
   Agar overflow, variabel O harus bernilai . 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 :
   
   Agar overflow, variabel O harus bernilai . 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 :
   
   Tampaknya, quartet ini juga akan gagal membentuk duplet <O, R>. Mari kita periksa. Agar overflow, variabel O harus bernilai . 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”.

Persamaan-persamaan dasar :

Jumlahkan persamaan 3 dan 4 :

Jumlahkan persamaan 3 dan 5 :

Substitusi persamaan 8 ke dalam persamaan 4 :

Substitusi persamaan 5 ke persamaan 4 :

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 :

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 :
   
   Agar overflow, variabel O harus berada di rentang . 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 :
   
   Agar overflow, variabel O harus berada di rentang . 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 :
   
   Seperti yang sudah-sudah, agar menghasilkan suatu overflow, nilai O harus berada di rentang . 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 :
   
   Untuk menghasilkan suatu overflow, maka O harus berada di rentang . 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 :

Trivial

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

Konsep Modulus dan Kekongruenan Bilangan

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 :

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 . Secara simbolik dinyatakan dengan .

Sekarang, karena dan , maka dengan melakukan operasi pengurangan kita memperoleh . Dengan memanfaatkan sifat distributif pada perkalian, kita mendapatkan . Sampai disini, kita dapat menyimpulkan bahwa a – b pasti habis dibagi oleh n. Atau secara simbolis dinyatakan dengan .

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

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

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 , 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 : = -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 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 .

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 + 12 – 12.
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 .

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 : dan
Berlaku (semacam operasi pembagian) :
Berlaku (semacam operasi perkalian) :

Asal muasal datangnya kedua sifat tersebut adalah sebagai berikut :

Karena , maka . Dalam bentuk yang lain dapat dituliskan : .

Begitu pula  . Kekongruenan p dan q ini dapat dituliskan ke dalam bentuk

Jika dikenakan operasi penjumlahan :

Sekarang, karena :

Begitu juga :

Jika kedua persamaan di atas dikenai operasi penjumlahan :

Jika salah satu (atau keduanya) dari a atau q bernilai 0, sifat pun jelas terpenuhi.

Obat ngantuk

1. Berapa sisa pembagian ?
2. Berapa sisa pembagian ?
3. Berapa sisa pembagian ?
4. Buktikan bahwa habis dibagi 7. (Seleksi Tim Olimpiade Matematika Indonesia 1997). Pembahasan bisa dilihat di sini.
5. Kira-kira saja, berapa digit-kah ? 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.

Artikel Terkait :

• Algoritma Pembagian

Beberapa Fungsi Dasar : absolute, floor, ceil dan mod

Fungsi abs(x)

Definisi : abs(x) adalah fungsi yang akan mengembalikan bentuk tidak negatif dari sebuah bilangan real () x.
Secara matematis dinyatakan dengan
Secara komputatif dinyatakan dengan :

Fungsi floor(x)

Definisi : floor(x) adalah fungsi yang akan mengembalikan bilangan bulat () terbesar yang tidak lebih besar dari bilangan real () x.
Secara matematis dinyatakan dengan :
Secara komputatif dinyatakan dengan

Secara logis, persamaan , ekivalen (jika dan hanya jika) dengan pertidaksamaan-pertidaksamaan di bawah ini :

Gunakan garis bilangan untuk memahami pertidaksamaan-pertidaksamaan di atas.

Fungsi ceil(x)

Definisi : ceil(x) adalah fungsi yang akan mengembalikan bilangan bulat () terkecil yang tidak lebih kecil dari bilangan real () x.
Secara matematis dinyatakan dengan :
Secara komputatif dinyatakan dengan

Secara logis, persamaan , ekivalen (jika dan hanya jika) dengan pertidaksamaan-pertidaksamaan di bawah ini :

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 :

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 :

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

Definisi mod(x, y) yang dipakai dalam blog ini mengikuti definisi Donald Knuth :

Di dalam garis bilangan, berlaku pertidaksamaan-pertidaksamaan berikut :

Untuk :

Untuk :

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.

Algoritma Pembagian 2 : Pembahasan FakPos

Obat ngantuk 1

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

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

1. 
2. 
3. 

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) :

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 . Sebagai contoh, angka 25, jika direpresentasikan ke dalam tabel perkalian faktor adalah sebagai berikut :

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 secara implisit mengatakan bahwa   Sekarang, misalkan kasus pertama kali terjadi di baris ke-lima, yaitu pada .

Apakah mungkin di baris-baris berikutnya kasus terulang kembali?
Setelah baris ke-lima kita tentu menemui baris ke-enam. Di baris ke-enam akan muncul yang lebih besar dari , yakni . Dan akan muncul pula yang lebih kecil dari , yakni .

Karena , maka . Suatu hal yang tidak boleh kita lakukan karena di setiap baris kita sudah menyepakati bahwa . Dengan demikian, jika kasus terjadi di baris ke-lima dapat dipastikan tidak akan ada baris lagi di bawah baris ke-lima. Atau secara umum dapat kita katakan kasus 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 .

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

Obat Ngantuk 2

Faktor-faktor untuk 1 dapat dituliskan sebagai :

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

Faktor-faktor untuk 4, yakni , dapat dituliskan sebagai :

Faktor-faktor untuk 8, yakni , dapat dituliskan sebagai :

Faktor-faktor untuk 24, yakni , dapat dituliskan sebagai :

Faktor-faktor untuk 72, yakni , dapat dituliskan sebagai :

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 datang, kalikan dengan semua faktor yang ada.
• Ketika datang, kalikan dengan semua, kecuali dengan faktor yang mengandung
• Ketika datang, kalikan dengan semua, kecuali dengan faktor yang mengandung ataupun
• Ketika datang, kalikan dengan semua faktor yang ada.
• Ketika datang, kalikan dengan semua, kecuali dengan faktor yang mengandung
• dst..

Tanpa mengurangi kebenarannya, kita modifikasi sedikit menjadi :

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

Sekarang, kita tambahkan sedikit logika.

Ketika datang (step 2), belum ada bilangan yang mengandung 2. Begitu juga ketika 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 datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 2
• Ketika datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
• Ketika datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
• Ketika datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
• Ketika datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
• dst..

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

Sehingga, secara umum, ketika (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 buah, maka :

• Ketika 1 ditentukan sebagai awalan, jumlah faktor = 1
• Ketika datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
• Ketika datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
• Ketika datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
• …
• Ketika 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 kali, maka total faktor sekarang ada .

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

• Ketika datang, dia hanya mau dikawinkan dengan buah bilangan,
• Ketika datang, dia hanya mau dikawinkan dengan buah bilangan,
• Ketika datang, dia hanya mau dikawinkan dengan buah bilangan,
• …
• Ketika datang, dia hanya mau dikawinkan dengan buah bilangan

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

Jika dituliskan ulang polanya menjadi :

• (awalan)
• 
• 
• 
• 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 seperti dijelaskan pada divisor function.

Secara matematis, FakPos(n) atau d(n) dirumuskan sebagai : dimana adalah pangkat/eksponen dari faktor prima ke-i dari n.

Algoritma Pembagian

Teorema 1 : Untuk sembarang bilangan bulat dan , dimana . Pasti ada bilangan bulat dan yang memenuhi dimana
Secara matematis : Untuk , dimana . Pasti ada yang memenuhi dimana

Selanjutnya :

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

Teorema 2 : dinyatakan habis membagi jika dan hanya jika . Sebaliknya, dinyatakan tidak habis membagi jika dan hanya jika
Secara matematis : . Sebaliknya,

Contoh 1 :

Contoh 2 :

Teorema 3 :  Untuk bilangan bulat , , dan . Jika habis membagi dan habis membagi , maka habis membagi
Secara matematis : Untuk . Jika dan maka

Teorema 4 : Untuk bilangan bulat , , dan . Jika habis membagi dan habis membagi , maka habis membagi
Secara matematis : Untuk . Jika dan maka

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

Contoh 1 (lagi) :

Contoh 2 (lagi) :

Untuk selanjutnya, kita definisikan istilah faktor (divisor) dari bilangan bulat adalah bilangan bulat yang habis membagi .
Secara matematis : Faktor/divisor dari adalah yang memenuhi , dimana .

Contoh 3 :

• Faktor-faktor (divisors) dari 24 :
• Faktor-faktor (divisors) dari 84 :

Obat Ngantuk

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

Prinsip Inklusi-Eksklusi

Problem

• Berapa jumlah bilangan kelipatan 2 atau 3 di bawah 1 juta?
• Berapa jumlah bilangan kelipatan 2 atau 3 di bawah 10 juta?
• Berapa jumlah bilangan kelipatan 2 atau 3 di bawah 100 juta?
• Berapa jumlah bilangan kelipatan 2 atau 3 di bawah 1 milyar?
• Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 di bawah 1 juta?
• Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 di bawah 10 juta?
• Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 di bawah 100 juta?
• Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 di bawah 1 milyar?
• Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 atau 7 di bawah 1 juta?
• Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 atau 7 di bawah 10 juta?
• Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 atau 7 di bawah 100 juta?
• Berapa jumlah bilangan kelipatan 2 atau 3 atau 5 atau 7 di bawah 1 milyar?
• dst…

Post Terkait : Barisan Bilangan 1 : Deret Aritmatika
Bahan : Deret Aritmatik, Prinsip Inklusi-Eksklusi

Pembahasan

Ada satu prinsip yang perlu dikuasai untuk menjawab pertanyaan-pertanyaan di atas. Namanya Prinsip Inklusi-Eksklusi. Hal penting yang mungkin lupa diajarkan oleh bapak/ibu guru kita di sekolah. Untuk memahami penjelasan mudahnya, perhatikan contoh di bawah ini :

Tanda (+) :  3, 5, dan 7
Tanda (-) :  15, 21 dan 35
Tanda (+) :  105
dst…

Secara umum, semua kombinasi “orde” ganjil akan bertanda positif dan semua kombinasi “orde” genap akan bertanda negatif. Untuk pembuktiannya silahkan kunjungi link yang penulis berikan di atas. Yang dimaksud orde disini adalah “jumlah faktor”. Misalnya, 15 = 3.5. Artinya 15 adalah orde 2 (genap) dan akan bertanda negatif. Sedangkan 105 = 3.5.7 adalah orde 3 (ganjil) dan akan bertanda positif.

Desain Algoritma

Asumsi 1 : Setiap bilangan pada input adalah bilangan bulat positif.
Asumsi 2 : Setiap bilangan pada input saling koprima (FPB-nya 1) dengan bilangan lainnya.

Siapkan sebuah array dengan ukuran yang cukup untuk menampung semua kombinasi bilangan. Jumlah kombinasi yang mungkin adalah . Dikurangi 1 karena kita tidak menangani kombinasi kosong.

Negasikan setiap bilangan pada input sehingga menjadi bilangan negatif (-).
Kalikan setiap bilangan (negatif) ini dengan semua bilangan lainnya yang ada pada array.
Hasil perkaliannya letakkan di bagian array yang masih kosong.

Catatan : Bagian array yang “baru saja” ditulisi dengan hasil perkalian jangan dibaca. Cukup baca isi array sebelum bilangan (negatif) ini “datang”.

Jika sudah tidak ada lagi bilangan yang ingin dikalikan. Maka letakkan versi awal (versi positif) dari bilangan ini ke dalam tempat yang masih kosong.

Lakukan terus sampai input habis.

Contoh

Kita akan mencari kombinasi dari lengkap dengan inklusi-eksklusi-nya

Ukuran input :
Ukuran array :

Kondisi sebelum input pertama (2) :

• Array : [-1, -1, -1, -1, -1, -1, -1]
• Slot kosong : 1

Proses input pertama (2) :

• Tidak ada elemen sebelumnya.
• Letakkan 2 di slot 1. Sehingga array menjadi [2, -1, -1, -1, -1, -1, -1], slot kosongnya sekarang di 2.

Kondisi sebelum input kedua (3) :

• Array : [2, -1, -1, -1, -1, -1, -1]
• Slot kosong : 2

Proses input kedua (3) :

• Kalikan -3 dengan 2 = -6.
• Letakkan -6 di slot 2. Sehingga array menjadi [2, -6, -1, -1, -1, -1, -1], slot kosongnya sekarang di 3
• Elemen sebelumnya habis.
• Letakkan 3 di slot 3. Sehingga array menjadi [2, -6, 3, -1, -1, -1, -1], slot kosongnya sekarang di 4

Kondisi sebelum input ketiga (5) :

• Array : [2, -6, 3, -1, -1, -1, -1]
• Slot kosong : 4

Proses input ketiga (5) :

• Kalikan -5 dengan 2 = -10.
• Letakkan -10 di slot 4. Sehingga array menjadi [2, -6, 3, -10, -1, -1, -1], slot kosongnya sekarang di 5
• Kalikan -5 dengan -6 = 30.
• Letakkan 30 di slot 5. Sehingga array menjadi [2, -6, 3, -10, 30, -1, -1], slot kosongnya sekarang di 6
• Kalikan -5 dengan 3 = -15.
• Letakkan -15 di slot 6. Sehingga array menjadi [2, -6, 3, -10, 30, -15, -1], slot kosongnya sekarang di 7
• Elemen sebelumnya habis
• Letakkan 5 di slot 7. Sehingga array menjadi [2, -6, 3, -10, 30, -15, 5], tidak ada slot kosong lagi

Input habis

Technical Jibba-Jabba

Pseudocode algoritma Gauss :

Pseudocode algoritma Inklusi-Eksklusi Iteratif :

Pseudocode algoritma Inklusi-Eksklusi Rekursif (Oleh Peter Harjanto) :

Implementasi Java Iteratif :  Ideone , PDF
Implementasi Java Rekursif :  Ideone
Implementasi C++ : sabar, lagi dibuat

Benchmark

Algoritma 1 : Algoritma Konvensional (Brute Force)
Algoritma 2 : Algoritma Gauss + Prinsip Inklusi-Eksklusi (Versi Iteratif)
Algoritma 3 : Algoritma Gauss + Prinsip Inklusi-Eksklusi (Versi Rekursif)
Mesin 1 : Intel Celeron 1.5 GHZ + Windows XP SP3 + Java 1.6.0.13 (Laptop pribadi)
Mesin 2 : Intel(R) Pentium(R) 4 CPU 3.20GHz + Unknown OS + Java 1.6.0.17  (Ideone – Unofficial Information)

Benchmark Algo Konvensional vs Algo Gauss + Inklusi-Eksklusi

Catatan : Algoritma 1 tidak dites di mesin 2 (Ideone) karena mesin 2 hanya mengizinkan program untuk berjalan selama maksimal 15 detik.
Catatan : Algoritma 3 tidak dites karena ide dasarnya sama dengan algoritma 2. Yang membedakan hanya implementasi yang menggunakan teknik rekursif atau iteratif.

Permasalahan 100 dan 99

Problem

Mana yang lebih besar? atau

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. 
2. Untuk bilangan bulat positif dan , jika diketahui , maka

Sekarang, kita asumsikan bahwa , sehingga diharapkan

Sesuai dengan rumus logaritma, kita memperoleh bahwa dan sebaliknya, kita juga memperoleh

Sekarang, pertanyaannya berubah menjadi “Apakah ?” Kita tidak tahu dengan pasti berapa nilai dari , tetapi kita tahu dengan pasti bahwa adalah 2.

Seharusnya – hanya feeling – , nilainya sekitar 1.99xxx.

Yap. nilainya 1.9956351945975499153 di kalkulator.

Sehingga pertidaksamaan bernilai salah dan dengan demikian asumsi awal yang dibuat pun salah. Suatu kontradiksi yang mengakibatkan pernyataan yang benar adalah

Pembahasan (via Bilangan Euler)

Jika kita misalkan dan maka kita peroleh

Bentuk di atas sangat mirip dengan bentuk legendaris .

Dengan memerhatikan bahwa adalah sebuah fungsi yang monoton naik dan konvergen, yakni

• Monoton naik karena

• Konvergen karena . Tes konvergensi via perbandingan rasio

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

atau sederhananya

Dengan demikian

Sebagai akibatnya

Secara umum, kita dapat mengatakan bahwa berlaku untuk atau dalam kelompok bilangan lain (real) pertidaksamaan berlaku dengan syarat dimana adalah bilangan Euler.

Pembahasan (via Binomial Newton)

Jika diketahui dimana

Kita peroleh pertidaksamaan 1:

Lalu, karena , kita peroleh pertidaksamaan 2:

Dengan menggabungkan kedua pertidaksamaan, kita peroleh

Selanjutnya

Sehingga

Dari definisi binomial Newton kita tahu bahwa

Selanjutnya, dengan mengambil , kita peroleh

Setelah dijabarkan kita peroleh

Dengan mengambil asumsi berani, yaitu :

Kita peroleh :

Satu-satunya yang mengganjal pada aljabar pertidaksamaan di atas adalah asumsi berani kita, yaitu .

Secara intuitif jelas sekali bahwa kecepatan “terbang” fungsi kuadratik akan kalah jauh dibanding . 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 berapa, pertidaksamaan berlaku? Pada saat , sisi kiri masih lebih besar dari sisi kanan, yaitu . Akan tetapi pada saat , sisi kiri sudah kalah (dan akan terus kalah) dari sisi kanan, yaitu .

Sehingga pertidaksamaan berlaku untuk

Barisan Bilangan 1 : Deret Aritmatika (Arithmetic Progression)

Deret

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

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

Contoh-contoh deret aritmatika :

• . Deret aritmatika terhingga (finite), yaitu jumlahnya terbatas. Selisih tiap suku dengan suku berikutnya adalah 2.

• . Deret aritmatika terhingga. Selisih tiap suku dengan suku berikutnya adalah 1.

• . Deret aritmatika tak terhingga (infinite), yaitu jumlahnya tidak terbatas. Selisih tiap suku dengan suku berikutnya adalah 1.

• . Deret aritmatika terhingga. Selisih tiap suku dengan suku berikutnya adalah -1.

• . Deret aritmatika tak terhingga. Suku pertamanya adalah 4 dan selisih tiap suku dengan suku berikutnya adalah -3.

• . Deret aritmatika tak terhingga. Suku pertamanya adalah 0 dan selisih tiap suku dengan suku berikutnya adalah 2.5

• . Deret aritmatika tak terhingga. Suku pertamanya adalah dan selisih tiap suku dengan suku berikutnya adalah

• . Deret aritmatika tak terhingga. Suku pertamanya adalah dan selisih tiap suku dengan suku berikutnya adalah .

• . Deret aritmatika terhingga. Suku pertamanya adalah dan selisih tiap suku dengan suku berikutnya adalah .

Perhatikan baik-baik contoh terakhir.

Di dalam matematika, barisan bilangan seringkali dinyatakan dengan dimana , , , … dan . Notasi ini dalam matematika bermakna :

Suku pertama () adalah dan suku ke-n () adalah dimana adalah jarak/selisih antara suatu suku dengan suku berikutnya, yakni jarak antara dengan dimana . Blog mengikuti notasi ini.

Definisi formalnya :

Contoh barisan aritmatika yang lain :

• Deret bilangan cacah : 0, 1, 2, 3, 4, 5 …
  Tak terhingga dengan , dan

• Deret bilangan asli : 1, 2, 3, 4, 5, 6 …
  Tak terhingga dengan , dan .

• Deret bilangan genap : 0, 2, 4, 6, 8, 10,…
  Tak terhingga dengan , dan

• Deret bilangan ganjil : 1, 3, 5, 7, 9, 11, 13, 15, ….
  Tak terhingga dengan , dan

• Deret bilangan kelipatan 2 : 2, 4, 6, 8, 10, 12, 14, 16 … 2n
  Terhingga dengan , dan

• Deret bilangan kelipatan 3 : 3, 6, 9, 12, 15, 18, 21 … 3n
  Terhingga dengan , dan

• Deret bilangan kelipatan 3 : 0, 3, 6, 9, 12, 15, 18, 21 … 3(n-1)
  Terhingga dengan , dan

Sifat-sifat Deret Aritmatik

Perhatikan aljabar di bawah ini :

Kita peroleh sifat pertama dari deret aritmatika, yaitu .

Penjabaran yang lain :

Mengingat

Maka bisa disimpulkan sifat kedua dari deret aritmatika, yaitu

Sifat kedua inilah yang nantinya akan menjadi dasar teori untuk rataan aritmatik (Arithmetic Mean). Sebagai gambaran saja, sifat kedua ini dapat dituliskan menjadi yang dapat diterjemahkan secara statistik : “nilai rata-rata dari dan adalah “.

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

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 :

Dengan demikian kita peroleh rumus untuk menghitung total nilai seluruh suku pada deret aritmatika, yaitu . Dimana :

menyimbolkan jumlah (sum) dari suku-suku pada deret.
menyimbolkan suku pertama pada deret.
menyimbolkan suku terakhir pada deret.
menyimbolkan banyaknya suku pada deret.

Karena deret aritmatika berbentuk maka kita boleh saja meng-asumsikan bahwa ada suku yang letaknya berada di rentang (well-order principle) sehingga deret aritmatika dapat dituliskan sebagai .

Sekarang jika kita pandang secara parsial (sebagian), yakni deret kita mulai dari suku ke-m, maka kita memperoleh deret baru, yaitu .

Ada berapa banyak suku pada deret ini?

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

Berapa jumlah nilai suku-suku pada deret baru ini?

Suku pertama pada deret ini adalah dan suku terakhir adalah . Banyaknya suku ada buah. Sesuai dengan rumus yang tadi kita peroleh, jumlah nilai suku-suku pada deret ini adalah

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 .

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 adalah
2. Nilai rata-rata dari deret adalah
3. Nilai rata-rata dari deret adalah
4. Nilai rata-rata dari deret adalah
5. Nilai rata-rata dari deret adalah
6. Nilai rata-rata dari deret adalah
7. Nilai rata-rata dari deret adalah
8. Nilai rata-rata dari deret adalah

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 :

Jika kita ambil kasus sederhana yaitu deret dengan tiga buah suku , maka .

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

Hal ini menarik perhatian kita karena secara langsung penjabaran di atas menyatakan bahwa

Ingat bahwa di bagian atas dari artikel ini kita telah membahas sifat kedua dari barisan aritmatika, yaitu . Dengan mengambil dan kita peroleh :

Atau dengan menuliskan ke dalam bentuk lain kita peroleh .

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

Mari kita bahas perlahan-lahan.

Misalkan dan . Maka .

Seperti yang sudah kita ketahui melalui sifat kedua dari barisan aritmatik, dan akan memiliki nilai rata-rata yang sama dengan , yaitu suku yang berada di tengah-tengah mereka. Hal ini berlaku umum untuk setiap suku pada barisan aritmatik.

Bagaimana jika tidak habis dibagi 2?

Jika tidak habis dibagi 2, maka suku ke- adalah suku fiktif. Walaupun demikian, konsepnya tidak berubah. Suku fiktif ini secara logis akan berada di tengah-tengah dari dan .

Dengan demikian, fenomena di atas dapat dijelaskan sebagai berikut :

Terlihat jelas bahwa nilai rata-rata dari , dan adalah lagi.

Mari kita perbesar kasusnya dengan mencari rata-rata dari :

Nilai-rata-rata dari adalah , yaitu suku tengah (median) pada deret.

Mari kita lihat kasus parsial dengan mencari rata-rata dari :

Nilai-rata-rata dari adalah , yaitu suku tengah (median) pada deret.

Secara umum, bisa disimpulkan bahwa deret akan memiliki nilai rata-rata yang sama dengan nilai rata-rata dari , yaitu .

Atau, untuk kasus parsial seperti deret , akan memiliki nilai rata-rata yang sama dengan nilai rata-rata dari , yaitu .

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.

Obat Ngantuk

1. Dengan mengambil rentang ,
   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. 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. Carilah rumus suku ke-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. Misalkan adalah sebuah barisan bilangan aritmatik.
   Diketahui dan
   Carilah nilai dimana (American High School Mathematics Examination). Pembahasan ada di sini.
6. Hitunglah nilai dari . Pembahasan ada di sini.
7. Untuk , diketahui tiga buah suku pertama pada barisan aritmatik adalah , dan . Berapakah nilai suku ke-4? Pembahasan ada di sini.
8. Diketahui , dan adalah tiga buah suku berurutan pada sebuah barisan aritmatik. Pembahasan ada di sini.
   Buktikan bahwa , dan juga merupakan tiga buah suku berurutan pada sebuah barisan aritmatik (tidak harus barisan yang sama). Pembahasan ada di sini.
9. Ada berapa banyak nilai sedemikian rupa sehingga habis membagi . (American Mathematics Competition grade). Pembahasan ada di sini.
10. Dalam sebuah barisan aritmatika , diketahui . Jika jarak antar suku satu dengan suku yang lain () adalah sebuah bilangan bulat, berapa nilai minimum agar ? (Introduction to Algebra). Pembahasan ada di sini.
11. Hitunglah nilai dari . Pembahasan ada di sini.
12. Dalam sebuah deret aritmatika, diketahui fakta-fakta berikut :
    1. 
    2. 
    3. Berapakah nilai dari ? Pembahasan ada di sini.
13. 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?