Pigeonhole Principle merupakan salah satu teorema matematika yang menarik..
Pigeonhole Principle:
Jika k + 1 merpati dimasukkan ke dalam k rumah, maka ada satu rumah yang berisi paling tidak 2 merpati.
Note: jumlah k+1 itu tidak wajib. Asalkan jumlah merpati lebih besar dari jumlah rumahnya, maka prinsip ini selalu berlaku.
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.
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??
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...
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).
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.
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.
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.
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.
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.
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.
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.
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. |
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:
Soal di atas diambil a = 0 dan n=50.
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.
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.
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.
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.
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:
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 
.
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.
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.
No comments:
Post a Comment