MATH & CS For N0thing, but Fun

MAJALAH

Zer0 O_o

MATH & CS For N0thing, but Fun

EDISI 02 | AGUSTUS 2008

Dalam edisi ini:

Logika

”

Tiga merpati dan dua sarang. Ada paling tidak satu sarang dengan dua mepati

”

Prinsip Induksi devilish trick; jika kamu memberikan satu tanganmu pada si iblis, maka ia akan mendapatkan seluruh tanganmu.

Masalah Geometri

Mau, donk MAJALAH Zer0 nya.

Edisi elektronik MAJALAH Zer0 gratis “Anda bisa mendistribusikan, mengutip sebagian atau seluruh isi MAJALAH secara bebas dengan syarat penambahan rujukan ke MAJALAH Zer0 dalam artikel Anda dan artikel Anda tidak berlisensi komersial.”

Zer0

MAJALAH Zero EDISI 02 | AGUSTUS 2008

3

Pengantar Terima kasih Tuhan, MAJALAH Zer0 edisi kedua Agustus 2008 bisa rilis. Dalam edisi ini akan dibahas pengenalan pemecahan masalah secara matematika. Mulai dari pengenalan pernyataan matematika dan bagaimana cara menanganinya. Pernyataaan matematika merupakan bagian penting dalam matematika karena permainanan matematika secara umum ada seputar otak-atik pernyataan matematika. Kemudian dilanjutkan pada pengenalan dua prinsip ampuh matematika. Pertama adalah prinsip rumah merpati yang ampuh untuk membuktikan pernyataan eksistensi. Dan prinsip induksi yang ampuh untuk membuktikan pernyataan dengan kuantor universal yang dapat dicacah. Sasaran utama tema edisi ini adalah memperlihatkan beberapa teknik pembuktian yang membangun deduksi valid – bukan konstruksi objek – sehingga dihasilkan bukti yang valid pula. Jadi bulan ini akan ada yang bisa dibaca sebagai pengisi waktu luang. Bagi yang tidak ingin sekedar jadi pembaca, kamu bisa ikut berpartisipasi mengirimkan tulisan karyamu sendiri melalui email ke salah satu tim redaksi. Tulisan bisa berupa artikel, atau solusi atas masalah yang diterbitkan pada edisi tertentu, atau masalah baru atau apapun seputar matematika dan ilmu komputer yang menurutmu berharga untuk dibagikan. Selamat menikmati.

Penulis dan penyunting Bernard, [email protected] Johan Gunardi, [email protected]

Blog zer0tointfy.wordpress.com artofmathematics.wordpress.com

Kontributor Ivan Wangsa C.L., [email protected] Raja Octovin Ferry Pranolo


4

Perkenalan dengan Logika dan Pernyataan Matematika Matematika secara umum merupakan ilmu yang bermain-main dengan sistem dan objek yang berkaitan dengannya. Sistem ini dibangun dengan aturan yang telah didefinisikan sebelumnya. Sisanya adalah mempelajari objek dalam sistem tersebut. Suatu sistem tidak jadi dengan sendirinya; aturan yang sesuai sulit untuk didefinisikan. Sehingga sistem dalam matematika tidak tunggal. Idealnya matematikawan selalu mencari sistem yang paling ideal: konsisten dan komplit. Namun Godel berhasil menunjukkan bahwa sistem dalam matematika tidak bisa sekaligus konsisten dan komplit. Ok, lupakan dulu soal itu. Dalam catatan ini kita akan mempelajari pernyataan matematika yang membangun sistem. Sebelum ada sistem didefinisikan dulu objek yang akan ada di sistem itu. Pendefinisian ini tidak perlu dibuktikan relatif terhadap sistem dan dikenal dengan istilah aksioma atau definisi. Sedangkan sifat-sifat yang dapat diturunkan dari aksioma secara umum disebut teorema 1 . Teorema lah yang harus dibuktikan. Teorema ini dibangun oleh pernyataan matematika. Dan dalam pernyataan terkandung logika yang merupakan jantung matematika. Logika merupakan lem yang menyatukan matematika; berawal dari fakta yang sudah diketahui (aksioma) atau suatu hipotesis dan berakhir dengan sesuatu yang baru. Logika adalah ilmu yang mempelajari deduksi valid yang bahan dasarnya bukan bilangan, melainkan pernyataan.

Pernyataan Dalam matematika kalimat pernyataan dibedakan atas: 1. pernyataan terbuka, yaitu pernyataan yang masih bisa bernilai benar atau sebaliknya salah. Contohnya: “Jika x real, maka x2 – 1 = 0.” Pernyataan tersebut benar jika x = 1 atau -1, untuk nilai x lainnya peryataan itu salah. 2. pernyataan tertutup, yaitu pernyataan yang nilai kebenarannya sudah dapat ditentukan benar atau salahnya. Selanjutnya kita akan membahas lebih lanjut tentang pernyataan tertutup. Inilah yang biasanya kita sebut sebagai teorema matematika. Nilai kebenaran pada pernyataan ini adalah salah satu dari benar atau salah, tidak bisa keduanya secara bersamaan. Prinsip nilai kebenaran ini dikenal sebagai Law of Excluded Middle, dan sistem logika yang menganut prinsip ini dikenal sebagai sistem Boolean. Sistem inilah yang biasa kita pakai dalam bahasa alami sehari-hari. Contohnya adalah: “Jika x = 1, maka x2 – 1 = 0” 1

Terkadang disebut juga proposisi, lemma, atau akibtat (corollary). Lemma merupakan “teorema pembantu”, sedangkan akibat merupakan konsekuensi secara cepat dari teorema. Semua istilah berarti sama secara logika.


5

Pernyataan Berkuantor Kebanyakan kalimat matematika melibatkan variabel. Contohnya dari teori pertidaksamaan, Untuk setiap x real berlaku x 2 ≥ 0 . Di sini x adalah variabel bilangan sedangkan real adalah variabel sifat bilangan. Variabel berkenaan dengan objek ini dapat diquantifikasi menjadi dua jenis, yaitu: Kuantor umum (universal) Melibatkan semua atau setiap objek yang dibicarakan. Untuk menyingkat penulisan kuantor ini dinotasikan dengan “∀” dan biasa ditulis “∀: P(x)” yang artinya “untuk setiap x yang bersifat/memenuhi P(x)” dengan P(x) adalah suatu pernyataan yang berkaitan dengan x. Contohnya adalah “Setiap siswa yang tidak hadir di kelas hari ini sedang mengikuti OSN.” “Untuk setiap x real berlaku x 2 ≥ 0 .”

Kalimat ekspresi untuk kuantor ini antara lain: “Untuk setiap x …” “Untuk semua x …” “Diberikan sembarang x …” “Ambil x sembarang …” Kuantor khusus (eksistensial) Melibatkan sebagian atau beberapa objek yang dibicarakan dan dinotasikan dengan “∃”. Biasa ditulis sebagai “∃: P(x)” yang artinya ada x yang bersifat P(x). Ada disini bisa berarti beberapa atau tidak tunggal. Kalimat ekspresi kuantor ini antara lain “Untuk suatu x …” “Ada suatu x …” “Terdapat beberapa x …” Perlu diperhatikan bahwa pernyataan yang dimulai dengan “Untuk setiap …” tidak mengakibatkan eksistensi sesuatu. Pertimbangkan contoh “Setiap unicorn punya tanduk di kepalanya.” Pernyataan ini tidak menyebabkan bahwa unicorn itu ada.

Operasi Logika A. Negasi (ingkaran) Negasi, yang dinotasikan ¬ (atau ~), berarti ingkaran suatu peryataan P. Singkatnya ¬P berarti tidak (bukan) P. Contohnya, pernyataan “Ali menyontek” negasinya adalah “Ali tidak menyontek.” B. Dan (konjungsi) Dinotasikan dengan “∧” dan melibatkan dua pernyataan P dan Q. P ∧ Q (P dan Q) benar jika kedua pernyataan benar.


6

C. Atau (disjungsi) Dinotasikan dengan “∨” dan melibatkan dua pernyataan P dan Q. P ∨ Q (P atau Q) benar jika salah satu pernyataan benar. D. Implikasi Ditulis P ⇒ Q : Jika P maka Q. P disebut hipotesis (syarat perlu) dan Q disebut konklusi atau kesimpulan (syarap cukup). Implikasi bernilai salah jika hipotesis benar tetapi konklusi salah. E. Biimplikasi Ditulis P ⇔ Q : P jika dan hanya jika Q. Biimplikasi bernilai benar bila kedua pernyataan bernilai sama. Untuk mencari tahu nilai kebebaran suatu pernyataan kita dapat membuat tabel kebenaran. Tabel ini mempermudah pencacahan setiap nilai kebenaran yang mungkin untuk masing-masing pernyataan. Tabel kebenaran definisi B sampai E adalah P Q B B B S S B S S

P ∧Q B S S S

P∨ Q B B B S

P⇒Q B S B B

P⇔Q B S S B

Implikasi Pernyataan matematika biasanya berbentuk Jika [hipotesis] maka [kesimpulan]. Atau P ⇒ Q yang ekuivalen dengan ¬P atau Q (bisa dicek dengan mudah menggunakan tabel kebenaran). Jadi jika seseorang berkata, “jika hari tidak hujan maka saya akan datang ke rumahmu.” equivalen, sama saja, jika orang itu berkata, “hari hujan atau saya akan datang ke rumahmu.” Dari implikasi diatas ada tiga bentuk yang perlu diperhatikan o o o

Q ⇒ P disebut konvers dari implikasi ¬P ⇒ ¬Q disebut invers dari implikasi ¬Q ⇒ ¬P disebut kontraposisi dari implikasi


7

Perhatikan bahwa konvers pernyataan P ⇒ Q , yaitu Q ⇒ P tidak selalu benar. Sebagai contoh konvers pernyataan ”Jika x real maka x 2 ≥ 0 , ” adalah “Jika x 2 ≥ 0 maka x real” yang tidak benar. Pernyataan terkondisi yang konversnya juga valid, P ⇒ Q dan Q ⇒ P , merupakan biimplikasi. Jika demikian kita bisa mengatakan bahwa P equivalen secara logika dengan Q. Definisi berbentuk seperti ini. Cotohnya, “sebuah segitiga sama kaki jika dan hanya jika ada dua sisi yang sama panjang.” Aturan berikut memberikan cara tambahan membuat ”implikasi” yang digunakan sebagai langkah pembuktian. o [( P ⇒ Q) ∧ P] ⇒ Q o [( P ⇒ Q) ∧ ¬Q] ⇒ ¬P o [( P ⇒ Q) ∧ (Q ⇒ R )] ⇒ ( P ⇒ R) o ¬Q ⇒ ¬ P

Ketiga aturan di atas merupakan tautologi, karena mereka valid berdasarkan bentuk; tidak tergantung pada nilai kebenaran masing-masing pernyataan. Equivalensi diatas sangat berguna untuk membuktikan suatu pernyataan yang melibatkan implikasi. Demi ilustrasi aturan di atas, perhatikan konstruksi deduksi pada lelucon berikut yang ingin membuktikan bahwa setiap perempuan sama dengan masalah 2 . Karena perempuan identik dengan uang dan waktu yang harus diluangkan untuknya, maka perempuan = waktu x uang. Tetapi waktu adalah uang, sehingga perempuan = uang2. Dan kita tahu bahwa uang adalah akar dari masalah, uang = √masalah. Jadi perempuan = uang2 = (√masalah)2 = masalah. Karena kita mengambil sembarang perempuan, maka setiap perempuan adalah masalah. >:) Dapatkah kamu menerka aturan mana saja yang digunakan? Bagaimana jika kita lihat contoh yang lebih serius. Buktikan bahwa jika kedua akar suatu persamaan kuadrat irasional, maka determinan persamaan kuadrat itu kurang dari nol. Mari kita coba bangun deduksi seperti pada lelucon di atas. Misalkan persamaan kuadrat yang dimaksud adalah y = ax 2 + bx + c . Pertanyaannya adalah bagaimana menggunakan hipotesis kedua akar y irasional untuk sampai pada kesimpulan bahwa determinannya, Δ = b 2 − 4ac , kurang dari nol? Sulit dilakukan. Kalau menemukan situasi seperti ini, untuk menghindari rasa mandek yang berkepanjangan, ada baiknya mencoba memanipulasi pernyataan yang diminta. Dalam hal ini coba kontrapositifnya, Jika Δ ≥ 0 , maka kedua akar y real. 2

Nyatanya ada juga bukti bahwa “Men Are Even Worse Then Evil”, coba deduksikan dari fakta bahwa pria butuh uang, waktu, dan wanita :D


8

Pernyataan di atas lebih mudah dibuktikan. Karena akar-akar y memenuhi x=

−b ± Δ , 2a

dan Δ ≥ 0 , maka diperoleh dua x (mungkin sama) yang real. Terbukti. Ada kalanya masalah berbentuk suatu pertanyaan apakah suatu pernyataan benar. Masalah tipe ini cenderung lebih sulit, karena dihadapkan pada dua pilihan: mencoba membuktikan atau mencari contoh penyangkal. Sebagai contoh: Apakah untuk setiap bilangan asli n, n 2 − n + 41 prima? Setelah kita pertimbangkan beberapa nilai n kecil, ternyata n 2 − n + 41 prima:

Sampai sini kita mungkin akan membuat konjektur (menerka) bahwa n 2 − n + 41 prima untuk setiap bilangan asli n. Dan metode yang terlintas pertama adalah induksi 3 . Namun, usahanya tidak akan membuahkan hasil positif karena ada contoh penyangkal terkecil, yaitu n = 41 yang membuat n 2 − n + 41 komposit. Gagasan pencarian contoh penyangkal adalah mencari suatu kontradiksi, mirip dengan metode pembuktian secara kontradiksi.

Kontradiksi Metode lain pembuktian memanfaatkan logika pernyataan adalah pencapaian kontradiksi. Metode ini termasuk metode pembuktian yang tidak langsung, alias bukti matematikanya tidak dikonstruksi secara langsung. Perhatikan konstruksi tabel kebenaran berikut. P Q B B B S S B S S

¬Q S B S B

P ∧ ¬Q S B S S

P⇒Q B S B B

Tampak bahwa pernyataan A: P ∧ ¬Q merupakan negasi dari B: P ⇒ Q , sehingga bila A salah maka B pasti benar. Inilah inti dari metode kontradiksi: jika diberikan suatu implikasi B, dengan memisalkan P benar dan tidak Q, pernyataan A, maka bila kita berhasil menemukan suatu kontradiksi, artinya A salah, maka kita yakin bahwa B benar. Secara umum kontradiksi yang terjadi bisa dua macam: jika kontradiksi terjadi 3

Dalam edisi ini ada artikel tentang induksi.


9

terhadap asumsi, pernyataan P, maka kita sebut sebagai pembuktian tidak langsung, jika kontradiksi terjadi terhadap sesuatu yang sebelumnya sudah kita yakini kebenarannya, maka kontradiksi ini kita sebut reductio ad absurdum, RAA. Contoh. Buktikan bahwa

2 merupakan bilangan irasional.

Solusi. Kita akan membangun argumentasi secara kontradiksi, jadi misalkan kebalikannya benar, yaitu 2 merupakan bilangan rasional. Karena 2 rasional, a a2 maka ada a, b dengan fpb( a, b ) = 1 sehingga 2 = atau 2 = 2 yang ekuivalen b b 2 2 dengan a = 2b . Berikut ini adalah tiga kontradiksi yang dapat terjadi.

a.

b.

c.

Karena a 2 = 2b 2 maka a 2 genap, sehingga a juga genap atau a = 2k untuk suatu k bulat positif. Kita tulis kembali persamaan a 2 = 2b 2 dengan menyubsitusi a = 2k , sehingga diperoleh (2k ) 2 = 2b 2 atau 4k 2 = 2b 2 atau 2k 2 = b 2 yang mengatakan bahwa b juga genap. Kontradiksi dengan pernyataan bahwa fpb( a, b ) = 1. Kita pandang persamaan a 2 = 2b 2 dengan lebih seksama. Perhatikan bahwa faktor dua pada ruas kanan muncul sebanyak ganjil kali, sedangkan pada ruas kiri akan muncul sebanyak genap kali, sehingga berdasarkan prinsip faktorisasi tunggal persamaan tersebut merupakan suatu kontradiksi. Perhatikan bahwa karena fpb( a, b ) = 1 maka a / b sudah dalam bentuk paling sederhana. Namun, a a (a − b) a 2 − ab 2b 2 − ab b(2b − a ) 2b − a = = = = = . b b( a − b) b ( a − b ) b( a − b) b( a − b) a−b

Persamaan terakhir lebih kecil dari a / b . Kontradiksi. Dari kontradiksi yang terjadi kita dapat mengambil kesimpulan bahwa merupakan bilangan irasional.

2

Dan sekarang beberapa contoh yang mengilustrasikan penarikan kesimpulan. Contoh. Asumsikan dua pernyataan berikut benar:

a. b.

Tidak semua siswa Zer0 College tinggal di Bandung. Semua bobotoh Persib yang tidak tinggal di Bandung bukan siswa Zer0 College.

Apakah a dan b mengakibatkan c.

Tidak semua siswa Zer0 College merupakan bobotoh Persib


10

Solusi. Jawabannya adalah ya. Karena a, maka ada siswa ZC yang tidak tinggal di Bandung. Misalkan siswa itu S. Kita klaim bahwa S bukan bobotoh Persib yang mengakibatkan pernyataan c benar. Misalkan sebaliknya, yaitu S bobotoh Persib. Karena dia tidak tinggal di Bandung, maka dari pernyataan b, S bukan siswa ZC, kontradiksi. Pernyataan c benar. Contoh. Pilihan yang aneh: Dalam sebuah tes zer0 menemukan sebuah pertanyaan pilihan berganda yang tidak terbaca masalahnya, tetapi tertulis, “Jawaban mana yang benar?”. Sedangkan pilihan yang tersedia cukup aneh, yaitu

A. B. C. D. E. F.

Semua pilihan di bawah. Tidak satupun pilihan di bawah. Semua pilihan di atas. Satu pilihan di atas. Tidak satupun pilihan di atas. Tidak satupun pilihan di atas.

Adakah pilihan yang benar? Solusi. Jika A benar maka B-E benar. Karena B benar maka C-E salah. Kontradiksi. Jadi A salah. Karena itu maka C harus salah juga. Akibatnya B juga harus ikut salah. Jadi A-C salah. Hal ini membuat D tidak benar. Sampai sini kita sudah mengonfirmasi bahwa pilihan A-D salah. Karena itu E benar. Bagaimana dengan F? Jika F benar maka A-E salah. Karena A-D salah maka E benar. Kontradiksi. Jadi F salah. Jadi hanya ada satu pilihan yang benar dari masalah pilihan yang aneh ini, yaitu E. Contoh. Empat tersangka suatu kejahatan berhasil diringkus polisi. Keempat tersangka itu masing-masing memberi pernyataan pada polisi,

Alice: Carl yang melakukannya. Bob: Saya tidak melakukannya. Carl: Dave yang melakukannya. Dave: Carl bohong waktu ia berkata saya yang melakukannya. (a) Jika diketahui bahwa tepat satu dari keempat pernyataan yang benar, maka siapa yang melakukannya? (b) Jika diketahui bahwa tepat satu dari keempat pernyataan yang salah, maka siapa yang melakukannya? Solusi. Untuk mempersempit banyaknya kasus yang mungkin terjadi kita mulai dari pernyataan mengenai dirinya sendiri, yaitu Bob. Misalkan Bob bohong, sehingga ialah pelakunya. Jika Alice jujur, maka Carl pelakunya, kontradiksi dengan asumsi bahwa Bob pelakunya. Maka Alice bohong. Sampai sini kita punya hubungan,

Jika Bob bohong, maka Alice bohong. (1)


11

(a) Asumsikan hanya satu yang jujur dan Bob bohong. Carl tidak mungkin jujur karena asumsi bahwa pelakunya adalah Bob. Carl bohong. Maka Dave jujur. Karena pernyataanya tetap konsisten, maka dalam kondisi ini Bob lah pelakunya. (b) Asumsikan hanya satu yang berbohong. Misalkan Alice jujur, maka Carl pelakunya. Berdasarkan (1) Bob jujur. Karena Alice dan Bob jujur, maka salah satu dari Carl dan Dave jujur. Jika Carl yang jujur, maka Dave lah pelakunya. Kontradiksi, sehingga Carl bohong. Maka Dave jujur dan pernyataanya konsisten. Jadi dengan asumsi satu dari keempat pernyataan yang salah (Carl berbohong, sedangkan Alice, Bob, Dave jujur), maka Carl lah pelakunya. Latihan. Tiga konsidi satu bilangan: Misalkan A merupakan bilangan bulat positif. 3A lebih besar dari 35, 7A paling tidak 43, 2A paling banyak 99, A paling tidak 21, dan 5A paling tidak 51. Jika hanya tiga kondisi tentang A yang benar, berapakah A? Latihan. Siswa Mana Yang Menyontek: Pada saat ujian seorang guru memanggil tiga siswa yang dicurigai menyontek, A, B, C. Saat ditanyai diperoleh pernyataan dari masing-masing siswa, yaitu:

A: “C tidak menyontek.” B: “A menyontek.” C: “B menyontek.” Jika yang menyontek bebohong dan yang tidak; berkata jujur, maka pernyataan berikut yang mungkin terjadi adalah A. A dan B menyontek B. A dan C menyontek C. B dan C menyontek D. Hanya C yang menyontek E. Hanya A yang tidak menyontek. Sebagai penutup, kita kembali pada pembahasan sistem yang komplit dan konsisten. Suatu sistem yang menuju ke arah kokoh dan komplit secara logika adalah Principia Mathematica oleh Whitehead dan Russell. Dalam principia setiap matematika diturunkan menggunakan bahasa formal untuk menghindari keambiguan. Namun, Russell malah menemukan paradoks dan menunjukkan bahwa principia tidak konsisten. Paradoks ini dikenal sebagai Barber Paradox, paradoks tukang cukur. Paradoks tukang cukur: Dalam sebuah kota ada seorang tukang cukur (pria) yang mencukur kumis setiap pria di kota itu yang tidak mencukur kumisnya sendiri. Apakah tukang cukur itu mencukur kumisnya sendiri?

Happy puzzling, forever –Nobuyuki Yoshigahara


12

Prinsip Rumah Merpati Dapatkah kamu membuktikan bahwa ada paling tidak dua orang penduduk di Bandung yang banyaknya rambut di kepala sama? Pertanyaan seperti ini dan masalah serupa yang lebih serius dapat dijawab dengan melibatkan suatu prinsip kuno yang ampuh dan dikenal sebagai prinsip rumah merpati. Prinsip ini merupakan prinsip yang sangat jelas dan sederhana, tetapi aplikasinya bisa secara tidak terduga mengejutkan. Pada catatan ini kita akan telusuri prinsip dan aplikasinya. Prinsip Rumah Merpati Jika k + 1 merpati dimasukkan ke dalam k rumah, maka ada satu rumah yang berisi paling tidak dua merpati.

Ok, prinsip di atas sudah jelas dan tidak ada yang harus dibuktikan. Untuk menyingkat kita akan sebut prinsip ini sebagai prm. Di Barat prm dikenal sebagai pigeonhole principle atau Dirichlet drawer principle. Nama Dirichlet muncul karena dipercaya pertama kali dinyatakan oleh matematikawan Jerman bernama Gustav Lejeune Dirichlet pada tahun 1834. Sebagai pemanasan selidiki penerapan prm pada lima contoh di bawah ini. 1. Diantara tiga orang ada dua yang berjenis kelamin sama. 2. Berapa banyak orang dibutuhkan untuk yakin bahwa ada dua orang yang berulang tahun pada tanggal yang sama? 3. Jika kn + 1 kelereng didistribusika ke dalam n kotak, maka satu kotak akan berisi paling tidak k + 1 kelereng. Ini merupakan bentuk prm yang lebih umum. (prm yang ditulis disini diperoleh untuk k = 1). 4. Sebuah garis l di dalam bidang melalui sisi-sisi segitiga ABC dengan tidak melewati titik sudutnya. Buktikan garis itu tidak akan melewati ketiga sisi segitiga. 5. Misalkan dalam sebuah laci ada kaos kaki: 10 hitam dan 12 biru yang tersebar secara acak. Misalkan kamu ingin mendapatkan satu pasang kaos kaki dengan warna sama, tetapi kamu hanya bisa sekali ambil tanpa melihat isi laci. Cukup berapa kaos kaki yang akan kamu ambil?

Sekilas Logika: 10 koin dan 3 gelas

Ada sepuluh koin dan tiga gelas. Bisakah kamu memasukkan setiap koin kedalam gelas sehingga dalam setiap gelas ada koin yang jumlahnya ganjil?


13

Aplikasi prm yang bersifat rekreasi Salah satu hal yang menarik dari prinsip rumah merpati yang sederhana itu adalah aplikasinya yang dapat muncul di mana saja. Konon Erdos pernah mengundang makan siang seorang anak ajaib, Lajos Posa. Di tengah makan siang Erdos bertanya ”Bagaimana kamu membuktikan bahwa jika kita mengambil n + 1 bilangan dari himpunan bilangan 1, 2, 3, ..., 2n, maka ada dua bilangan yang koprima?” Sesaat pertanyaan tersebut tidak cukup jelas. Namun, argumentasi Lajos yang dikemukakan sesaat setelah pertanyaan selesai membuat pertanyaan Erdos lebih jelas: dalam n + 1 bilangan yang terpilih pasti ada dua bilangan yang berbeda satu alias saling berurutan dan dua bilangan tersebut koprima. Masalah di bawah ini mirip dengan masalah sebelumnya: Dari himpunan bilangan bulat 1, 2, 3, ..., 2n, ambil n + 1 bilangan, sebutlah himpunan ini A. Maka selalu ada dua bilangan di A sehingga bilangan yang satu membagi bilangan yang lain. Klaim ini tidak jelas. Dan Lajos berhasil membuktikannya dengan mengaplikasikan prinsip rumah merpati. Tulis setiap bilangan a ∈ A dalam bentuk a = 2k m dengan m bilangan ganjil antara 1 dan 2n – 1. Karena ada n + 1 bilangan dalam A, sedangkan hanya ada sebanyak n bagian ganjil yang mungkin, maka ada dua bilangan dalam A yang bagian ganjilnya sama. Maka bilangan yang satu merupakan kelipatan bilangan lainnya. Untuk dapat mengaplikasikan prm, kita harus tahu tipe masalah. Prm merupakan prinsip yang sangat ampuh untuk menangani masalah atau teorema yang berkaitan dengan eksistensi. Bagian yang paling sulit adalah menemukan rumah dan merpati yang sesuai. Untuk menambah mengalaman dan mengasah intuisi tentang prm telusuri contoh-contoh berikut. Latihan si master catur. Seorang master catur punya 77 hari untuk latihan sebelum turnamen dimulai. Untuk itu ia menerapkan program latihan: setiap hari paling tidak bermain catur sekali, tetapi secara keseluruhan banyaknya permainan tidak lebih dari 132. Buktikan bahwa ada barisan hari berturut-turut disaat ia bermain catur sebanyak tepat 21 kali. Sket. Masalah ini berbau prm, tetapi rumah dan merpatinya tidak jelas. Kita harus mencoba menghubungkan bilangan-bilangan yang diberikan untuk membentuk rumah dan merpati yang sesuai. Pertama, ada 77 hari untuk latihan dan setiap hari minimal satu permainan. Kedua ada 132, yaitu banyaknya seluruh permainan maksimal dalam latihan. Bagaimana jika kita memisalkan ai sebagai banyaknya permainan yang telah


14

dilakukan sampai hari ke-i dengan i = 1, 2, …, 77? Jika demikian maka a1 paling tidak 1, a2 paling tidak 2, dst, sampai a77 paling banyak 132. Secara matematika 1 ≤ a1 < a2 < ... < a77 ≤ 132 . Dan ada 21, banyaknya permainan yang dilakukan selama beberapa hari berturutturut. Mendorong untuk menambahkan setiap ai dengan 21. Dan perhatikan bahwa 132 + 21 = 153 = 2·77 - 1. Sekarang kita punya rumah dan merpati yang sesuai. Bukti. Misalkan ai banyaknya permainan yang telah dilakukan sampai hari ke-i dengan i = 1, 2, …, 77. Maka 1 ≤ a1 < a2 < ... < a77 ≤ 132 , dan 22 ≤ a1 + 21 < a2 + 21 < ... < a77 + 21 ≤ 153 . Ada 153 bilangan (rumah), tetapi merpatinya, a1 , a2 ,..., a77 , a1 + 21,..., a77 + 21 , ada 154. Akibatnya ada dua merpati yang berrumah sama. Maka ada i, j, sehingga ai = a j + 21 . Dengan kata lain pada hari ke-j+1, j+2, …, i, si master catur bermain

catur tepat 21 kali. Blok Yang Habis Dibagi n – dari Erdos pada Marta Sved. Misalkan kita tulis secara acak suatu barisan bilangan bulat yang terdiri dari n suku, maka terdapat suatu blok suku-suku yang berurutan yang jumlahnya habis dibagi n. Contohnya, kita bangun secara acak barisan dengan 7 suku: 22, 5, 89, 4, 94, 123, 44. Perhatikan bahwa terdapat suatu blok: 5, 89, 4 yang jumlahnya 98, habis dibagi 7. Buktikan hasil ini. Bukti. Misalkan barisan itu a1 , a2 ,...an . Pandang n penjumlahan

s1 = a1 , s2 = a1 + a2 ,..., sn = a1 + a2 + ... + an . Jika dalam barisan di atas ada suku yang habis di bagi n, pembuktian selesai. Jika tidak, maka paling ekstrim setiap suku sisa pembagiannya berbeda modulo n. Tetapi, karena hanya ada n – 1 sisa yang mungkin, maka ada dua suku yang sisanya sama, misalkan s p dan sq dengan p > q. Maka selisihnya pasti habis dibagi n,

s p − sq = aq +1 + aq + 2 + ... + a p . Dan kita telah mendapatkan blok yang habis dibagi n. Prm dan teori bilangan. Misalkan A adalah himpunan dua puluh bilangan berbeda yang dipilih dari himpunan B = {1, 4, 7, …, 100}. Buktikan bahwa ada dua anggota A berbeda yang jumlahnya 104.


15

Bukti. Pertimbangkan himpunan bilangan C,

C = {(4,100), (7,97),..., (3 ⋅17 − 2 = 49,3 ⋅19 − 2 = 54)} , Himpunan semua pasangan yang jumlahnya 104 yang anggotanya diambil dari B. Terlihat bahwa ada tujuh belas anggota C. Ambil salah satu bilangan dari setiap pasangan di C, tambahkan satu dan 52 (dua bilangan di B yang tidak ada di C) untuk membentuk A. Karena baru ada sembilan belas anggota, kita harus mengambil salah satu bilangan di C. Apapun bilangan itu, pasangannya sudah ada di A dan jumlahnya 104. Terbukti. Fibonacci dengan n nol. Buktikan bahwa ada bilangan Fibonacci yang berakhir dengan n nol. Bukti. Suatu nilai ap berakhir dengan n nol jika ia habis dibagi 10n atau jika a p ≡ 0(mod10n ) . Pertimbangkan barisan Fibonacci dalam modulo 10n, sehingga kita

akan membuktikan bahwa nilai nol muncul dalam barisan itu. Ambil 102n + 1 nilai barisan Fibonacci, a1 , a2 ,...(mod10n ) . Dalam barisan itu terbentuk 102n pasangan, (a1 , a2 ), (a2 , a3 ),... , tetapi pasangan (0,0) tidak akan muncul, sehingga pasangan yang mungkin muncul ada sebanyak 102n – 1. Jadi ada pasangan yang berulang dan barisan itu periodic dengan panjang maksimum 102n – 1. Seperti masalah sebelumnya pasangan yang mungkin muncul pertama kali adalah (1,1). 1,1, 2,3,5,..., a p ,1,1 ÅperiodeÆ Maka a p = 1 − 1 = 0(mod10n ) . Jadi ada bilangan Fibonacci yang berakhir dengan n nol, nyatanya bilangan itu merupakan bilangan di akhir periode. Pemangkatan bilangan. Misalkan a bilangan yang relatif prima dengan 2 dan 5. Buktikan bahwa untuk suatu n ada bilangan hasil pemangkatan a yang berakhir dengan 000..001 (n dijit). Bukti. Pertimbangkan 10n nilai hasil pemangkatan a, n

a, a 2 , a 3 ,..., a10 .

Ambil masing-masing sisa pembagian modulo 10n. perhatikan bahwa nilai 0 tidak mungkin muncul karena a relatif prima terhadap 10. Maka hanya ada (10n – 1) nilai sisa yang mungkin, 1,2,3,…,10n – 1. Jadi ada dua nilai, a i , a k (i < k ) , yang bersisa sama, sehingga selisih mereka akan habis dibagi 10n:


16

10n | a k − a i ⇔ 10n | a i (a k −i − 1) Karena gcd(10n , a i ) = 1 , maka 10n | a k −i − 1 atau a k −i − 1 = x ⋅10n atau a k −i = x ⋅10n + 1 . Jadi a k −i berakhir dengan 000..001 (n dijit). Pengubinan. Di dalam suatu ruangan yang luasnya 5 akan dipasang 9 ubin yang masing-masing luasnya 1, tapi bentuknya beragam. Buktikan bahwa ada dua ubin yang saling tumpang-tindih seluas paling tidak 1/9. Bukti. Misalkan setiap pasangan ubin saling tumpang-tindih seluas paling tidak 1/9. Kita perhatikan berapa banyak sisa luas yang belum tertutup pada setiap pemasangan ubin. Ubin pertama akan menutup seluas 1 atau 9/9. Ubin ke-2, ke-3, … dan ke-9 akan menutup seluas lebih dari 8/9,7/9,…,1/9. karena 9/9 + 8/9 + … + 1/9 = 5, kesembilan ubin akan menutupi ruangan seluas lebih dari lima. Kontradiksi.

Prm pada bilangan real. Buktikan bahwa diantara tujuh bilangan real y1 , y2 ,..., y7 , ada dua, yi dan y j , sehingga 0≤

yi − y j 1 + yi y j

≤

3 . [CMO 1984] 3

Sket. Sekarang kita coba mengaplikasikan prm pada objek bilangan real. Ekspresi di tengah tampak seperti tan(a − b) . Karena pada selang antara − π 2 dan π 2 fungsi tan monoton naik, maka kita bisa memisalkan yn = tan xn , n = 1, 2,..., 7 . yn berada

dalam selang antara −∞ dan ∞ , sedangkan xn antara − π 2 dan π 2 . Jika kita partisi 4 selang xn menjadi 6 sub-interval dengan panjang masing-maing π 6 , maka berdasarkan prm dari tujuh xn ada dua yang berada pada selang yang sama, sehingga selisihnya berada dalam selang antara 0 dan π 6 . Kita tinggal balik langkahnya untuk membuktikan masalah. Bukti. Misalkan yn = tan xn , n = 1, 2,..., 7 . Berdasarkan prm dari tujuh x dalam selang antara − π 2 dan π 2 ada dua xi dan x j , sehingga 0 ≤ xi − x j ≤

π 6

.

Karena fungsi tangen monoton naik, maka

4

Partisi adalah membagi-bagi suatu himpunan menjadi sub-himpunan yang tak kosang dan membangun himpunan itu.


17

0 ≤ tan( xi − x j ) ≤ tan 0 ≤

Jadi ada yi dan y j , sehingga 0 ≤

tan xi − tan x j 1 + tan xi x j

yi − y j 1 + yi y j

≤

π 6 ≤ tan

π 6

.

3 . 3

Objek Geometri Menarik ketika prm dapat diaplikasikan pada masalah dengan objek geometri. Di sini kita mencoba membuat rumah dan merpati yang berupa objek geometri. Sebuah sasaran berbentuk segitiga sama sisi dengan sisi dua. (a) jika sasaran itu ditembak lima kali, maka ada dua lubang dengan jarak paling besar satu. (b) jika sasaran ditembak 17 kali, paling tidak berapa jarak maksimum dua lubang di sasaran itu? Solusi. (a). untuk dapat menerapkan prm, kita butuh merpati dan rumahnya. Yang menjadi masalah adalah kedua objek yang diperlukan tidak terlihat jelas. Tapi, perhatikan objek yang dimunculkan pada masalah ini, yaitu sasaran dan lubangnya. Lubang-lubang pada sasaran tentu saja berdistribusi secara acak. Yang perlu dilakukan sekarang adalah membuat ‘rumah’ sehingga bagaimanapun distribusi lubang di sasaran pasti ada dua lubang pada rumah yang sama dan berjarak paling besar satu. Pas! Bagi saja sasaran tersebut menjadi empat daerah yang luasnya sama. Masing-masing daerah itu berberbentuk segitiga sama sisi dengan sisi satu. Sekarang baru bisa menerapkan prm. Jika sasaran yang sudah dibagi menjadi empat daerah itu ditembak empat kali, maka menurut prm, ada dua lubang yang berada pada daerah segitiga sama sisi kecil yang panjang sisinya satu, sehingga jarak maksimum kedua lubang itu adalah satu.

(b). masalah pada bagian ini merupakan modifikasi masalah sebelumnya. Jika sasaran ditembak tujuh belas kali maka kita harus membuat enam belas rumah di sasaran. Dapatkah ini terjadi? Karena sasaran berbentuk segitiga sama sisi maka tentu saja kita dapat membaginya menjadi enam belas daerah yang kongruen, berbentuk segitiga sama sisi dengan sisi 1/8. Setelah prm diterapkan maka paling tidak ada dua lubang yang jarak maksimumnya 1/8. Diberikan sepuluh titik di dalam sebuah lingkaran berdiameter lima. Buktikan ada dua titik yang jaraknya kurang dari dua. Bukti. Masalah ini mirip masalah sebelumnya. Bedanya masalah ini lebih ditekankan pada bagaimana kita membuat rumah-rumah di dalam lingkaran. Kalau kita ingin membagi daerah di dalam lingkaran menjadi sembilan daerah yang sama, kita akan


18

kesulitan. Kita harus menemukan cara lain membuat rumah agar prm dapat diterapkan. Karena kita ingin agar ada dua titik yang jarak maksimumnya kurang dari dua, kita coba membuat daerah berbentuk lingkaran dengan radius satu dari titik pusat lingkaran utama. Tugas kita sekarang adalah membagi bagian antara lingkaran besar dan lingkaran kecil menjadi delapan daerah, demi kemudahan, yang sama. Jika dua titik ada di dalam salah satu dari daerah ini maka jarak maksimumnya adalah 1.5 atau kurang dari 2. Dengan menerapkan prm, masalah ini selesai. Perhatikan bahwa masalah ini tidak lebih tegas dari masalah sebelumnya, di sini kita hanya harus mengarahkan agar ada dua titik yang jaraknya kurang dari dua sehingga kita tidak lagi perlu membuat rumah-rumah yang kongruen satu sama lain. Diberikan sembilan titik didalam sebuah persegi unit, buktikan bahwa ada tiga titik yang membentuk sebuah segitiga yang luasnya tidak melebihi 1/8. [CMO] Solusi. Bagi persegi itu menjadi empat persegi kongruen. Kotak-kotak ini adalah rumahnya. Perhatikan bahwa 9 = 2 x 4 + 1 titik jika disebarkan di persegi maka ada paling tidak 3 = 2 + 1 titik yang berada di kotak yang sama. Target kita selanjutnya adalah menunjukkan bahwa luas segitiga di dalam kotak tidak melebihi setengah luas persegi unit = 1/8. Kita ingat kembali bahwa luas segitiga adalah (alas x tinggi)/2 dengan alas dan tinggi saling tegak lurus. Maka luas segitiga maksimum dalam kotak adalah ketika alas dan tingginya adalah dua sisi yang saling tegak lurus kotak itu yang panjangnya ½. Jadi luas maksimum segitiga dalam kotak adalah 1/8.

Latihan 1. Suatu papan catur berukuran 3 x 7 setiap perseginya akan diwarnai hitam atau putih. Buktikan bahwa untuk bagaimanapun pewarnaannya papan itu mengandung sebuah persegi panjang sehingga keempat persegi di sudut berwarna sama. (cacah pewarnaan yang mungkin untuk papan berukuran 3 x 1) 2. Buktikan bahwa dua dari 70 bulat positif berbeda ≤ 200 selisihnya 4, 5, atau 9. (tambahkan ke-70 bilangan dengan 4, 5, 9: pertimbangkan 210 bilangan yang terbentuk) 3. Dua titik dari 6 titik yang disebarkan pada persegi panjang 3 x 4 jaraknya ≤ 5 . 4. Buktikan bahwa diantara 13 bilangan real ada dua, x dan y, sehingga | x − y |≤ (2 − 3) |1 + xy | . (pertimbangkan identitas trigonometri)

Aplikasi Teori dalam matematika diskrit yang sedang berkembang pesat karena aplikasinya pada ilmu komputer yang lahir akibat penerapan prm adalah teori Ramsey. Teori ini bermula dari masalah sederhana


19

“Diantara enam orang buktikan bahwa ada tiga orang yang saling mengenal atau tidak saling kenal.” Erdos dan Szekeres menyuguhkan teorema menarik dalam papernya tentang masalah Ramsey: Untuk n ≥ ( p − 1)(q − 1) + 1 setiap barisan sebanyak n bilangan bulat mengandung subbarisan yang monoton naik dengan panjang p atau sub-barisan yang monoton turun dengan panjang q. Dalam ilmu komputer prm muncul secara alami pada masalah tabel hash. Tumbukan dalam tabel hash tidak dapat dihindari karena banyaknya kunci yang mungkin melebihi batas kapasitas suatu array. Untuk mengatasinya didefinisikan perumuman prm yang bersifat probabilistik. Ups.. topik ini diluar tema sekarang, jadi tunggu saja barangkali akan diungkap di MAJALAH Zer0.

Sekilas Logika: Banyaknya binatang peliharaan

Zer0 punya binatang peliharaan. Semua peliharaannya kucing, kecuali dua yang bukan. Semuanya juga anjing, kecuali dua yang bukan. Dan Semuanya juga merpati, kecuali dua yang bukan. Berapa banyaknya binatang peliharaan Zer0?


20

Prinsip Pencarian Pola dan Induksi Bagaimana kita membuktikan suatu pernyataan yang melibatkan suatu bilangan asli sebagai pijakan? Seperti: hasil kali dua bilangan asli berurutan habis dibagi dua. Secara alamiah kita akan mencacah beberapa bilangan mulai dari bilangan terkecil yang mungkin sebagai langkah pertama untuk membuktikan proposisi itu. Dalam hal ini kita dapat meyakinkan diri bahwa, dua bilangan asli berurutan pertama adalah 1, 2 dan hasil kali mereka habis dibagi 2, selanjutnya adalah 2,3 dan jelas habis dibagi 2, karena hasil kalinya punya factor 2. Mungkin langkah selanjutnya adalah mengambil bilangan asli yang cukup besar dan mengalikannya dengan bilangan asli setelahnya, misalnya 23, 24 hasil kalinya jelas habis dibagi 2, karena 24 habis dibagi dua. Kita tidak bisa menyimpulkan bahwa pernyataan berkuantor universal seperti di atas dengan hanya menunjukkan beberapa contoh saja, sekalipun contoh itu melibatkan bilangan yang besar. Masalah utamanya tetap bagaimana membuktikan bahwa memang benar hasil kali dua bilangan asli berurutan selalu habis dibagi 2. Buktinya sudah didepan mata, cukup menyadari bahwa setiap dua bilangan berurutan salah satunya pasti genap, sehingga hasil kali mereka selalu genap. Namun, banyak masalah yang melibatkan bilangan asli sebagai pijakan solusinya tidak didepan mata. Metoda yang kita lakukan tadi bisa diterapkan untuk perhitungan. Perhitungan seperti ini membuat G. Peano membangun suatu aksioma tentang sistem bilangan asli. Aksioma inilah yang menjadi dasar prinsip induksi, yaitu Aksioma Peano: a. Setiap n ∈ ` punya tepat sebuah penerus n* ∈ ` . b. n ≠ m berakibat n* ≠ m * . c. Ada sebuah elemen, dinotasikan 1, di ` sehingga 1 ≠ n * untuk setiap n ∈ ` . d. Jika S ⊂ ` memenuhi: 1 ∈ S (kasus basis), dan n ∈ S berakibat n* ∈ S (langkah induksi) maka S = ` .

Sebagai ilustrasi, misalkan seorang ibu mempunyai n anak. Ia ingin memberikan setiap anaknya sebuah permen, anak pertama ia beri satu permen, lalu ia membuat aturan: jika anak ke-n mendapat permen maka anak ke-(n+1) juga mendapat permen. Jika aturan si ibu kita terapkan, maka kita mendapatkan serentetan peristiwa, o o o o o

Anak pertama mendapat permen, Karena aturan si ibu maka anak kedua mendapat permen, Karena anak kedua mendapat permen maka anak ketiga juga mendapat permen, (begitu seterusnya sampai akhirnya) Anak terakhir mendapat permen karena anak kedua sebelum terakhir dapat.


21

Berdasarkan prinsip ini maka kita bisa katakan bahwa si ibu telah memberi satu permen pada setiap anaknya. Prinsip ini juga bisa diilustrasikan sebagai gerak jatuhnya domino yang diurutkan berdiri: jika domino pertama jatuh, ia akan membuat domino setelahnya jatuh, karenanya domino ketiga ikut jatuh, begitu seterusnya, sampai domino terakhir jatuh. Matematikawan menemukan prinsip ini sangat membangun, sehingga ada yang mengangapnya sebagai suatu aksioma, lainnya menganggap sebagai suatu proposisi yang dapat dibuktikan kebenarannya. Aksioma peano poin c dan d, merupakan prinsip induksi. Jika kita menganut aksioma Peano maka kita memegang prinsip induksi sebagai suatu aksioma. Berdasarkan aksioma ini kita dapat membuktikan sifat terurut rapi bilangan asli, yaitu setiap himpunan bagian bilangan asli tak kosong punya anggota terkecil. Dari sini kita bisa membuktika sifat Archimedes yang menyatakan bahwa untuk setiap x > 0, tidak ada y yang melebihi setiap bulat kelipatan x. Sebaliknya jika sifat terurut rapi dan sifat Archimedes benar maka kita bisa membuktikan prinsip induksi. Sebelumnya kita nyatakan kembali prinsip induksi, Prinsip Induksi. Misalkan P(n) adalah suatu pernyataan mengenai n ∈ ` . Misalkan pula i. P (1) benar (kasus basis) dan ii. untuk setiap k ∈ ` berlaku: jika P (k ) benar, maka P (k + 1) (langkah induksi), maka P(n) benar untuk setiap n ∈ ` .

Menggunakan Induksi Induksi merupakan metoda pembuktian yang ampuh dan aplikasinya sangat terasa dalam penerapan ilmu komputer. Prinsip ini dapat membuktikan suatu pernyataan yang berkaitan dengan bilangan asli, tetapi tidak sampai pada tahap menemukan. Polya mengatakan bahwa metoda ini merupakan devilish trick; jika kamu memberikan satu tanganmu pada si iblis, maka ia akan mendapatkan seluruh tanganmu. Mari kita terapkan metoda ini pada contoh klasik dan melihat betapa devilish-nya metoda ini. Contoh 1. Untuk setiap n ∈ ` berlaku:

1 + 2 + 3 + ... + n =

n(n + 1) . 2


22

Sket. Masalah seperti inilah yang cocok dibuktikan dengan prinsip induksi; ada suatu pernyataan yang berkaitan dengan bilangan asli. Misalkan pernyataan itu kita sebut P(n) dan tidak lain adalah "1 + 2 + 3 + ... + n = n(n + 1) 2" , yaitu jumlah n bilangan asli pertama, kita akan membuktikan bahwa P(n) benar untuk setiap bilangan asli n. Yang pertama harus kita tunjukkan adalah kebenaran kasus basis, dalam hal ini n = 1. P (1) tidak lain adalah penjumlahan 1 bilangan asli pertama, yaitu 1, tetapi 1(1 + 1) 2 = 1 . Sampai sini kita telah menunjukkan kebenaran P (1) . Langkah selanjutnya adalah mengasumsikan bahwa P (n) untuk setiap n asli, dan perlihatkan P (n + 1) benar, yaitu bahwa asusmsi ini berakibat "1 + 2 + 3 + ... + n + (n + 1) = (n + 1)(n + 2) 2" . Dengan perbekal ini jika kita berangkat dari ruas kiri P(n + 1) dan mengaplikasikan asusmsi P (n) benar maka kita harus sampai pada ruas kanan P (n + 1) . Sekarang kita asumsikan P( n) , yaitu berlaku hubungan 1 + 2 + 3 + ... + n = n(n + 1) 2 , langkah ini merupakan langkah induksi dikenal juga sebagai asumsi induki. Lalu kita hitung jumlah n + 1 bilangan asli pertama, n(n + 1) + (n + 1), karena asumsi induksi 2 n(n + 1) + 2(n + 1) = 2 (n + 1)(n + 2) . = 2

1 + 2 + 3 + ... + n + (n + 1) =

Dari perhitungan diatas terlihat bahwa P (n) benar berakibat P (n + 1) benar, sehingga berdasarkan prinsip induksi P(n) benar untuk setiap bilangan asli n atau (kita nyatakan kembali masalah pembuktian kita) untuk setiap n ∈ ` berlaku: n(n + 1) . 1 + 2 + 3 + ... + n = 2 Sebelum membuktikan teorema pada contoh 1 dengan rapi, kita lihat bahwa alur pembuktiannya cukup sederhana dengan mengaplikasikan prinsip induksi. Namun, masalah yang lebih rumit pun, jika kita ingin membuktikannya secara induksi, mempunyai alur pembuktian yang sama yang dapat kita rinci sebagai, 1. Nyatakan bahwa bukti akan dilakukan secara induksi. Hal ini dilakukan supaya kita bisa dengan cepat mengilustrasikan secara kasar alur pembuktian. 2. Definisikan P(n) yang diperlukan. Definisinya bisa dilakukan secara implisit atau eksplisit yang penting kita tahu suatu pernyataan P yang berkaitan dengan n. langkah mengasumsikan bahwa P(n) benar untuk setiap n, dikenal sebagai asumsi atau hipotesis induksi. 3. Buktikan bahwa P (1) benar. Langkah ini dikenal sebagai langkah atau kasus basis.


23

4. Buktikan bahwa P (n) berakibat P (n + 1) . Langkah ini dikenal sebagai langkah induksi. Langkah ini merupakan langkah yang tersulit karena berdasarkan asumsi P(n) kita harus tunjukkan bahwa P(n + 1) juga benar. 5. Kesimpulan induksi. Pada langkah ini kita cukup menyatakan kembali bahwa secara induksi kita telah membuktikan bahwa P (n) benar untuk setiap bilangan asli n. Pernyataannya bisa dilakukan secara implisit atau eksplisit, kebanyakan yang sudah terbiasa menyatakannya secara implisit. Pada pembuktian formal kita tidak perlu menunjukkan setiap ide dan hasil kotretan, cukup alur dan perhitungan seperlunya. Bukti formal teorema pada contoh 1 adalah seperti ditunjukkan berikut. Bukti. Kita akan menggunakan induksi. Misalkan P (n) adalah pernyataan bahwa n(n + 1) . Untuk kasus n = 1 kita peroleh untuk setiap n ∈ ` berlaku 1 + 2 + 3 + ... + n = 2 bahwa 1 = 1(1 + 1) 2 , sehingga P (1) benar. Asumsikan bahwa P (n) benar untuk n bilangan asli sembarang. Karena n(n + 1) 1 + 2 + 3 + ... + n + (n + 1) = + (n + 1), karena asumsi induksi 2 (n + 1)(n + 2) = , 2 maka P(n + 1) benar. Jadi terbukti secara induksi bahwa untuk setiap n ∈ ` berlaku

1 + 2 + 3 + ... + n =

n(n + 1) . 2

Contoh 2. Untuk setiap bilangan asli n, 3 | n3 − n . Sket. Kita akan coba membuktikan secara induksi. Kasus basis biasanya merupakan langkah yang trivial, tetapi harus tetap ditunjukkan. Untuk n = 1 kita peroleh 13 − 1 = 0 yang habis dibagi tiga. Pemilihan asumsi induksi, P(n) , merupakan langkah yang cukup sulit karena harus disesuaikan dengan keadaan P (n + 1) . Secara alami untuk masalah ini kita akan memilih P(n) , pernyataan bahwa 3 | n3 − n untuk setiap bilangan asli n. Mari kita lihat bagaimana P(n + 1) , 3 | (n + 1)3 − (n + 1) . Sekarang masalahnya adalah bagaimana menunjukkan 3 | (n + 1)3 − (n + 1) , dengan asumsi bahwa 3 | n3 − n . Kita akan coba mengekspansi bentuk (n + 1)3 − (n + 1) pada P(n + 1) ,

(n + 1)3 − (n + 1) = n3 + 3n 2 + 3n + 1 − n − 1 = n3 + 3n 2 + 2n.


24

Sampai sini mungkin kita akan stak. Tapi tunggu dulu, persamaan terakhir sangat mengintimidasi, pada persamaan pertama sudah muncul bentuk n3 − n pada P(n) dan bila dikelompokkan berdasarkan bentuk ini, (n + 1)3 − (n + 1) = n3 − n + 3(n 2 + n) . Aha! Karena n3 − n habis dibagi 3 dan jelas bahwa 3(n 2 + n) habis dibagi 3 maka, secara keseluruhan (n + 1)3 − (n + 1) habis dibabagi 3 atau 3 | (n + 1)3 − (n + 1) . Sampai sini kita bisa menyusun bukti formal, seperti, Bukti. Akan dibuktikan secara induksi. Untuk kasus n = 1 jelas bahwa 3 | 0 = 13 − 1 . Asumsikan bahwa 3 | n3 − n untuk suatu n bilangan asli sembarang.

[alternatif langkah induksi I] 3 | n3 − n ⇒ 3 | (n3 − n) + 3(n 2 + n) ⇒ 3 | n3 + 3n 2 + 3n + 1 − n − 1 ⇒ 3 | (n + 1)3 − (n + 1). Implikasi pertama berlaku karena 3 | 3(n 2 + n) , sedangkan implikasi kedua dan ketiga hanya merupakan manipulasi aljabar. [alternatif langkah induksi II] Kita akan berangkat dari bilangan ke-(n + 1) dari suatu bilangan berbentuk n3 − n . (n + 1)3 − (n + 1) = n3 + 3n 2 + 3n + 1 − n − 1 = (n3 − n) + 3(n 2 + n).

Karena 3 | n3 − n berdasarkan asumsi induksi dan jelas bahwa 3 | 3(n 2 + n) , maka 3 | (n + 1)3 − (n + 1) . Jadi secara induksi terbukti bahwa 3 | (n3 − n) untuk setiap bilangan asli n. Untuk bukti formal kita bisa pilih salah satu langkah induksi. Pada alternatif pertama bukti formalnya akan tampak bahwa bentuk 3(n 2 + n) muncul secara tiba-tiba. Padahal motivasinya jelas pada kotretan. Berbeda dengan alternatif kedua dimana bentuk itu muncul secara alami. Kedua alternatif tersebut valid karena P (n + 1) dibuktikan benar berdasarkan asumsi P( n) , dengan P(n) yang dinyatakan secara implisit, yaitu 3 | n3 − n untuk suatu bilangan asli n sembarang. Pada kenyataannya tipe langkah induksi seperti alternatif kedua diatas lebih banyak digunakan. Pada contoh-contoh berikutnya kita akan menuliskan P(n) dan P (n + 1) secara implisit untuk mengefisienkan ruang tulis, kecuai memang dinyatakan. Yang penting


25

adalah bagaimana membangun hipotesis induksi yang menyebabkan induksi berkerja secara valid. Buktikan bahwa n5 / 5 + n 4 / 2 + n3 / 3 − n / 30 bulat untuk setiap n bulat non-negatif. Bukti. Bukti secara induksi. Pernyataan itu jelas benar untuk n = 0. Asumsikan pernyataan benar untuk n = k. Sekarang kita akan bergerak dari P(k + 1) dan memunculkan P(k) untuk memanfaatkan asumsi induksi.

(k + 1)5 (k + 1) 4 (k + 1)3 k + 1 + + − 5 4 3 30 5 4 3 ⎡k k k k ⎤ = ⎢ + + − ⎥ + ⎡⎣ k 4 + 4k 3 + 6k 2 + 4k ⎤⎦ . ⎣ 5 4 3 30 ⎦ Grup pertama berdasarkan asumsi induktif merupakan bilangan bulat, dan grup kedua jelas bulat karena merupakan penjumlahan bilangan bulat. Jadi terbukti secara induksi. Kita akan melihat penerapan yang menarik dari induksi matematika pada masalah berikut. Bayangkan ada papan kotak-kotak berukuran 2n x2n dengan n bulat positif yang memiliki lubang di satu petak. Apakah kita selalu dapat menutup papan itu dengan triomino L?

Solusi. Karena kita akan menggunakan induksi, kita perhatikan dulu jika n = 1. Papan berukuran 2 x 2 yang memiliki satu lubang pasti bisa langsung ditutup satu triomino L, seperti terlihat pada gambar di atas.


26

Sekarang, kita asumsikan bahwa papan 2k x2k yang memiliki satu lubang bisa ditutup beberapa triomino. Susun empat papan berukuran 2k x2k seperti gambar diatas (warna abu-abu menyatakan lubang). Perhatikan bahwa lubang di tengah dapat ditutup dengan satu triomino L. Maka papan itu menjadi papan 2k +1 x2k +1 yang memiliki satu lubang dan dapat ditutup dengan triomino. Maka langkah induksi selesai dan kita telah membuktikan bahwa triomino L selalu dapat menutup papan 2n x2n yang berlubang satu. Induksi juga dapat digunakan untuk pernyataan yang mengandung pertidaksamaan. Berikut ini adalah contoh yang memberikan ide. Contoh. Buktikan 1 + 1

2 +1

3 + ... + 1

n ≤ 2 n − 1 untuk setiap bilangan asli n.

Bukti. Bukti secara induksi. Untuk n = 1, jelas bahwa 1 ≤ 2 1 − 1 = 1 . Asumsikan pernyataan itu benar untuk sembarang n. Perhatikan bahwa

1 2 2 = < =2 n +1 n +1 + n +1 n +1 + n

(

)

n +1 − n .

Maka 1+

1 1 1 1 + ... + + ≤ 2 n −1+ , (asumsi induksi) 2 n n +1 n +1 < 2 n −1+ 2

(

n +1 − n

)

= 2 n + 1. Terbukti secara induksi. Coba juga buktikan 1 + 1 2 + 1 3 + ... + 1 n > 2 n + 1 − 2 sebagai latihan. Kita harus berhati-hati mengaplikasikan induksi pada setiap langkah, jika tidak kita akan mudah membuat kesalahan. Seperti tampak pada contoh berikut Teorema Salah. Semua kuda berwarna sama.

Bukti. Akan dibuktikan secara induksi. Misalkan P (n) merupakan pernyataan setiap kuda dalam himpunan n kuda berwarna sama. Sebagai kasus basis, untuk n = 1, P (1) karena setiap kuda dalam himpunan satu kuda warnanya sama. Misalkan P(n) benar untuk suatu bilangan asli n sembarang. Sekarang pertimbangkan himpunan n + 1 kuda: berdasarkan asumsi n kuda pertama berwarna sama. Juga berdasarkan asumsi n kuda terakhir berwarna sama. Jadi kuda sebanyak n + 1 itu berwarna sama atau P (n +1) . Jadi berdasarkan prinsip induksi P(n) benar untuk setiap bilangan asli n. Dengan kata lain setiap kuda berwarna sama. ◊


27

Kita telah membuktikan sesuatu yang salah! Apakah matematika bobol? Argumentasi kita yang keliru. Perhatikan pernyataan: “kuda sebanyak n + 1 itu berwarna sama.” Pernyataan ini berkata bahwa n kuda pertama dan n kuda terakhir saling melingkupi. Ini tidak benar, bahkan untuk n = 1: seekor kuda dan seekor kuda lainnya tidak saling melingkupi alias berbeda. Kita telah membuktikan P (1) , alasan bahwa n kuda terakhir berwarna sama, karena asumsi, membuktikan bahwa P (2) ⇒ P(3) , P (3) ⇒ P(4) , dst. Tapi belum membuktikan P (1) ⇒ P(2) , sehingga membuat argumentasi kita runtuh dan matematika tetap utuh. Dengan kata lain ada himpunan kuda-kuda berwarna beda. Untuk mengatasi masalah seperti ini sebelum kita menginduksi kita harus memperlihatkan kebenaran beberapa P (n) , yang kemudian mengakibatkan kebenaran P (n +1) . Secara formal bentuk induksi seperti ini dinamakan induksi kuat.

Induksi Kuat Misalkan P(n) adalah suatu pernyataan mengenai bilangan bulat n ≥ a . Misalkan pula i. P (a ) benar (kasus basis) dan ii. untuk setiap k ≥ a berlaku: jika P (a ), P(a + 1),..., P(k ) benar, maka P (k + 1) benar (langkah induksi), maka P(n) benar untuk setiap n ≥ a . Bedanya dengan induksi sebelumnya adalah bahwa asumsi kita di langkah induksi (ii) lebih kuat, yaitu mengasumsikan kebenaran P (a ), P(a + 1),..., P(k ) – tidak hanya P (k) untuk mengakibatkan bahwa P (k + 1) . Secara teori kedua bentuk induksi equivalen, tetapi ada beberapa masalah yang harus melibatkan asumsi pada induksi kuat. Contoh. Setiap jalan di Nebula satu arah. Setiap pasang kota dihubungkan dengan tepat satu jalan. Tunjukkan bahwa ada kota yang dapat dijangkau dari setiap kota lainnya baik secara langsung atau melalui paling banyak suatu kota lainnya. Bukti. Akan dibuktikan secara induksi kuat. Pernyataan yang disuguhkan benar untuk dua dan tiga kota. Misalkan pernyataanya benar untuk n kota. Misalkan kota-kota yang memenuhi kondisi masalah disebut golongan H. Untuk sembarang n kota ambil kota A yang merupakan golongan H. Kota lainnya, sebanyak n – 1, dapat dipartisi menjadi dua himpunan, yaitu golongan X yang merupakan kota-kota yang terhubung langsung dengan kota A dan golongan Y, himpunan kota-kota yang tidak terhubung langsung ke kota A. Karena setiap kota dihubungkan dengan tepat satu jalan, maka setiap kota yang tergolong Y dapat menuju A dengan melewati suatu kota yang tergolong X. Misalkan kota B baru dibangun, sehingga sekarang ada n + 1 kota. Untuk menunjukkan masih adanya kota yang tergolong H pertimbangkan 2 kasus:


28

1.

Ada jalan yang menghubungkan secara langsung kota B ke kota A atau ke kota golongan Y. Maka A tetap tergolong kota H untuk n + 1 kota. 2. Dari A dan dari setiap kota yang tergolong X ada jalan langsung menuju B. Juga terdapat sebuah jalan yang menghubungkan secara langsung golongan kota Y ke suatu kota di X. Maka kota B tergolong H. Terbukti secara induksi. Contoh. Ekspresi ekspisit barisan Fibonacci, rumus Binet. Buktikan bahwa f n = (α n − β n ) 5 , dengan α = 1 + 5 2 dan β = 1 − 5 2 . α dikenal sebagai

(

)

(

)

golden ratio. Bukti. Untuk n = 0 , jelas bahwa

f 0 = (α 0 − β 0 )

5 = 0 merupakan barisan

Fibonacci. Asumsikan rumus Binet berlaku untuk n dan n + 1 . Tetapi, Fn + 2 = Fn + Fn +1 = (α n − β n ) Perhatikan bahwa α , β

5 + (α n +1 − β n +1 )

5 = (α n (α + 1) − β n ( β + 1) )

5.

merupakan akar persamaan x 2 − x − 1 = 0 , sehingga

α + 1 = α 2 dan β + 1 = β 2 . Jadi Fn + 2 = (α n + 2 − β n + 2 )

5 . Rumus Binet terbukti secara

induksi.

Pencarian Pola Prinsip ini erat hubungannya dengan pencarian pola berdasarkan sesuatu yang dapat dihitung dan mempunyai nilai terkecil. Jika kita telah merasa yakin telah menemukan pola dibalik sesuatu dan sesuatu itu dapat dihitung, maka prinsip induksi mungkin muncul sebagai pilihan pertama untuk membuktikan kebenaran pola itu. Pola bisa berupa suatu barisan yang mempunyai aturan tertentu, sedangkan aturannya dapat didefinisikan secara rekursif, seperti persamaan rekursif yang muncul dibalik masalah Josephus (dibahas di MAJALAH Zer0 edisi pertama). Barisan Fibonacci didefinisikan sebagai berikut: untuk suatu bilangan bulat tak negatif, f n adalah suku ke-n barisan Fibonacci jika f 0 = 0, f1 = 1 dan f n = f n −1 + f n − 2 untuk n ≥ 2 . Banyak pola yang dapat digali dari barisan ini, bahkan pola Fibonacci muncul pula sebagai pola yang terjadi di alam. Ada sesuatu yang mistis dibalik barisan Fibonacci, tetapi kita akan bahas nanti. Sekarang kita hanya akan melihat salah satu polanya, yaitu: Contoh. Buktikan bahwa untuk setiap n bulat tak negatif, n

f n + 2 = ∑ fi + 1 . i =0

0

Bukti. Akan dibuktikan secara induksi. Untuk n = 0, jelas bahwa f 2 = ∑ fi + 1 = 1 . i =0

Asumsikan persamaan f n + 2 itu benar untuk suatu n sembarang. Karena


29 n +1

n

f n +3 = f n + 2 + f n +1 = ∑ fi + 1 + f n +1 = ∑ f i + 1 , i =0

i =0

n

maka terbukti secara induksi bahwa berlaku f n + 2 = ∑ fi + 1 untuk setiap bilangan i =0

bulat tak negatif n. Sebagai latihan cobalah cari pola pada masalah berikut, generalisasi, kemudian buktikan dengan induksi. Latihan 1. Perhatikan

1 = 1, 1 + 3 = 4, 1 + 3 + 5 = 9,...

Beberapa contoh di atas mendorong kita untuk menerka bahwa jumlah n bilangan ganjil pertama sama dengan n kuadrat. Benarkah? Latihan 2.

1⋅ 2 ⋅ 3 , 6 3⋅ 4 ⋅5 12 + 32 = , 6 5⋅6⋅7 12 + 32 + 52 = ,... 6 12 =

Latihan 3.

1 1 4 + = , 1 3 3 1 1 8 + = , 3 5 15 1 1 12 + = , 5 7 35

42 + 32 = 52 , 82 + 152 = 17 2 , 122 + 352 = 37 2 ,...

Latihan 4.

62 − 52 = 11, 562 − 452 = 1111, 5562 − 4452 = 111111,... Latihan 5. Dengan prinsip cari pola, terka, dan induksi coba hitung berapa banyak kata “ABRACADABRA” dapat dibaca pada gambar di samping. Aturan membacanya adalah mulai dari A teratas dengan arah kebawah sampai di A terbawah.


30

Memperkuat hipotesis induksi merupakan langkah yang bagus ketika induksi biasa tidak bekerja dengan baik. Yang perlu diperhatikan adalah bahwa setiap asumsi hipotesis harus benar, jika tidak konstruksi bukti yang valid tidak akan terjangkau. Sering kali, menemukan hipotesis induksi yang tepat diperlukan trial and error dan pemahaman yang mendalam. Pernah terjadi ketika matematikawan selama hamper dua puluh tahun mencoba membuktikan atau menyangkal konjektur tentang graf bidang: “setiap graf bidang merupakan 5-choosable 5 .” Baru pada tahun 1994 Carsten Thomassen memberikan bukti induksi yang begitu sederhana. Kuncinya adalah menemukan hipotesis induksi yang benar-benar cerdas yang membuat konstruksi selanjutnya mengalir dengan mudah. Teorema Salah. Saya bisa memindahkan semua pasir di pantai.

Bukti. Bukti secara induksi. Misalkan P(n) : “Saya bisa memindahkan n butir pasir.” Kasus basis, P (1) , benar karena saya bisa dengan mudah memindahkan 1 butir pasir. Pada langkah induksi, asumsikan bahwa saya bisa memindahkan n butir pasir. Jika demikian maka saya bisa memindahkan n + 1 butir pasir karena penambahan 1 butir pasir tidak jadi masalah. Sehingga P (n) ⇒ P (n + 1) . Secara induksi terbukti bahwa P(n) benar untuk setiap bilangan asli n. Jadi saya bisa memindahkan semua pasir di pantai. ◊ Pernyataan yang menjebak adalah penegasan bahwa saya bisa memindahkan n + 1 butir pasir karena saya bisa memindahkan n butir pasir. Kita tidak bisa dengan tepat memastikan dapat memindahkan pasir sebanyak n, sembarang bilangan asli. Meskipun sulit mendapatkan n dimana P(n) salah yang penting adalah eksistensinya. Masalah ini dapat dijelaskan dengan baik bila kita mengacu pada logika fuzzy yang nilai kebenarannya dinyatakan sebagai bilangan real antara 0 dan 1. Masalah ini merupakan analogi induksi yang nilai kebenarannya berkurang satu satuan pada setiap implikasi.

5

5-choosabiity merupakan generalisasi dari 5-colorability. Dalam teori graf telah dibuktikan bahwa setiap graf bidang 4-colorable, sehingga 5-colorable, tetapi tidak semua graf bidang 4-choosable. Panik? Tenang, teori graf akan dibahas di MAJALAH Zer0 suatu saat.


31

Argumentasi yang Keliru AK5. Sudut Siku-siku sama dengan Sudut Tumpul Misalkan ada segmen AB. Dari A pada sudut siku-siku buat sembarang segmen AC. Dari B pada sudut tumpul, misalnya 100o, buat segmen BD yang panjangnya sama dengan AC. Misalkan garis tengah tegak lurus AB dan CD berpotongan di E. Perhatikan gambar di bawah.

Karena E pada garis tengah tegak lurus AB maka AE = BE, sedangkan CE = DE, karena E pada garis tengah tegak lurus CD. Karena AE = BE, CE = DE, dan AC = BD, maka segitiga AEC dan BED kongruen. Karena segitiga AEC dan BED kongruen maka ∠EAC = ∠EBD dan karena segitiga AEB sama kaki maka ∠EAB = ∠EBA , sehingga 90D = ∠EAC − ∠EAB = ∠EBD − ∠EBA = ∠ABD = 100D.

Jadi sudut siku-siku sama dengan sudut tumpul.

◊

AK6. 14 = 15 Di Wroclaw 1952 dalam sebuah pertemuan peserta Olimpiade Matematika, Dr. J. Mikusinski mendemonstrasikan sebuah masalah temukan di mana kesalahannya dengan menggunakan argumentasi pengubinan bidang dengan segi tujuh beraturan. Misalkan P adalah sudut 180o. Jumlah seluruh sudut sebuah segi tujuh adalah 5P, sehingga sebuah sudut di heptagon besar rata-ratanya adalah 5P/7. Karena bidang dapat diselimuti oleh segitujuh, maka sudut rata-rata pada mosaik ini adalah 5P/7. Tetapi, karena pada setiap titik terbentuk tiga sudut itu, maka sudut rata-rata pada setiap titik adalah 2P/3. Hal ini mengakibatkan rata-rata sudut pada mosaik itu adalah 2P/3, karena setiap sudut dibangun oleh suatu titik. Jadi 5P/7 = 2P/3 atau 14 =15. ◊


32

Masalah & Solusi Anda dapat turut berpartisipasi dengan mengirimkan solusi untuk masalah yang disediakan (pada suatu edisi) atau mengirim masalah baru untuk dipublikasikan. Untuk masukan masalah sertakan solusi Anda. Alamatkan solusi atau masalah Anda melalui email ke salah satu alamat email editor. Cantumkan informasi sedetil mungkin untuk memudahkan editor menyunting masukan dan tulis sebagai file Word.

Solusi Masalah 2 [MZ 01-0708]. Bilangan diantara empat bilangan kubik Buktikan bahwa, di antara empat bilangan kubik, selalu ada dua bilangan yang selisihnya habis dibagi 7. Solusi oleh Raja Octovin, Pekanbaru. Semua bilangan kubik, jika dibagi 7, akan memberikan sisa atau . Misalkan A = {himpunan bilangan kubik yang habis dibagi 7}, B = {himpunan bilangan kubik bersisa 1 jika dibagi 7} dan B = {himpunan bilangan kubik bersisa 6 dibagi 7}. Apabila dari empat bilangan ada dua bilangan yang berasal dari himpunan yang sama, maka bilangan tersebut habis dibagi 7. Berdasarkan PHP, apabila ada 4 benda yang akan dimasukkan ke dalam 3 kotak, maka ada 1 kotak yang mengandung lebih dari 1 benda. Dari sini, terbukti bahwa dari empat bilangan kubik, ada dua bilangan kubik yang berasal dari himpunan yang sama. Dan bukti mengikuti. ?

Komentar penyunting Sebagai catatan PHP di atas adalah prm, prinsip rumah merpati. Hey, kenapa di akhir bukti ada tanda “?”? Karena ada sesuatu yang masih cacat. Yang masih belum tepat adalah ambiguitas pengarahan “bilangan tersebut” pada kalimat, “Apabila dari empat bilangan ada dua bilangan yang berasal dari himpunan yang sama, maka bilangan tersebut habis dibagi 7.” Yang tepat adalah selisih dua bilangan dalam himpunan yang sama yang habis dibagi 7 (0 mod 7). Sesuai pernyataan masalah. Ini adalah kekeliruan yang berharga, sayangnya Raja tidak memberikan informasi tambahan untuk menghubunginya kembali. Beberapa masalah yang pernah diungkapkan di blog Zer0. 1. Pada gambar di samping, Jika lingkaran terbesar dan sedang berturut-turut berjari-jari 9 dan 4 cm, maka jari-jari lingkaran terkecil adalah… cm. Solusi. Kita akan menyelesaikan masalah yang lebih umum. Misalkan koordinat pusat lingkaran besar, sedang, kecil berturut-turut adalah


33

(h, a), (k , b), dan (0, c) , dengan a ≥ b > c . Dengan menerapkan teorema Pythagoras pada setiap dua lingkaran yang bersinggungan maka diperoleh tiga persamaan,

h 2 + (a − c) 2 = (a + c) 2 , k 2 + (b − c) 2 = (b + c) 2 , ( h + k ) 2 + ( a − b) 2 = ( a + b) 2 . Dengan mengekspansi masing-masing persamaan kita peroleh,

h 2 = 4ac,

k 2 = 4bc,

h 2 + k 2 + 2hk = 4ab.

Subtitusi persamaan pertama dan kedua ke persamaan ketiga kita peroleh,

hk = 2(ab − bc − ca) . (1) Karena h 2 k 2 = 16abc 2 , maka dengan meguadratkan kedua ruas (1) kita peroleh 4abc 2 = (ab − bc − ca) 2 . (2) Persamaan (2) cukup untuk menyelesaikan masalah ini, yaitu pilih a = 9, b = 4 , sehingga 144c 2 = (36 − 13c) 2 = 362 − 2 ⋅ 36 ⋅13c + 132 c 2 . Karena c merupakan jari-jari lingkaran terkecil maka dengan menyelesaikan persamaan kuadrat terakhir kita peroleh c, jari-jari lingkaran terkecil sama dengan 36/25. Cacatan. a,b,c dalam h dan k memenuhi persamaan

a=

h( h + k ) k (h + k ) hk . , b= , c= 2k 2h 2(h + k )

2. L1 dan L2 adalah dua lingkaran yang konsentris.

Jika panjang AB adalah 16 cm, maka luas daerah yang diarsir adalah… π cm2.


34

Solusi. Misalkan jari-jari lingkaran besar dan kecil berturut-turut adalah R dan r. Pandang

Dan kita punya persamaan R 2 = r 2 + 16 atau R 2 − r 2 = 16 . Dan Luas daerah yang diarsir adalah π R 2 − π r 2 = 16π cm 2 . 3. ABCD adalah sebuah trapesium sama kaki dengan BC = 12 cm. Dalam trapesium dibuat lingkaran yang menyinggung keempat sisinya. Perhatikan gambar di bawah

Jika PQ = 10 cm, maka luas lingkaran adalah … π cm2. Solusi. Misalkan jari-jari lingkaran itu r. Dari B dan Q tarik garis sehingga tegak lurus DC dan masing-masing berpotongan dengannya berturut-turut di F dan G. Misalkan E adalah titik singgung lingkaran dengan garis DC. Misalkan EC = x, maka karena simetri CQ = x. Akibatnya QB = 12 – x.

Pandang segitiga CFQ. CG = EG – EC = 12 – x – x. Aplikasikan teorema Pythagoras padanya, sehingga berlaku


35

(12 − 2 x) 2 + (2r ) 2 = 122

r 2 = 12 x − x 2 . Pandang segitiga CFQ dan CGB. Kedua segitiga itu sebangun karena ∠QCF = ∠BCG dan ∠CFQ = ∠CGB = 90D . EF = 1/2PQ = 5. Maka berlaku perbandingan

CQ CB = CF CG 12 x = 5 − x 12 − 2 x 30 = x 2 − 12 x = r 2 . Jadi luas lingkaran itu adalah 30 π cm2.

Solusi Sekilas Logika Banyaknya binatang peliharaan Zer0 adalah tiga: satu kucing, satu anjing, dan satu merpati. Di sini semua berarti satu. 10 koin dan 3 gelas: masukkan 1, 2, 7 koin ke berturut-turut gelas 1, 2, 3. Masukkan gelas 1 ke gelas 2. Sekarang dalam masing-masing gelas ada sebanyak ganjil koin. Ada banyak solusi.


36

Berita Raihan Tim Indonesia di IMO ke-49 2008 Hasil resmi Olimpiade Matematika 2008 di Madrid, Spayol, sudah keluar. Berikut ini data raihan diambil dari situs resmi IMO, http://www.imo-official.org/, Kontestan

P1

P2

P3

P4

P5

P6

Total

Rangking

%

Mendali

Andreas Dwi Maryanto G.

7

5

0

4

7

0

23

116

78.46

S

Aldrian Obaja Muis

7

3

0

7

2

0

19

170

68.35

B

4

7

0

0

6

0

0

17

199

B

7

1

0

4

0

0

12

297

44.57

H

Satria Stanza Pramayoga

0

5

0

4

0

0

9

346

35.39

Sa'Aadah Sajjana Carita

7

0

0

1

0

0

8

368

31.27

H

Tim

32

21

0

26

9

0

88

36

63.5

S, B, B, H, H

Fahmi Fuady Joseph Andreas

Dengan mendali G, S, B, H, berturut-turut adalah Gold, Silver, Bronze, dan Honourable Mention. Dipimpin oleh Hery Susanto tim ini berhasil meraih prestasi terbaik dari tahun-tahun sebelumnya. Berikut adalah statistik prestasi tim olimpiade Indonesia sampai tahun 2008.


37

Selamat pada tim olimpiade dan kita semua berdoa bahwa prestasi akan terus memuncak.

Sumber Matematika Teka-teki http://www.conceptispuzzles.com/ https://www.pennydellpuzzles.com/free_puzzles/default.aspx http://bozzball.blogspot.com/ http://www.puzzlepicnic.com/puzzles http://puzzlebeast.com/ http://www.ocf.berkeley.edu/~wwu/riddles/ http://mathpuzzle.com/

Olimpiade http://www.mathlinks.ro/ http://www.olimpiade.org/

Perangkat Lunak http://www.themathlab.com/toolbox/geometry%20stuff/geosketch.htm http://www.geogebra.org/cms/index.php?option=com_frontpage&Itemid=1

Masalah Seribu Tahunan - Millennium Prize Problems Oleh Ferry Tahukah kamu bahwa matematika bisa membuat kamu kaya. Pada tahun 2000, Clay Mathematics Institute mengumumkan Millennium Prize dengan total hadiah US$ 7.000.000. Tentunya hadiah ini tidak untuk sembarang orang. Hadiah ini berkaitan dengan 7 permasalahan matematika yang disebut Millennium Prize Problems. Setiap orang yang mampu memecahkan satu permasalahan akan diberi hadiah sejumlah $ 1.000.000 oleh Clay. Semua masyarakat dari seluruh dunia diperbolehkan mengikuti perlombaan matematika ini tanpa dipungut biaya apapun. Sampai saat ini hanya satu dari 7 permasalahan ini telah dapat dipecahkan. Ketujuh permasalahan ini adalah: 1. P versus NP Apakah setiap permasalahan yang solusinya dapat diklaim benar komputer dalam waktu polinomial, juga dapat ditemukan secara pasti dengan waktu yang sama. 2. The Hodge conjecture


38

Buktikan untuk varietas proyeksi dalam aljabar, Lingkaran Hodge adalah kombinasi linear dari lingkaran aljabar. 3. The Poincaré conjecture (terselesaiakan oleh Grigori Perelman) Dalam dimensi-2 suatu bola akan terhubung secara sederhana. Diketahui pula bahwa setiap permukaan di dimensi-2 bersifat kompak dan terhubung secara sederhana adalah bola secara topologi. Konjektur ini mengatakan bahwa hal yang sama untuk dimensi-3. Pertanyaannya adalah membuktikan konjektur ini unutk dimensi yang lebih besar dari 3. 4. The Riemann hypothesis Buktikan: untuk setiap nol tak trivial dari fungsi Riemann zeta memiliki bagian real ½. Hipotesis ini erat dengan teori number, terutama distribusi bilangan prima. (red: ada matematikawan, Xian-Jin Li, yang membuat paper tentang bukti hipotesis Riemann. [papernya dapat dilihat di Arxiv, http://arxiv.org/abs/0807.0090v3]. Paper ini dirilis mulai tanggal 1 Juli 2008. Namun, Terence Tao, pernah dianugerahi Field Medal, menemukan kesalahan, sehingga di versi yang keempat paper Li ditarik kembali dengan alasan ada yang salah di halaman 29.) 5. Yang–Mills existence and mass gap Permasalahan ini erat dengan fisika, yaitu teori kuantum Maxwell. Permasalahannya adalah membuktikan keberadaan teori kuantum Yang-Millis dan gap massa secara matematika. 6. Navier–Stokes existence and smoothness Permasalah: membuktikan secara matematika persamaan Navier–Stokes tentang gerak fluida dan gas. 7. The Birch and Swinnerton-Dyer conjecture Konjektur ini berkaitan dengan kurva eliptik di bilangan rasional. Pertanyaannya: apakah terdapat suatu cara mudah untuk mengatatakan suatu fungsi memiliki solusi rasional yang berhingga atau tak berhingga. Sumber: http://en.wikipedia.org/wiki/Millennium_Prize_Problems


39

Iklan

Simpan Iklan Di Sini




40

Daftar Isi PENGANTAR

3

PERKENALAN DENGAN LOGIKA DAN PERNYATAAN MATEMATIKA

4

PRINSIP RUMAH MERPATI

12

PRINSIP PENCARIAN POLA DAN INDUKSI

20

ARGUMENTASI YANG KELIRU

31

MASALAH & SOLUSI

32

SOLUSI

32

BERITA

36

RAIHAN TIM INDONESIA DI IMO KE-49 2008

36

SUMBER MATEMATIKA

37

MASALAH SERIBU TAHUNAN - MILLENNIUM PRIZE PROBLEMS

37

MATH & CS For N0thing, but Fun

Recommend Documents