Pigeonhole Principle ... (ii)

Lanjutan dari post 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.

Sumber:
Majalah Zero ed.2 , download di www.artofmathematics.wordpress.com,
http://en.wikipedia.org/wiki/Pigeonhole_principle,
http://www.cut-the-knot.org/do_you_know/pigeon.shtml, dan
http://zimmer.csufresno.edu/~larryc/proofs/proofs.pigeonhole.html