Pigeonhole principle merupakan salah satu materi dasar terpenting dalam kombinatorika. Meskipun merupakan materi dasar, prinsip ini dapat digunakan untuk menyelesaikan berbagai masalah kombinatorial. Tidak jarang malah memunculkan hasil yang mengejutkan. Prinsip ini memiliki banyak nama yang berbeda, seperti prinsip sarang merpati dan prinsip kotak Dirichlet (Dirichlet's box principle ). Secara kasarnya, Prinsip Sarang Merpati menyatakan bahwa jika terdapat lebih banyak merpati daripada sarang, maka setidaknya ada satu sarang yang ditempati oleh dua atau lebih merpati.
Setidaknya ada dua bentuk dari PHP, yaitu bentuk sederhana dan bentuk yang lebih kuat. Di artikel ini kita akan membahas bentuk sederhananya.
Prinsip Sarang Merpati: Bentuk Paling Sederhana
Dalam bentuk paling sederhananya, prinsip sarang merpati dapat dinyatakan dalam teorema berikut.
Teorema: Prinsip Sarang Merpati 1 (Simplest form)
Bukti teorema ini tergolong mudah. Kita akan membuktikannya dengan reductio ad absurdum. Tapi bagaimana idenya? Coba bayangkan, apa jadinya kalau tiap kotak isinya tidak lebih dari satu objek? Yup. Banyak semua objek pun nantinya tidak sampai \(n + 1\), bertentangan dengan bahwa kita punya \(n + 1\) objek. Pemikiran seperti ini dapat kita tuangkan ke pembuktian sebagai berikut.
Bukti. Andaikan tiap kotak berisi paling banyak \(1\) objek. Karena ada \(n\) kotak, maka total objek paling banyak ada sebanyak \(1 + 1 + 1 + ... + 1 = n\). Kontradiksi. \(\blacksquare\)
Sekarang kita akan mencoba beberapa pemakaian prinsip yang kelihatannya sederhana ini. Catat bahwa PHP tidak memberikan kepada kita kotak mana yang akan terisi lebih dari \(1\) objek, atau berapa isi kotak masing-masing objek. PHP hanya menjamin bahwa selalu ada kotak yang berisi lebih dari satu objek. Dalam penggunaannya, kita harus menentukan mana yang menjadi objek dan mana yang menjadi kotak. Pada praktiknya, bagian inilah yang agak sulit. Kita harus memadukan hal-hal yang telah kita ketahui ataupun melakukan hal-hal yang kreatif. Math is about ideas after all.
Tinjau soal sederhana berikut.
Problem 1.
Dari \(13\) orang, selalu ada setidaknya dua orang yang lahir pada bulan
yang sama.
Apa yang jadi objeknya? Orang yang ada sebanyak \(13\). Kotaknya tentu saja adalah bulan yang ada sebanyak \(12\) bulan. Berdasarkan PHP, selalu ada setidaknya dua orang yang lahir pada bulan yang sama.
Ketika kita memiliki sebuah ide, hal yang sedikit sulit adalah menuangkannya ke dalam kata-kata. Kita mungkin terpikirkan bagaimana menyelesaikan suatu soal, tetapi tidak dapat menuangkannya dengan kata-kata yang cukup baik atau tidak dapat menjelaskan dengan baik. Misalnya saja Problem \(1\) tadi. Kita mungkin berpikir “Orang cuma ada \(12\) bulan koq, kan orangnya ada \(13\) ya pasti ada yang lahir dalam bulan yang sama lah!” Namun, terkadang kita harus dapat menjelaskan sesuatu dengan lebih baik lagi. Karena tidak tiap hal sesederhana yang tadi.
Problem 2.
Dari \(3\) bilangan bulat, selalu ada dua di antaranya yang selisihnya
merupakan bilangan genap. Apakah ini akan tetap berlaku jika genap diganti dengan
ganjil?
Mari berpikir sejenak. Sekarang kotak(sangkar) dan objek(merpati)nya tidak terlihat begitu jelas. Setidaknya tidak sejelas tentang permasalahan bulan lahir tadi. Namun, hal ini bukan berarti kita telah dikalahkan oleh suatu permasalahan. Ketika kita melihat dari sudut pandang yang benar, permasalahan yang awalnya nampak sulit akan menjadi terasa lebih mudah.
Ketika kita stuck pada suatu permasalahan, ada baiknya kita meninjau beberapa kasus khusus. Sekarang kita coba ambil beberapa bilangan. Katakanlah \(2, 3, 5\). Apakah kita punya dua buah yang selisihnya genap? Ada! Yaitu \(3\) dan \(5\). Apa yang begitu spesial dari bilangan-bilangan ini? Untuk melihatnya kita bisa ambil beberapa bilangan lain. Katakanlah \(11, 8, 22\). Sekarang yang selisihnya genap adalah \(8\) dan \(22\). Kita bisa mencoba lebih banyak lagi untuk melihat apa sebenarnya yang terjadi. Tetapi sepertinya yang selisihnya genap adalah dua bilangan genap atau dua bilangan ganjil. Dari observasi ini kita menduga bahwa
Selisih antara dua bilangan genap adalah genap, begitu juga selisih dua bilangan ganjil selalu genap.
(Untuk yang sudah tau tentunya ini bukan hal yang begitu mengejutkan). Bisakah kita membuktikan ini? Pada faktanya hal ini tidak terlalu sulit untuk dibuktikan, tetapi perhatian kita tidak tertuju pada hal ini.
Sekarang tentunya sudah terlihat sedikit lebih jelas apa yang menjadi kotaknya. Yup, himpunan bilangan genap dan himpunan bilangan ganjil, yaitu \[\{. . . , −4, −2, 0, 2, 4, . . . \}\] dan \[\{−3, −1, 1, 3, . . . \}\] dan ini merupakan partisi dari himpunan bilangan bulat. Sekarang terlihat bahwa ketika kita mengambil tiga bilangan bulat, pasti ada dua di antaranya yang masuk ke salah satu himpunan tersebut. Akibatnya, selisih mereka genap.
Hal ini juga dapat dikatakan dengan kalimat yang berbeda: Dari tiga bilangan bulat, selalu ada dua di antaranya yang sama-sama ganjil atau sama-sama genap. Kita akan tinggalkan bukti formalnya kepada pembaca.
Pertanyaan selanjutnya adalah apakah dari tiga bilangan ganjil selalu ada dua di antaranya yang selisihnya ganjil? Tidak! Hanya perlu meninjau \(1, 3, 5\) yang selisihnya semuanya merupakan bilangan genap.
Apa yang begitu spesial dari himpunan bilangan genap ini? Ketika kalian belajar lebih lanjut lagi tentang struktur aljabar, himpunan bilangan genap memiliki struktur yang bagus, baik sebagai grup ataupun sebagai ring. Jangan takut kalau belum mengetahui hal ini, tetapi alangkah baiknya kita mengantisipasi.
Sekarang kita akan ke suatu problem yang sangkar dan burungnya lebih tidak terlihat jelas lagi. Sebelum itu kita akan mendefinisikan istilah baru. Terkadang kita kesulitan menerima istilah baru (seperti istilah grup dan ring di atas). Padahal istilah ini terkadang hanyalah hal-hal yang sederhana ketika kita mengetahuinya. Fobia akan hal baru bukanlah hal yang baik. Selalu ingat itu.
Definisi: Titik Latis
Dari sebarang \(5\) titik latis di \(\mathbb{R}^2\) selalu terdapat dua titik yang titik tengahnya merupakan titik latis.
Bagaimana? Ada bayangan untuk menyelesaikannya? Lihatlah dari berbagai sudut pandang. Menyelesaikan suatu soal dengan cepat memang merupakan hal yang baik, tetapi terkadang bukanlah hal yang diperlukan. Di suatu waktu kita memerlukan waktu lebih untuk berpikir dan merenungkan. Bisa saja jawabannya terlintas begitu saja saat bermain game atau saat sedang di perjalanan. Tidak menyerah adalah hal yang lebih penting dibandingkan menyelesaikan suatu permasalahan dengan cepat. Tips: kamu juga bisa mencoba untuk mengambil beberapa titik untuk melihat apa yang sebenarnya terjadi. Kita akan mengesampingkan hal ini. Buktinya dapat kamu lihat pada solusi Latihan 3 di bawah.
Kita akan mencoba melihat contoh lain. Contoh ini berasal dari teori graf. Namun, kita tidak perlu menginterpretasikannya sebagai graf. Jangan berpikir terlalu sulit, ketika kita berpikir terlalu sulit, pikiran kita juga akan malas malasan memikirkannya. Remember, “memahami matematika tidak seperti membaca novel, it takes time”. Selalu sediakan waktu.
Di suatu pesta terdapat \(n\) orang. Buktikan bahwa ada dua di antara orang-orang tersebut yang memiliki banyak kenalan yang sama.
Di sini diasumsikan bahwa kenal itu dua arah. Bukankah menjadi pengagum rahasia saja, melihatnya dari jauh saja, bukan berarti kenal? Ok abaikan hal ini.
Sekarang apa yang menjadi sangkar dan apa yang menjadi burung? Karena yang ditanyakan adalah banyak kenalan, maka adalah hal yang logis jika kita memikirkan bahwa sangkarnya adalah banyak kenalan dan yang menjadi burung adalah orang-orang tersebut.
Apa saja yang mungkin untuk menjadi banyak kenalan? Seseorang tidak mengenal sama sekali, kenal dengan satu orang, dua orang, ..., atau kenal dengan \(n−1\) orang (kenal dengan semua orang yang ada di pesta tersebut). Jadi, semua kemungkinan banyak kenalannya adalah \[0, 1, 2, . . . , n−1.\] Ada berapa kemungkinan? Yep, ada \(n\) kemungkinan.
Ada \(n\) orang dan \(n\) sangkar. Sepertinya PHP tidak dapat digunakan di sini, karena dalam PHP banyak burungnya harus lebih banyak. Tapi, hey, jangan terlalu cepat untuk menyerah begitu saja.
Sedikit pemikiran: jika ada orang yang tidak kenal sama sekali dengan yang lain, apakah bisa ada orang lain yang kenal semuanya?
Tentu saja tidak. Jadi, sangkar \(0\) dan \(n − 1\) tidak dapat terisi kedua-duanya sekaligus bersamaan. Dengan kata lain, hanya ada \(n − 1\) buah sangkar yang dapat ditempati. Dari sini kita dapat menyimpulkan bahwa selalu ada dua orang yang banyak kenalannya sama.
Selanjutnya kita akan melihat bagaimana PHP dapat digunakan pada keterbagian. Pertama ingat fakta berikut
Kemungkinan sisa suatu bilangan bulat saat dibagi bilangan bulat \(n\) adalah \[0,1,2,3,\dots, n-1.\]
Soal berikut ini merupakan perumuman dari Problem 2 dan cukup mudah untuk dibuktikan dengan menggunakan fakta di atas dan PHP.
Problem 5
Andaikan \(n\) adalah bilangan asli dengan \(n \geq 2\). Tunjukkan bahwa dari sebarang \(n+1\) bilangan bulat berbeda pasti terdapat dua di antaranya yang selisihnya habis dibagi \(n\).
Pembahasan
Berdasarkan PHP, jika kita mengambil \(n + 1\) bilangan, maka ada dua di antaranya yang bersisa sama saat dibagi \(n\). Selisih kedua bilangan ini habis dibagi \(n\).
Salah satu hal yang sangat penting dalam problem solving adalah berlatih. Terlebih lagi dalam hal kombinatorika. Contoh mungkin dapat memberikan kita gambaran, tetapi skill problem solving bisa didapatan ketika kita benar-benar menyelesaikan soal-soal dengan kemampuan kita sendiri. Tidak hanya membaca solusi orang lain.
Latihan
Soal-soal berikut merupakan beberapa penerapan dari prinsip sarang merpati. Beberapa dari soal ini memiliki solusi penuh dan sebagian yang lain hanya berisi petunjuk. Sebagian soal ini diambil dari soal-soal ONMIPA yang dapat diselesaikan dengan prinsip sarang merpati.
Jika \(n+ 1\) bilangan berbeda diambil dari himpunan \(\{1, 2, 3, . . . , 2n\}\), maka ada dua di antaranya yang selisihnya \(1\).
Bagaimana bentuk himpunan yang anggotanya memiliki selisih \(1\)? Ya, cuma \(\{1,2\}\) dan sejenisnya. Jadi, kita bisa partisi himpunan tersebut menjadi \[\{1,2\},\{3,4\},\dots,\{2n - 1, 2n\}.\] Ada berapa himpunan? Jelas ada \(n\) buah himpunan. Jika kita ambil \(n+1\) buah bilangan, berdasarkan PHP, pasti ada dua di antaranya yang masuk ke himpunan sama. Selisih kedua bilangan ini sudah pasti \(1\).
Kalau kalian sudah bisa menyelesaikan Latihan 1 (atau melihat solusinya), Latihan 2 berikut memiliki ide yang sama dan menjadi soal yang lebih mudah. Pastikan untuk mencoba soal di atas dulu.
Jika \(n+ 1\) bilangan berbeda diambil dari himpunan \(\{1, 2, 3, . . . , 3n\}\), maka ada dua di antaranya yang selisihnya tidak lebih dari \(2\).
Cukup buat sangkar-sangkar berikut \begin{align*} &\{1,2,3\},\\ &\{4,5,6\},\\ & \vdots\\ & \{3n - 2, 3n - 1, 3n\} \end{align*} Perhatikan bahwa terdapat \(n\) sangkar dengan tiap sangkar memiliki karakteristik yang sama: selisih setiap pasang anggotanya tidak lebih dari \(2\).
Buktikan Problem 3.
Ini adalah soal yang cukup sulit karena kita dihadapkan dengan persoalan geometri. Akan tetapi, kuncinya adalah memakai koordinat titik tengah. Titik tengah antara koordinat \((x_1,y_1)\) dan \((x_2,y_2)\) adalah \[\left(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2}\right)\] Untuk menjamin koordinat di atas merupakan bilangan bulat, kita cukup menjamin masing-masing penjumlahan habis dibagi \(2\). Kapan jumlah dua bilangan habis dibagi \(2\)? Saat bilangan tersebut sama-sama genap atau sama-sama ganjil. Oleh karena itu, kita dapat mempartisi titik koordinat berdasarkan genap ganjil. Karena masing-masing absis dan ordinat memiliki dua kemungkinan, maka ada total \(2\times 2 = 4\) bentuk koordinat yang mungkin. Kita juga bisa menuliskan semuanya secara manual sebagai berikut \begin{align*} &(\mathrm{genap},\mathrm{genap})\\ &(\mathrm{genap},\mathrm{ganjil})\\ &(\mathrm{ganjil},\mathrm{genap})\\ &(\mathrm{ganjil},\mathrm{ganjil}) \end{align*} Karena ada \(4\) kemungkinan, berdasarkan Prinsip Sarang Merpati pasti ada dua titik dengan bentuk koordinat ganjil genap yang sama. Akibatnya, titik tengahnya merupakan titik latis.
Tidak disangka, soal yang terlihat sangat geometri ini hampir tidak ada geometrinya sama sekali!
Dua soal sebelumnya dapat kita perumum sebagai berikut
Misalkan \(m \geq 2\). Jika \(n+1\) bilangan berbeda diambil dari himpunan \(\{1, 2, 3, . . . , mn\}\), maka ada dua di antaranya yang selisihnya tidak lebih dari \(m - 1\).
Kelompokkan bilangan-bilangan tersebut menjadi \begin{align*} &\{1,2,3\dots,m\}\\ &\{m+1,m+2,\dots,2m\}\\ &~~\vdots\\ &\{m(n-1) + 1,\dots, mn\}. \end{align*}
Jika \(n + 1\) bilangan berbeda diambil dari himpunan \(\{1, 2, 3, . . . , 2n\}\) maka ada dua di antaranya sehingga salah satu bilangan membagi habis yang lain.
Saat melihat soal ini kita tidak ada bayangan apa yang harus dilakukan. Mari kita lihat kasus khususnya. Kita coba untuk mengelompokkan \(1,2,3,\dots,10\) menjadi lima bagian dengan bilangan di tiap bagian selalu membagi yang sekelompok dengannya. Pertama mari kita mencari yang dapat sekelompok dengan \(2\). Berapa bilangan yang dapat dibagi \(2\)? Ya. Empat. Sekarang berapa bilangan yang bisa dibagi \(4\)? Delapan. Kita peroleh satu kelompok \(2,4,8\). Ternyata kita dapat membuat satu kelompok dengan memulai dari suatu bilangan, kemudian mengalikannya dengan \(2\). Kenapa \(2\)? Karena itu bilangan terkecil yang bisa kita pakai agar bilangannya membesar! Jadi, salah satu pengelompokkan yang bisa kita lakukan adalah \begin{align*} &1,2,4,8\\ &3,6\\ &5,10\\ &7\\ &9 \end{align*} Ada berapa kelompok? Lima. Yes! Kita berhasil mengelompokkan bilangan-bilangan ini dengan memulai dari bilangan ganjil kemudian mengalikannya dengan \(2\). Apakah ini bisa dilakukan ke bentuk yang lebih umum? Ya. Pengelompokkannya adalah \begin{align*} &\{1,2,\dots\}\\ &\{3,6,\dots\}\\ &\vdots\\ &\{2n - 1\} \end{align*} Ada \(n\) buah kelompok. Mari kita tulis bukti formalnya.
Bilangan-bilangan \(1,2,\dots,2n\) dapat dituliskan ke dalam bentuk \((2k + 1)2^m\) untuk \(k = 1,2,\dots, n\) dan suatu \(m\). Karena kemungkinan nilai \(k\) hanya ada \(n\) buah, jika kita mengambil \(n + 1\) bilangan maka berdasarkan Prinsip Sarang Merpati ada dua di antara bilangan tersebut yang memiliki nilai \(k\) yang sama. Bilangan yang lebih kecil di antara dua bilangan ini membagi habis yang satunya lagi.
Di suatu pesta terdapat \(n\) orang saling berjabat tangan. Buktikan bahwa selalu ada dua di antaranya yang banyak jabat tangannya sama.
Ini soal yang sama persis dengan Problem 4. "Banyak jabat tangan" di soal ini dapat dianggap sama saja dengan "banyak kenalan" pada soal tersebut.
Buktikan bahwa dari sebarang \(5\) titik di dalam segitiga sama sisi dengan panjang sisi \(2\) satuan selalu terdapat dua titik yang jaraknya tidak lebih dari \(1\).
Bagi daerah bagian dalam dari segitiga tersebut menjadi \(4\) buah segitiga sama sisi dengan sisi \(1\).
Buktikan bahwa dari sebarang \(5\) titik di dalam persegi dengan panjang sisi \(2\) satuan selalu ada dua di antaranya yang jaraknya tidak lebih dari \(\sqrt{2}\).
Bagi daerah dalam persegi tersebut menjadi \(4\) buah persegi dengan sisi \(1\) satuan. Jarak terjauh di dalam masing-masing persegi tersebut adalah \(\sqrt 2\), yaitu panjang diagonalnya.
Dari \(12\) buah bilangan bulat dua digit selalu ada dua buah di antaranya sedemikian sehingga selisihnya berbentuk \(AA\) (bilangan bulat dua digit dengan angka yang sama).
Partisi \(\{10,11,\dots,99\}\) menjadi \begin{align*} &\{10,21,32,43,\dots, 98\}\\ &\{11,22,33\dots,99\}\\ &\{12,23,34\dots,89\}\\ &\vdots\\ &\{20,31,42,\dots,97\}. \end{align*}Selain langsung mempartisi dengan cara seperti di atas, kita juga bisa pakai modulo \(11\). Kenapa? Karena \(AA = 10A + A = 11A\) merupakan kelipatan \(11\).
Buktikan bahwa dari sebarang \(9\) titik di ruang selalu ada dua di antaranya yang titik tengahnya merupakan titik lattice. (Titik latis didefinisikan analog dengan di \(\mathbb{R}^2\)).
Soal ini sudah menjadi mudah karena Problem 3 sudah selesai. Ada berapa kemungkinan ganjil genap yang mungkin? Ya. Ada \(2\cdot2\cdot 2 = 8\).
Bilangan \(1, 2, 3, ..., 10\) disusun pada suatu lingkaran. Buktikan bahwa kita selalu dapat memilih \(3\) bilangan berurutan sedemikan sehingga jumlahnya \(17\) atau lebih.
Misalkan bilangan-bilangan tersebut adalah \(\{a_1,a_2,\dots,a_{10}\}\). Seluruh penjumlahan yang mungkin adalah \begin{align*} &a_1 + a_2 + a_3\\ &a_2 + a_3 + a_4 \\ &\vdots\\ &a_{10} + a_1 + a_2 \end{align*} Perhatikan bahwa setiap bilangan muncul sebanyak \(3\) kali. Akibatnya, total keseluruhannya \[3(1 + 2 + \dots + 10) = 165.\]
Andaikan tidak ada yang jumlahnya lebih dari \(16\), maka penjumlahannya paling besar adalah \(10\cdot 16 = 160\). Kontradiksi. Haruslah salah satu dari penjumlahan tiga bilangan berurutan tersebut bernilai \(17\) atau lebih.
Kita akan buktikan versi yang lebih kuat, yaitu penjumlahannya \(18\) atau lebih.
Misalkan bilangan-bilangan tersebut adalah \(\{a_1,a_2,\dots,a_{10}\}\). Tanpa mengurangi keumuman, andaikan \(a_1 = 1\). Tinjau tiga penjumlahan suku-suku berurutan berikut \begin{align*} &a_2 + a_3 + a_4\\ &a_5 + a_6 + a_7\\ & a_8 + a_9 + a_{10}\\ \end{align*} Masing-masing bilangan muncul satu kali. Akibatnya, total penjumlahannya adalah \(2+3+\dots + 10 = 54\). Namun, jika ketiga penjumlahan tersebut bernilai kurang dari \(18\) totalnya paling besar adalah \(3\times17 = 51\). Kontradiksi. Akibatnya salah satu dari penjumlahan tersebut haruslah bernilai \(18\) atau lebih.
(ONMIPA 2007) Diberikan sebelas buah bilangan bulat berbeda. Buktikan bahwa dua di antara bilangan-bilangan tersebut memiliki selisih yang merupakan kelipatan \(10\).
Ini adalah kasus khusus dari Problem 5 untuk \(n = 10\).
(ONMIPA 2010) Buktikan bahwa dalam sebarang barisan yang terdiri dari \(m\) bilangan bulat terdapat satu atau beberapa suku berurutan yang jumlahnya habis dibagi \(m\).
Terlalu banyak kemungkinan apabila kita memulai dari sembarang suku, belum lagi panjang penjumlahannya berbeda-beda. Daripada kita meninjau penjumlahan sebarang suku berurutan, bagaimana kalau kita mulai dari suku pertama saja? Misalnya saja \[a_1 + a_2 + \dots + a_{15}\]
Pertanyaannya sekarang adalah apakah kita bisa menuliskan suku berurutan lain yang tidak dimulai dari suku pertama? Bisa. Perhatikan bahwa kita bisa menuliskan \[a_7 + a_8 + \dots + a_{15}\] sebagai \[a_1 + \dots + a_{15} - (a_1 + \dots +a_6).\]Kita selalu bisa memotong beberapa suku pertama untuk dihilangkan!
Ide: ketimbang melihat suku-sukunya, kita bisa meninjau jumlah parsialnya dari suku pertama.
Sekarang, kita hanya terdapat \(n\) buah penjumlahan yang harus kita lihat. Ide seperti ini juga dapat kamu coba ke soal yang lain.
Andaikan bilangan-bilangan tersebut adalah \[a_1, a_2, a_3, \dots, a_m.\] Definisikan \[S_k = a_1 + a_2 +\dots + a_k\] untuk \(k = 1,2,\dots, m\).
Jika \(S_k\) habis dibagi \(m\) untuk suatu \(k\), maka bukti selesai karena merupakan penjumlahan \(k\) suku berurutan.
Jika \(S_k\) tidak habis dibagi \(m\), maka sisanya saat dibagi \(m\) adalah \(1,2,\dots, m - 1\). Karena hanya ada \(m - 1\) kemungkinan sisa, berdasarkan Prinsip Sarang Merpati, ada dua di antaranya yang memiliki sisa yang sama saat dibagi \(m\), katakankah \(S_p\) dan \(S_q\) dengan \(p \lt q\). Akibatnya, \(S_q - S_p\) habis dibagi \(m\). Akan tetapi, \[S_q - S_p = a_{p + 1} + \dots + a_q\] yang merupakan penjumlahan suku-suku berurutan.
Dengan demikian, dari barisan dengan \(m\) buah bilangan selalu ada penjumlahan beberapa suku berurutan yang habis dibagi \(m\).
(ONMIPA 2013) Diberikan tujuh bilangan real berbeda. Tunjukkan bahwa selalu dapat dipilih dua di antaranya, sebut \(a\) dan \(b\) yang memenuhi \[0 \lt \frac{a - b}{ab + 1} \lt \sqrt{3}\]
Himpunan bilangan real itu "terlalu besar" untuk kita ambil sebarang bilangan. Karena itulah, kita coba untuk meninjau himpunan yang "lebih kecil" tetapi masih memiliki anggota yang sama banyak dengan \(\mathbb{R}\). Bentuk \[\frac{a - b}{ab + 1}\] mengingatkan kita kepada bentuk identitas tangen dari selisih dua sudut: \[\tan[x - y] = \frac{\tan x - \tan y}{\tan x \tan y + 1}.\]
Karena fungsi tangen merupakan bijeksi dari \((-\frac{\pi}{2},\frac{\pi}{2})\) ke \(\mathbb{R}\), kita dapat menggantikan \(a\) dan \(b\) dengan \(\tan x\) dan \(\tan y\) untuk suatu \(x,y\in(-\frac{\pi}{2},\frac{\pi}{2})\)
Ketaksamaan bagian kiri jelas terpenuhi karena semua bilangan tersebut berbeda. Oleh karena itu, kita cukup membuktikan ketaksamaan kanan.
Andaikan ketujuh bilangan tersebut adalah \[a_1,a_2,\dots,a_7.\] Karena fungsi tangen adalah bijeksi dari \((-\frac{\pi}{2},\frac{\pi}{2})\) ke \(\mathbb{R}\), maka terdapat \(x_i\in (-\frac{\pi}{2},\frac{\pi}{2})\) sedemikian sehingga \[a_i = \tan x_i,\quad i =1,2,...,7.\]
Partisi \((-\frac{\pi}{2},\frac{\pi}{2})\) menjadi \(6\) bagian sama besar, yaitu \begin{align*} &\left(-\frac{\pi}{2},-\frac{\pi}{3}\right]\\ &\left(-\frac{\pi}{3},-\frac{\pi}{6}\right]\\ &~~~~~~~\vdots\\ &\left(\frac{\pi}{3},\frac{\pi}{2}\right) \end{align*}
Karena ada \(7\) buah \(x_i\), maka ada dua di antaranya yang masuk ke himpunan yang sama, katakanlah \(x_m\) dan \(x_n\) dan WLOG \(x_m \lt x_n\). Akibatnya selisih kedua bilangan tersebut kurang dari \(\frac{\pi}{6}\). Kemudian karena tangen naik pada \([0,\frac{\pi}{2})\) maka \begin{align*} \frac{a_n - a_n}{a_na_m + 1} &= \frac{\tan x_n - \tan x_m}{\tan x_n \tan x_m + 1}\\ &= \tan(x_n - x_m)\\ & \lt\tan \frac{\pi}{6}\\ & =\frac{1}{3}\sqrt 3\\ & \lt \sqrt 3 \end{align*}
Remark: Seperti kita lihat pada pengerjaan kita di atas, ketaksamaan yang diberikan pada soal dapat dibuat lebih kuat dengan mengganti \(\sqrt 3\) dengan \(\frac{1}{3}\sqrt 3\). Di sisi lain, kita juga dapat hanya memilih \(4\) bilangan untuk menjamin ketaksamaan berlaku.
(ONMIPA 2014) (versi lebih umum dari sebelumnya). Sebuah titik \((a_1, a_2, . . . , a_k) \in \mathbb{R}^k\) dikatakan sebuah titik lattice jika \(a_i\) adalah bilangan bulat untuk semua \(i = 1, 2, 3 . . . , k\). Perlihatkan bahwa setiap himpunan \(L_k\) yang terdiri dari \(2k+1\) buah titik lattice, terdapat dua titik lattice \(l_1, l_2 \in L_k\) sedemikian sehingga titik tengah dari \(l_1\) dan \(l_2\) adalah sebuah titik lattice.
Sama seperti Problem 3 dan Latihan 10, kemungkinan koordinatnya ada sebanyak \(2^n\).
(ONMIPA 2016) Perlihatkan bahwa untuk setiap himpunan yang terdiri dari \(7\) bilangan bulat berbeda terdapat dua bilangan \(x\) dan \(y\) pada himpunan tersebut sedemikian sehingga \(x + y\) atau \(x - y\) adalah kelipatan \(10\).
Kemungkinan sisa suatu bilangan saat dibagi \(10\) adalah \[0,1,2,\dots,9.\] Kita akan mengelompokkannya (membuat sarang merpati) menjadi beberapa himpunan dengan sifat: selisih atau jumlah di himpunan tersebut habis dibagi \(10\). Pengelompokkan ini adalah \[\{0\},\{5\},\{1,9\},\{2,8\},\{3,7\},\{4,6\}\]
Saat kita mengambil \(7\) bilangan, pasti ada dua di antaranya yang masuk ke himpunan yang sama. Akibatnya, selisih atau jumlahnya habis dibagi \(10\).
Jumlah dan selisih selalu mengingatkan kita kepada selisih kuadrat: \[(x - y)(x + y) =x^2 - y^2.\]
Mari kita coba apakah sifat ini bisa kita gunakan. Andaikan \(x - y\) atau \(x + y\) habis dibagi \(10\) maka \[(x - y)(x + y)\equiv 0 ~(\mathrm{mod}\ 10)\] maka \[x^2 \equiv y^2 ~(\mathrm{mod}~10).\] Ini artinya \(x^2\) dan \(y^2\) memiliki sisa yang sama saat dibagi \(10\). Oleh karena itu, mari kita lihat apa saja kemungkinan sisa bilangan kuadrat saat dibagi \(10\). Kemungkinannya hanyalah \(0,1,4,5,6,9\). Sekarang kita buat ini menjadi bukti formal dan memastikan langkahnya dapat dibalik.
BuktiSisa bilangan kuadrat saat dibagi \(10\) ada \(6\) kemungkinan, yaitu \(0,1,4,5,6,9\). Berdasarkan PHP, jika kita ambil \(7\) bilangan, maka ada dua di antaranya yang kuadratnya bersisa sama saat dibagi \(10\). Katakanlah bilangan-bilangan tersebut adalah \(x\) dan \(y\). Dengan kata lain, \begin{align*} x^2 \equiv y^2~(\mathrm{mod}~10)\\ (x - y)(x + y)\equiv 0~(\mathrm{mod}~10) \end{align*}
Kita tidak dapat langsung memastikan bahwa \(x - y\) atau \(x + y\) habis dibagi \(10\) karena \(10\) bukan bilangan prima. Akan tetapi, andaikan keduanya tidak habis dibagi \(10\) maka \begin{align*}x - y &\equiv 2~(\mathrm{mod}~10)\\&\mathrm{dan}\\ x + y &\equiv 5~(\mathrm{mod}~10) \end{align*}(atau sebaliknya). Namun, sistem kongruensi ini tidak memiliki solusi karena saat kita menambahkan keduanya diperoleh \(2x \equiv 7 ~(\mathrm{mod}~10)\) yang tidak memiliki solusi.
Oleh karena itu, haruslah \(x - y\) habis dibagi \(10\) atau \(x + y\) habis dibagi \(10\).
(ONMIPA 2017) Seorang petinju mempunyai waktu \(75\) minggu untuk mempertahankan gelar. Untuk itu pelatih menjadwalkan program latih tanding. Pelatih merencanakan sedikitnya terdapat satu latih tanding dalam satu minggu, tetapi tidak lebih dari total \(125\) latih tanding dalam periode \(75\) minggu. Perlihatkan ada periode waktu yang terdiri atas beberapa minggu berurutan sehingga terdapat tepat \(24\) latih tanding dalam waktu tersebut.
Kita bisa menggunakan ide yang sama dengan Latihan 13, yaitu meninjau jumlah parsialnya.
Andaikan banyaknya latih tanding dari minggu pertama hingga minggu ke-\(75\) adalah \[a_1,a_2,\dots,a_{75}.\]
Tinjau jumlah parsialnya, yaitu \(S_k = a_1 + a_2 + \dots + a_k\) untuk \(k = 1,2,\dots, 75\). Karena \(a_k \geq 1\) untuk setiap \(k\), maka \(S_k\) adalah barisan naik (karena bertambah minimal satu). Selain itu, karena total latih tanding tidak boleh dari \(125\), kita juga dapatkan \(S_{75} \leq 125\). Akibatnya, \[1 \leq S_1 \lt S_2 \lt \dots S_{75} \leq 125.\]
Dengan kata lain, \(S_1\) sampai \(S_{75}\) adalah \(75\) bilangan berbeda yang ada di antara \(1\) sampai \(125\).
Jika ada dua di antara bilangan tersebut yang selisihnya \(24\), maka bukti selesai. Bagaimana kita menunjukkan hal ini?
Ini tidak terlihat begitu jelas sehingga kita membutuhkan argumentasi tambahan.
Kita bisa tinjau barisan lain. Kita akan memaksa agar ada yang selisihnya \(24\). Oleh karena itu, kita coba tambahkan \(24\) ke bilangan yang sudah kita dapat sebelumnya, yaitu \[S_1+24, S_2 + 24, \dots, S_{75} + 24\] ini juga merupakan barisan naik sehingga \[\small 25 \leq S_1 + 24 \lt S_2 + 24\lt \dots \lt S_{75} + 24 \leq 149.\]
Dengan demikian, \(S_1,S_2, \dots, S_{75},\dots,S_1 + 24,\dots , S_{75} + 24\) adalah \(150\) bilangan dari \(1\) sampai \(149\). Ada \(150\) bilangan sementara dari \(1\) sampai \(149\) hanya ada \(149\) bilangan. Berdasarkan Prinsip Sarang Merpati, ada dua di antaranya yang nilainya sama. Karena \(S_1\) sampai \(S_{75}\) semuanya berbeda dan \(S_1 + 24\) sampai \(S_{75}+24\) semuanya juga berbeda, maka yang sama adalah \(S_i\) dan \(S_j + 24\) untuk suatu \(i\) dan \(j\). Akibatnya \begin{align*} S_i &= S_j + 24\\ S_i - S_j &= 24\\ a_{j + 1} + a_{j+2} + \dots + a_{i} &=24\\ \end{align*}
Dengan kata lain, ada beberapa minggu berurutan yang total latih tandingnya adalah \(24\).
(ONMIPA 2018) Andaikan \(G\) adalah sebuah graf sederhana (simple graph). Bila \(e\) adalah sebuah sisi yang menghubungkan titik \(u\) dan titik \(v\) di \(G\), maka dikatakan bahwa titik \(u\) bertetangga dengan titik \(v\). Derajat dari sebuah titik \(v\) di 𝐺 adalah banyaknya titik-titik yang bertetangga dengan \(v\). Perlihatkan bahwa pada sebuah graf sederhana \(G\) terdapat sedikitnya dua titik dengan derajat sama.
Seperti Latihan 6, ini hanyalah Problem 4 yang ditulis dengan istilah berbeda. Ganti "kenalan" dengan "sisi" dan "orang" dengan "titik" pada jawaban Problem 4.
(KNMIPA 2020) Diberikan himpunan \(A = \{a_1,a_2,\dots,a_n\}\). Andaikan dipilih \(2^{n-1} + 1\) himpunan bagian dari \(A\). Tunjukkan bahwa pasti ada dua di antaranya yang merupakan subset dari yang lain.
Jika \(A\) kosong, maka pernyataan tersebut jelas terbukti. Oleh karena itu, andaikan \(A\) tak kosong.
Andaikan \(A_k\) himpunan-himpunan bagian yang tidak memuat \(a_1\). Jelas bahwa ada sebanyak \(2^{n - 1}\) himpunan dengan sifat tersebut (setengah dari seluruh subset dari \(A\)). Partisi himpunan kuasa dari \(A\) menjadi \begin{align*} & \{A_1, A_1 \cup \{a_1\}\}\\ &\{A_2, A_2 \cup \{a_1\}\}\\ &\vdots\\ &\{A_{2^{n-1}}, A_{2^{n-1}} \cup\{a_1\}\}. \end{align*} Perhatikan bahwa setiap himpunan dalam himpunan tersebut adalah subset dari yang lain. Berdasarkan Pigeonhole principle Jika kita mengambil \(2^{n - 1}+1\) himpunan, pasti ada dua yang masuk ke dalam himpunan yang sama. Akibatnya, salah satunya pasti subset dari yang lain.
Argumen yang sama dengan yang kita gunakan pada Latihan 19 dapat digunakan untuk membuktikan bahwa juga ada dua di antaranya yang irisannya himpunan kosong.
Posting Komentar
Posting Komentar