Proposisi 4.1. Prinsip Sarang Merpati.
Jika \(f:X\longrightarrow Y\) adalah suatu fungsi dan \(|X|>|Y|\text{,}\) maka terdapat sebuah unsur \(y\in Y\) dan unsur-unsur berbeda \(x,x'\in X\) sedemikian sehingga \(f(x)=f(x')=y\text{.}\)
Subbab 4.1 Prinsip Sarang Merpati
Suatu fungsi \(f:X\longrightarrow Y\) dikatakan \(1\)–\(1\) (dibaca satu-ke-satu) apabila \(f(x)\neq f(x')\) untuk setiap \(x,x'\in X\) dengan \(x\neq x'\text{.}\) Fungsi \(1\)–\(1\) juga disebut suatu injeksi, atau kita mengatakan bahwa \(f\) bersifat injektif. Apabila \(f:X\longrightarrow Y\) bersifat \(1\)–\(1\text{,}\) kita perhatikan bahwa \(|X|\le |Y|\text{.}\) Sebaliknya, kita mempunyai pernyataan jelas berikut, yang dikenal luas sebagai prinsip “Sarang Merpati”.
Dalam bahasa yang lebih santai, jika Anda harus memasukkan \(n+1\) merpati ke dalam \(n\) sarang, maka setidaknya dua merpati harus dimasukkan ke sarang yang sama.
Berikut adalah hasil klasik yang pembuktiannya segera diperoleh dari Prinsip Sarang Merpati.
Teorema 4.2. Teorema Erdős–Szekeres.
Jika \(m\) dan \(n\) adalah bilangan bulat tak negatif, maka setiap barisan yang terdiri atas \(mn+1\) bilangan real berbeda memiliki subbarisan menaik dengan \(m+1\) suku atau subbarisan menurun dengan \(n+1\) suku.
Bukti.
Misalkan \(\sigma=(x_1,x_2,x_3,\dots,x_{mn+1})\) adalah barisan yang terdiri atas \(mn+1\) bilangan real berbeda. Untuk setiap \(i=1,2,\dots,mn+1\text{,}\) misalkan \(a_i\) adalah banyaknya suku maksimum dalam suatu subbarisan menaik dari \(\sigma\) yang suku pertamanya adalah \(x_i\text{.}\) Misalkan pula \(b_i\) adalah banyaknya suku maksimum dalam suatu subbarisan menurun dari \(\sigma\) yang suku terakhirnya adalah \(x_i\text{.}\) Jika terdapat suatu \(i\) dengan \(a_i\ge m+1\text{,}\) maka \(\sigma\) memiliki subbarisan menaik yang terdiri atas \(m+1\) suku. Demikian pula, jika untuk suatu \(i\) berlaku \(b_i\ge n+1\text{,}\) maka kita menyimpulkan bahwa \(\sigma\) memiliki subbarisan menurun yang terdiri atas \(n+1\) suku.
Tinggal kita pertimbangkan kasus ketika \(a_i\le m\) dan \(b_i\le n\) untuk setiap \(i=1,2,\dots,mn+1\text{.}\) Karena terdapat \(mn\) pasangan terurut berbentuk \((a,b)\) dengan \(1\le a\le m\) dan \(1\le b\le n\text{,}\) berdasarkan prinsip Sarang Merpati kita menyimpulkan bahwa pasti terdapat bilangan bulat \(i_1\) dan \(i_2\) dengan \(1\le i_1\lt i_2\le mn+1\) sedemikian sehingga \((a_{i_1},b_{i_1})=(a_{i_2},b_{i_2})\text{.}\) Karena \(x_{i_1}\) dan \(x_{i_2}\) berbeda, berlaku \(x_{i_1}\lt x_{i_2}\) atau \(x_{i_1}>x_{i_2}\text{.}\) Dalam kasus pertama, setiap subbarisan menaik yang suku pertamanya adalah \(x_{i_2}\) dapat diperpanjang dengan menempatkan \(x_{i_1}\) di awal. Hal ini menunjukkan bahwa \(a_{i_1}>a_{i_2}\text{.}\) Dalam kasus kedua, setiap subbarisan menurun yang suku terakhirnya adalah \(x_{i_1}\) dapat diperpanjang dengan menambahkan \(x_{i_2}\) di bagian paling akhir. Hal ini menunjukkan bahwa \(b_{i_2}>b_{i_1}\text{.}\)
Dalam Bab 11, kita akan mempelajari beberapa perumuman kuat dari Prinsip Sarang Merpati. Semua hasil ini mencerminkan gagasan umum bahwa ketidakteraturan mutlak tidak mungkin terjadi.
