Pigeonhole Principle ... (ii)

Lanjutan dari sebelumnya

Kasus F:
Seperti kasus nomor A. Sekarang, di laci ada 12 kaos kaki hitam, 13 kaos kaki putih, 20 kaos kaki biru, 5 kaos kaki merah, 1 kaos kaki hijau, dan 1 kaos kaki kuning. Berapa banyak kaos kaki minimal yang harus diambil agar setidaknya:
a) terdapat 2 kaos kaki yang memiliki warna yang sama
b) terdapat 2 kaos kaki yang memiliki warna yang berbeda.

(Ayo berpikir)...
Jawaban dapat dilihat di bawah... ^^..
Ada juga kasus-kasus lain yang lebih seru dan menantang..
=========================================================================

Jawaban Kasus F:

a)	Kemungkinan terburuk yaitu saat mengambil 6 kaos kaki yang semuanya berbeda warna (hitam, putih, biru, merah, hijau, dan kuning). Oleh karena itu, kaos kaki minimal yang harus diambil agar setidaknya terdapat 2 kaos kaki dengan warna sama adalah 7 buah.
b)	Kemungkinan terburuk yaitu saat mengambil 20 kaos kaki yang semuanya berwarna biru. Oleh karena itu, kaos kaki minimal yang harus diambil agar setidaknya terdapat 2 kaos kaki dengan warna berbeda adalah 21 buah.

Nah, ternyata masalah tersebut dapat ditinjau berdasarkan kemungkinan terburuknya. Berikut di bawah, akan dijelaskan kasus-kasus yang membuat kita harus meninjau kemungkinan terburuknya sebelum menuju kesimpulan...

=========================================================================

Pigeonhole Principle dan Teori Bilangan II

Kasus G:
Diberikan barisan bilangan dari 1,2,3,...,100. Jika dari barisan bilangan tersebut diambil 51 bilangan, buktikan bahwa paling tidak ada 2 bilangan yang selisihnya 50.

Jawab:
Sebelumnya, perhatikan di bawah.
Diberikan barisan dari a+1 sampai 2n, sebagai berikut:

a+1, a+2, a+3, a+4, ... , a+2n-1, a+2n

Dengan demikian, akan terdapat pasangan bilangan yang selisihnya n, seperti (a+1, a+n+1), (a+2, a+n+2), ... , (a+n, a+2n). Jumlah seluruh pasangan ini berjumlah n. Maka, dengan mengambil bilangan yang minimal n+1, maka pasti akan selalu ada pasangan bilangan yang selisihnya n.

Soal di atas diambil a = 0 dan n=50.

Kasus H:
Diberikan barisan bilangan dari 1,2,3,...,100. Jika dari barisan bilangan tersebut diambil 55 bilangan, buktikan bahwa paling tidak ada 2 bilangan yang selisihnya 9.

Jawab:
Perhatikan bahwa sesungguhnya soal ini tidak berbeda jauh dengan soal sebelumnya. Kemungkinan terburuk yaitu dengan mengambil n bilangan dari barisan 2n (dimana n=9), sehingga bilangan yang selisihnya 9 tidak didapat. Berikut akan dijabarkan pemilihan kemungkinan terburuknya:

Dari 1,2,3, ..., 18 dipilih 9 bilangan, yaitu 1,2,3,...,9.
Dari 19, 20, 21, ..., 36 dipilih 9 bilangan, yaitu 19, 20, 21, ... , 27.
Dari 37, 38, 39, ..., 54 dipilih 9 bilangan, yaitu 37, 38, 39, ..., 45.
Dari 55, 56, 57, ..., 72 dipilih 9 bilangan, yaitu 55, 56, 57, ..., 63.
Dari 73, 74, 75, ..., 90 dipilih 9 bilangan, yaitu 73, 74, 75, ..., 81.
Dari 91,92,93,...,100 dipilih 9 bilangan, yaitu dari 91,92,93, ..., 99.

Dengan demikian, bilangan yang terpilih ada 54 bilangan. Masih kurang 1 bilangan untuk mencapai 55 bilangan, dan bilangan apapun yang dipilih akan menyebabkan adanya bilangan yang selisihnya 9, misalnya 100 (100-91 = 9), atau 17 (17-8=9 dan 26-17 = 9). Dengan pemilihan kemungkinan terburuk ini sudah ada bilangan yang selisihnya 9, maka pernyataan di soal terbukti kebenarannya.

Kasus I:
Diberikan barisan bilangan dari 1,2,3,...,100. Jika dari barisan bilangan tersebut diambil 55 bilangan, buktikan bahwa belum tentu ada 2 bilangan yang selisihnya 11.

Jawab:
Sama seperti sebelumnya.
Dari 1,2,3, ..., 22 dipilih 11 bilangan, yaitu 1,2,3,...,11.
Dari 23,24,25, ..., 44 dipilih 11 bilangan yaitu 23,24,25,...,33.
Dari 45,46,47,..., 66 dipilih 11 bilangan, yaitu 45,46,47,..., 55.
Dari 67,68,69, ... , 88 dipilih 11 bilangan, yaitu 67,68,69,...,77.
Dari 89,90,91, ...,100 dipilih 11 bilangan, yaitu 89,90,91,...,99.

Perhatikan bahwa kita sudah memilih 55 bilangan, namun belum ada pasangan bilangan yang selisihnya 11. Maka, pernyataan di soal terbukti.

Note: Seandainya, jumlah bilangan yang diambil adalah 56, maka paling tidak ada 2 bilangan yang selisihnya 11, karena bilangan yang ke-56 akan menyebabkan selisih 11 dengan salah satu dari 55 bilangan yang sudah ada sebelumnya.

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

Jawab:
Pertama, ada 77 hari untuk latihan dan setiap hari minimal satu permainan. Kedua ada 132, yaitu banyaknya seluruh permainan maksimal dalam latihan. Jika kita memisalkan  sebagai banyaknya permainan yang telah ia lakukan sampai hari ke-i dengan i = 1, 2, …, 77, maka  paling tidak 1, paling tidak 2, dst, sampai  paling banyak 132. Secara matematika dapat dituliskan sebagai berikut.

Perhatikan bahwa kasus ini identik dengan kasus berikut:
"Diberikan barisan bilangan dari 1,2,3,...,132. Jika dari barisan bilangan tersebut diambil 77 bilangan, buktikan bahwa paling tidak ada 2 bilangan yang selisihnya 21."

Maka, kasus ini sama seperti Kasus H sebelumnya.

Tinjau kemungkinan terburuknya:
Dari 1,2,3, ..., 42 dipilih 21 bilangan, yaitu 1,2,3,...,21.
Dari 43,44,45, ..., 84 dipilih 21 bilangan yaitu 43,44,45,..., 63.
Dari 85, 86, 87, ..., 126 dipilih 21 bilangan, yaitu 85,86,87, ..., 105.
Dari 127,128, ...,132 dipilih semuanya (6 bilangan), yaitu 127,128,129,...,132.

Sudah ada 69 bilangan yang dipilih. Artinya, 1 bilangan lagi yang dipilih, apapun itu, mengakibatkan ada pasangan yang selisihnya 21. Artinya, 70 bilangan saja sudah cukup untuk membuat adanya paling tidak 2 bilangan yang selisihnya 21, sedangkan di soal tertulis "77 bilangan" yang artinya kondisi yang berlebih.

Jadi, terbukti bahwa ada barisan hari berturut-turut disaat ia bermain catur sebanyak tepat 21 kali.

Note: Soal yang sama bisa dilihat di majalah Zero edisi ke-2 halaman 14(sumber lihat di bawah), namun di sini saya mengoreksi sedikit solusi yang dijabarkan di sana.

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

54, 22, 9, 15, 24, 59, 102

Perhatikan bahwa terdapat suatu blok: 15, 24, 59 yang jumlahnya 98, habis dibagi 7. Buktikan hasil ini.

Jawab:
Misalkan barisan tersebut adalah 
Sekarang, misalkan simbol  menyatakan deret barisan, yang dijabarkan sbb:





Jika  dapat dibagi n atau  mod 7 = 0, maka pembuktian selesai.

Namun, jika  tidak dapat dibagi n, maka kita tinjau sisa pembagian terhadap n dari  yang mungkin (dari 1 sampai n-1). Artinya, ada n-1 jumlah kemungkinan sisa pembagian. Misalkan jika n=7, maka kemungkinan sisa pembagian terhadap 7 selain nol adalah 1, 2, 3, 4, 5, dan 6.

Namun, karena jumlah blok  ada sebanyak n buah sedangkan kemungkinan sisa pembagian yang berbeda adalah n-1 buah, artinya pasti ada  dan  () yang sisa pembagiannya sama. Karena sisa pembagiannya sama, maka:

Maka, kita telah mendapatkan blok yang habis dibagi n, yaitu dari  sampai .

Kasus J:
Misalkan A adalah himpunan dua puluh bilangan berbeda yang dipilih dari himpunan B = {1, 4, 7, …, 100}. Buktikan bahwa paling tidak ada dua anggota A berbeda yang jumlahnya 104.

Jawab:
Pertimbangkan himpunan bilangan C, himpunan semua pasangan yang jumlahnya 104, yang anggotanya diambil dari B.

C = {(4,100),(7,97),...,(49,54)}.

Terlihat bahwa ada tujuh belas anggota C. Ambil salah satu bilangan dari setiap pasangan di C, tambahkan 1 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.

=========================================================================

Materi Pigeonhole principle sesungguhnya banyak sekali ditemukan di kehidupan kita sehari-hari, dan kasusnya tidak sesederhana kasus-kasus di atas. Selain, teori bilangan, prm bisa muncul dalam kasus geometri, trigonometri, dan sebagainya.

Dalam ilmu komputer pun, 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.

Namun, masalah-masalah tersebut tidak akan dibahas sekarang. Mungkin, kalau aku ada waktu, materi ini akan saya lanjutkan.. ^^.. See you.

Read More

Pigeonhole Principle ... (i)

Pigeonhole Principle merupakan salah satu teorema matematika yang menarik..

Sebelumnya, perhatikan kasus berikut:

Kasus A:

Misalkan di rumahmu ada sebuah laci dan di dalam laci tersebut ada kaos kaki: 12 hitam dan 10 putih yang tersebar secara acak. Suatu hari, lampu di rumahmu mati, maka berapa kaos kaki MINIMAL yang harus kamu ambil agar dapat memperoleh sepasang kaos kaki dengan warna yang sama??

(Berpikirlah beberapa saat)...

(sudah dipikirkan??)

Kalau sudah, lanjut baca lanjutannya di bawah..
Dan, masih ada banyak sekali kasus yang akan dipaparkan selain di atas.. ^^.
=========================================================================

Pigeonhole Principle

Jawaban kasus A : cukup 3 kaos kaki..

Tentunya, kasus seperti di atas memang sangatlah mudah dan sederhana, namun dalam penerapannya bisa bermacam-macam, dan bisa secara tak terduga mengejutkan...

Pigeonhole Principle:

Jika k + 1 merpati dimasukkan ke dalam k rumah, maka ada satu rumah yang berisi paling tidak 2 merpati.

Note: gambar di atas menunjukkan bahwa ada 9 kotak, dan seharusnya ada 10 merpati. Merpati yang ke-10 yang ditempatkan di rumah manapun menyebabkan rumah itu berisi minimal 2 merpati..

Note: jumlah k+1 itu tidak wajib. Asalkan jumlah merpati lebih besar dari jumlah rumahnya, maka prinsip ini selalu berlaku.

Tentunya, bukti sudah jelas, bukan? Pigeonhole principle sering disebut juga sebagai prm (prinsip rumah merpati) ataupun Dirichlet drawer principle. Nama Dirichlet muncul karena dipercaya pertama kali dinyatakan oleh matematikawan Jerman bernama Gustav Lejeune Dirichlet pada tahun 1834.

Selain kasus kaos kaki di atas, perhatikan juga contoh mudah mengenai prm di bawah:

Kasus B:
Selidikilah kebenaran kasus di bawah ini:
1. Di antara tiga orang, maka pasti ada dua orang yang berjenis kelamin sama.
2. Dari 32 orang, pasti ada 2 orang yang memiliki tanggal lahir yang sama.
3. Jika kn + 1 kelereng didistribusikan ke dalam n kotak, maka satu kotak akan berisi paling tidak k + 1 kelereng.
4. Sebuah garis l di dalam bidang melalui sisi-sisi segitiga ABC dengan tidak melewati titik sudutnya. Maka, garis itu tidak akan melewati ketiga sisi segitiga.

Jawab:
Semua BENAR.
Perhatikan bahwa nomor 3 merupakan bentuk prm yang lebih umum. (prm yang ditulis disini diperoleh untuk k = 1).

Kasus C:
Dapatkah kamu membuktikan bahwa ada paling tidak dua orang penduduk di Bandung yang banyaknya rambut di kepala sama?

Jawab:
Sekilas, mungkin kamu akan berusaha memanggil satu demi satu penduduk di Bandung.. Kemudian, menyuruh mereka mencabuti setiap rambut mereka untuk dihitung.. Wahahaha.. Benar-benar lucu. Namun, untuk membuktikannya, kamu tidak perlu melakukan hal bodoh seperti itu. Gunakan prinsip rumah merpati di atas.

Perkirakan kemungkinan terburuk bahwa jumlah rambut terlebat adalah 1000 helai rambut per inchi persegi. Kemudian asumsikan kemungkinan terburuk bahwa rambut itu menutupi luas 1000 inchi persegi, maka jumlah helai rambut terlebat manusia ada sekitar 1000.000 helai.. (Ini sudah terburuk sekali)..

Membandingkannya dengan jumlah penduduk Bandung, yaitu sekitar 2.500.000 juta jiwa (tahun 2005, dan pasti akan terus bertambah), maka jumlah 1000.000 sekitar 2.5 kali lebih kceil dibandingkan jumlah penduduknya. Di kasus ini, kita dapat menganalogikan 2.500.000 sebagai jumlah merpati, dan 1000.000 sebagai jumlah rumah yang ada. Maka, akan ada paling tidak 2 orang yang memiliki jumlah rambut yang sama.

=========================================================================

Pigeonhole Principle dan Teori Bilangan

Kasus D:
Jika dari barisan bilangan 1,2,3,4,5,...,400 diambil 201 bilangan, maka buktikanlah bahwa dari 201 bilangan tersebut paling tidak ada dua bilangan yang koprima (faktor pembagi terbesarnya 1).

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

Kasus E:
Jika dari barisan bilangan 1,2,3,4,5,...,400 diambil 201 bilangan, maka buktikanlah bahwa dari 201 bilangan tersebut paling tidak ada dua bilangan dimana bilangan yang satu yang membagi bilangan yang lain.

Jawab:
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. Masalah ini berhasil dibuktikan pula oleh Lajos.

Kita dapat menulis kembali setiap anggota dalam himpunan A dalam bentuk: . Tentunya, karena yang diminta di soal adalah bilangan yang membagi bilangan lain, maka asumsikan bahwa anggota-anggota dalam himpunan A tidak boleh mengandung nilai m yang membagi satu sama lain. Dalam hal ini, m adalah bilangan ganjil yang mungkin dari 1,2,3,..., 2n. Artinya, m maksimal ada sebanyak n buah.

Perhatikan bahwa karena kita mengambil n+1 bilangan, maka artinya pernyataan di atas adalah kontradiksi. Akibatnya, pasti akan ada 2 bilangan dengan nilai m yang sama. Artinya, kedua bilangan itu dapat membagi bilangan yang lain.

=========================================================================
Eit, materi mengenai pigeonhole principle tidak berhenti sampai di sini saja..!!

Masih ada lanjutannya, 

Read More

Mengubah 4 kubus menjadi 3 kubus

Diberikan susunan korek api seperti pada gambar. Terlihat bahwa ada 4 kubus di sana.

Bisakah kalian memindahkan 1 batang korek api, sehingga tersisa 3 kubus?

Puzzle ini diambil juga dari game Professor Layton. (dan sangat mudah sekali, mungkin tidak sampai 1 menit untuk dipecahkan.)

Read More

iseng tanggal lahir

Kadang, temenmu rewel untuk tidak memberitahukan tanggal dan bulan kelahirannya.. Yah, mungkin karena alasan privasi dan sebagainya.. Hahaha. Di sini akan diberitahukan salah satu trik untuk mengetahui tanggal lahir temanmu dengan salah satu permainan teka-teki matematika yang *sangat* sederhana.. XDXD

Berikan instruksi-instruksi di bawah ini pada temanmu sebagai berikut.
1. "Pertama, pikirkan tanggal lahirmu."
2. "Kalikan dengan 5"
3. "Tambahkan dengan 6"
4. "Kalikan dengan 4"
5. "Tambahkan dengan 7"
6. " Kalikan dengan 5"
7. "Selanjutnya, tambahkan dengan bulan kelahiranmu"
8. "Sebutkan angka itu"
9. Kurangkan dengan 165 (Langkah ini hanya boleh kita yang tahu.)

Maka, kita dapat mengetahui tanggal dan bulan lahir temanmu. Sebagai contoh, tanggal lahir temanmu itu 29 dengan bulan 12. Maka, langkahnya seperti ini:
1. Tanggal lahir = 29
2. Kalikan 5: 29x5 = 145
3. Tambahkan 6: 145+6 = 151
4. Kalikan 4: 151x4 = 604
5. Tambahkan dengan 9: 604+9 = 613
6. Kalikan dengan 5: 613x5 = 3065
7. Tambahkan bulan kelahiran: 3065+12 = 3077.
8. Kurangkan dengan 165: 3077-165 = 2912 (Langkah ini hanya kita yang boleh tahu.. Kenapa? Supaya dia mau menyebutkannya.. XDXDXD)

2912 berarti tanggal 29 bulan 12... Mudah bukan??
Bagaimana ini bisa terjadi? Hal ini dapat dijawab dengan mudah, dengan memisalkan tanggal lahir dan bulan lahir sebagai variabel, misalnya x dan y.. Jika dijabarkan, maka akan menghasilkan 100x+y. Sebenarnya, ada contoh lain yang lebih rumit, dengan menggunakan pembagian, modulo, pangkat, akar, dan sebagainya. Teki-teki itu lebih rumit, sehingga tidak dulu dibahas di post ini..

So, temanmu yang sulit memberitahukan tanggal lahirnya tentunya akan ketahuan deh.. Hohohoho.. ^^.. (Btw, kalau untuk mengetahui sekaligus tanggal, bulan, dan tahun lahir, ada lagi cara lain.. Mungkin kamu berniat membuatnya sendiri dengan membentuk 10000x+100y+z dimana x,y, dan z merupakan tanggal, bulan, dan tahun lahir).. ^^

Read More