Prinsip Sangkar Burung dalam ON MIPA-PT Matematika

ON MIPA-PT Matematika adalah sebuah kompetisi matematika yang terdiri dari 5 materi, yaitu Kombinatorika, Aljabar Linear, Struktur Aljabar, Analisis Real, dan Analisis Kompleks. Kami telah menyajikan pembahasan soal beberapa tahun sebelumnya. Pembahasan tersebut dibuat per bagian materi. Sebagai contoh, kita pernah membahas Soal Kombinatorika Uraian Tahun 2009.

Nah, kali ini, kita akan membahas dengan cara yang berbeda, yaitu per topik. Dalam tulisan ini, kita membahas salah satu topik pada materi Kombinatorika, yaitu Pigeonhole Principle, atau dalam bahasa indonesia disebut Prinsip Sangkar Burung.

Prinsip Sangkar Burung merupakan topik yang muncul hampir setiap tahun dalam pelaksanaan ON MIPA-PT Matematika tingkat wilayah. Kami mencatat, sejak tahun 2006 sampai tahun kemarin, 2019, topik Prinsip Sangkar Burung muncul setiap tahunnya dalam bentuk soal uraian, kecuali pada tahun 2012.

Sebelumnya, pembahasan soal ini kami tulis di website MathPro.id. Namun, karena suatu alasan, pembahasan tersebut kami pindahkan ke website ini.

Tulisan ini adalah bagian dari seri Pembahasan Soal ON MIPA-PT Matematika. Jadi, setelah membaca tulisan ini, pastikan anda mengetuk tautan tersebut. Di sana tersedia pembahasan soal-soal ON MIPA-PT lainnya.

Tahun 2006

Misal $(x_i,y_i,z_i)$, $i=1,2,\cdots,9$, adalah himpunan 9 titik berbeda dengan koordinat bulat pada ruang $xyz$. Tunjukkan bahwa titik tengah dari garis yang menghubungkan sedikitnya satu pasang dari titik-titik tersebut berkoordinat bulat.

Misal $(a,b,c)$ adalah sebarang titik berkoordinat bulat pada ruang $xyz$. Komponen pertama ($a$) dapat bernilai ganjil atau genap. Begitupun dengan komponen kedua ($b$) dan ketiga ($c$). Berdasarkan aturan perkalian, terdapat $2 \cdot 2 \cdot 2=8$ komposisi yang mungkin. Kita bentuk sebuah himpunan untuk setiap komposisi.

Misal $o$ menyatakan bilangan ganjil dan $e$ menyatakan bilangan genap. Sehingga 8 komposisi yang dimaksud adalah$$ooo,ooe,oeo,oee,eoo,eoe,eeo,eee$$Semua titik dengan komposisi $oeo$ memiliki komponen pertama ganjil ($o$), komponen kedua genap ($e$), dan komponen ketiga ganjil ($o$). Aturan ini juga berlaku untuk komposisi lainnya.

Pada soal, terdapat 9 titik berbeda. Padahal, kita hanya punya 8 komposisi. Berdasarkan Prinsip Sangkar Burung, terdapat 2 titik dengan komposisi sama. Misal kedua titik tersebut adalah $(a_1,b_1,c_1)$ dan $(a_2,b_2,c_2)$. Karena komposisi kedua titik ini sama, maka $a_1+a_2$, $b_1+b_2$, dan $c_1+c_2$ adalah bilangan genap.

Ingat! Jumlah dua bilangan genap adalah genap dan jumlah dua bilangan ganjil adalah genap.

Tulis$$\begin{aligned}&a_1+a_2 = 2p, \quad &\text{untuk suatu } p \in \mathbb{Z} \\&b_1+b_2 = 2q, &\text{untuk suatu } q \in \mathbb{Z} \\&c_1+c_2 = 2r, &\text{untuk suatu } r \in \mathbb{Z}\end{aligned}$$

Titik tengah dari ruas garis yang menghubungkan $(a_1,b_1,c_1)$ dan $(a_2,b_2,c_2)$ adalah$$\begin{aligned}\left(\frac{a_1+a_2}{2},\frac{b_1+b_2}{2},\frac{c_1+c_2}{2} \right) &= \left(\frac{2p}{2},\frac{2q}{2},\frac{2r}{2} \right) \\&= (p,q,r)\end{aligned}$$Karena $p,q,r \in \mathbb{Z}$ maka titik tengah dari ruas garis tersebut berkoordinat bulat. Terbukti.

Tahun 2007

Diberikan sebelas buah bilangan bulat berbeda. Buktikan bahwa dua di antara bilangan-bilangan tersebut memiliki selisih yang merupakan kelipatan 10.

Berikut adalah proposisi yang akan kita gunakan.

Kita bentuk himpunan $A_i$, untuk $i=0,1,\ldots,9$, dengan $A_i=\{ x \in \mathbb{Z} \mid x \equiv i \pmod{10} \}$. Berdasarkan Proposisi 1, setiap bilangan bulat dapat kita kelompokkan ke tepat satu dari himpunan-himpunan ini.

Secara sederhana, kita mengelompokkan semua bilangan bulat dengan satuan $i$ ke dalam himpunan $A_i$.

Kita telah membentuk sepuluh himpunan. Berdasarkan Prinsip Sangkar Burung, jika diberikan sebelas bilangan bulat, maka terdapat dua bilangan yang berasal dari himpunan yang sama. Misalkan himpunan tersebut adalah $A_k$, untuk suatu $k \in \{0,1,\ldots,9\}$, dan kedua bilangan yang dimaksud adalah $a,b \in \mathbb{Z}$.

Sebagai anggota $A_k$, $a$ dan $b$ secara berturut-turut memenuhi $a \equiv k \pmod{10}$ dan $b \equiv k \pmod{10}$. Berdasarkan Proposisi 2 diperoleh, $a-b \equiv k-k \pmod{10}$ atau $a-b \equiv 0 \pmod{10}$. Artinya, $10 \mid a-b$. Jadi, terdapat dua bilangan dengan selisih merupakan kelipatan 10. Terbukti.

Tahun 2008

Perlihatkan bahwa bila $n+1$ bilangan bulat dipilih dari himpunan $\{ 1,2,\ldots,mn \}$ untuk suatu bilangan bulat $m \geq 2$, maka terdapat dua bilangan bulat yang selisihnya tidak lebih dari $m-1$.

Berikut adalah proposisi yang akan kita gunakan

Misalkan $m,n \in \mathbb{Z}$ dengan $m \geq 2$ dan $S=\{1,2, \ldots , mn \}$. Kita partisi himpunan $S$ menjadi $A_i$ untuk $i=1,2,\ldots,n$ dengan$$A_i=\{x \in S \mid (i-1)m < x \leq im \}$$

Kita telah membentuk sebanyak $n$ himpunan. Berdasarkan Prinsip Sangkar Burung, jika kita memilih $n+1$ bilangan bulat dari $S$, maka terdapat dua bilangan yang berasal dari himpunan yang sama. Misalkan himpunan tersebut adalah $A_k$ untuk suatu $k \in \{1,2,\ldots,n\}$ dan kedua bilangan yang dimaksud adalah $a$ dan $b$. Perhatikan bahwa $a,b \in A_k$ berakibat$$\begin{aligned}&(k-1)m < a \leq km \quad &\ldots \ldots (1) \\&(k-1)m < b \leq km \quad &\ldots \ldots (2) \\\end{aligned}$$Gunakan sifat distributif, lalu kalikan setiap ruas pertidaksamaan $(2)$ dengan $-1$, diperoleh$$\begin{aligned}km-m < a \leq km \quad \Rightarrow \quad &km-m < a \text{ dan } a \leq km \\-km \leq -b < -km+m \quad \Rightarrow \quad &-km \leq -b \text{ dan } -b < -km+m \\\end{aligned}$$

Dari sini, kita punya $km-m < a$ dan $-km \leq -b$. Berdasarkan Proposisi 1, diperoleh $\textcolor{red}{-m < a-b}$. Selain itu, kita juga punya $a \leq km$ dan $-b < -km+m$. Berdasarkan Proposisi 3, diperoleh $\textcolor{red}{a-b < m}$.

Perhatikan pertidaksamaan yang dicetak dengan warna merah. Dari keduanya, diperoleh $-m < a-b < m$ yang dapat ditulis sebagai $\mid a-b \mid < m$. Karena $a-b$ dan $m$ adalah bilangan bulat, maka bentuk ini sama saja dengan $\mid a-b \mid \leq m-1$. Artinya, selisih dari $a$ dan $b$ tidak lebih dari $m-1$. Terbukti.

Tahun 2009 (Uraian)

Dari 400 bilangan bulat $1,2,\ldots,400$ dipilih 201 bilangan. Buktikan bahwa di antara 201 bilangan bulat terpilih terdapat 2 bilangan sehingga satu dari bilangan tersebut akan membagi bilangan yang lain.

Misalkan $S=\{1,2,3, \ldots , 400 \}$. Perhatikan bahwa setiap anggota $S$ dapat ditulis sebagai $2^n \cdot k$, dengan $n$ bilangan bulat non negatif dan $k$ bilangan ganjil positif. Sebagai contoh, kita dapat menuliskan 24 sebagai $2^3 \cdot 3$. Namun, $2^2 \cdot 6$ bukanlah penulisan yang dimaksud, karena 6 bukan bilangan ganjil.

Karena $k$ ganjil, maka nilai $k$ yang mungkin adalah anggota dari $\{ 1,3,5, \ldots , 399 \}$. Sehingga terdapat 200 nilai $k$ yang mungkin. Berdasarkan Prinsip Sangkar Burung, jika kita memilih 201 bilangan, maka terdapat 2 bilangan dengan nilai $k$ sama. Misalkan kedua bilangan itu adalah $a=2^m \cdot k$ dan $b=2^n \cdot k$, untuk suatu bilangan bulat non negatif $m$ dan $n$. Jika $m < n$ maka $a \mid b$. Sedangkan, jika $m > n$ maka $b \mid a$. Dengan demikian, terdapat dua bilangan sehingga salah satu bilangan membagi bilangan yang lain. Terbukti.

Tahun 2010

Buktikan bahwa dalam sebarang barisan yang terdiri dari $m$ bilangan bulat terdapat satu atau beberapa suku berurutan yang jumlahnya habis dibagi $m$.

Berikut adalah proposisi yang akan kita gunakan

Misalkan $A:=\left( a_1,a_2,\ldots,a_m \right)$ adalah barisan bilangan bulat. Kita bentuk barisan $B:= \left( b_1,b_2,\ldots,b_m \right)$ dengan$$b_i = a_1+a_2+\ldots+a_i, \quad \text{untuk } i=1,2,\ldots,m$$Jika $B$ mempunyai suku yang habis dibagi $m$, sebutlah $B_z$, maka kita telah menemukan beberapa suku berurutan dari $A$ yang jumlahnya habis dibagi $m$, yaitu$$a_1,a_2, \ldots, a_z$$Terbukti. Namun, bagaimana jika $B$ tidak mempunyai suku yang habis dibagi $m$? Nah, sesuai judul, kita menggunakan Prinsip Sangkar Burung. Berdasarkan Proposisi 4, setiap suku dari $B$ kongruen modulo $m$ dengan tepat satu dari $\{0,1,\ldots,m-1\}$. Namun, tidak ada suku dari $B$ yang habis dibagi $m$, sehingga yang tersisa adalah $\{1,2,\ldots,m-1\}$. Untuk $j=1,2,\ldots,m-1$, kita bentuk himpunan $H_j$ yang berisi suku-suku dari $B$ yang kongruen modulo $m$ dengan $j$.

Terdapat $m-1$ himpunan dan barisan $B$ terdiri dari $m$ suku. Berdasarkan Prinsip Sangkar Burung, terdapat dua suku yang berasal dari himpunan yang sama, sebutlah $H_k$ untuk suatu $k \in \{1,\ldots,m-1\}$. Misalkan $b_x$ dan $b_y$ adalah dua anggota $H_k$ yang dimaksud, sehingga $b_x \equiv k \pmod{m}$ dan $b_y \equiv k \pmod{m}$. Tanpa mengurangi perumuman, kita asumsikan $x>y$. Berdasarkan Proposisi 5, diperoleh $b_x-b_y \equiv 0 \pmod{m}$. Artinya $m \mid b_x-b_y$.

Karena $x>y$, maka$$\begin{aligned}b_x &= \textcolor{red}{a_1+a_2+\ldots+a_y}+a_{y+1}+a_{y+2}+\ldots+a_x \\b_x &= \textcolor{red}{b_y}+a_{y+1}+a_{y+2}+\ldots+a_x \\b_x-b_y &= a_{y+1}+a_{y+2}+\ldots+a_x\end{aligned}$$Dengan demikian, $m$ habis membagi $a_{y+1}+a_{y+2}+\ldots+a_x$ yang merupakan jumlah beberapa suku berurutan dari $A$. Terbukti.

Tahun 2011 (Uraian)

Pada suatu acara seminar matematika dihadiri oleh $n$ orang peserta seminar. Tunjukkan bahwa di antara para peserta seminar tersebut, senantiasa terdapat dua orang peserta seminar yang mempunyai jumlah kenalan yang sama.

Terdapat $n$ orang peserta seminar. Kita tinjau satu orang peserta, sebutlah $x$. Jumlah kenalan yang mungkin dimiliki oleh $x$ adalah anggota dari $\{ 0,1,2,\ldots,n-1 \}$. Dalam hal ini, $0$ jika $x$ tidak punya kenalan dan $n-1$ jika $x$ mengenal semua peserta seminar.

Perhatikan bahwa, kondisi dimana terdapat peserta dengan $0$ kenalan dan peserta lain dengan $n-1$ kenalan, tidak mungkin terjadi secara bersamaan. Dengan kata lain, jika terdapat peserta dengan $0$ kenalan maka pasti tidak ada peserta dengan $n-1$ kenalan. Begitupun sebaliknya.

Kita dapat membuktikan pernyataan tersebut dengan kontradiksi. Asumsikan terdapat peserta $a$ dengan $0$ kenalan dan peserta $b$ dengan $n-1$ kenalan. Karena total peserta adalah $n$, maka $b$ mengenal seluruh peserta lain, termasuk $a$. Akibatnya, $a$ punya sedikitnya $1$ orang kenalan. Terjadi kontradiksi.

Dengan demikian, jumlah kenalan yang mungkin adalah anggota dari $\{ 0,1,2,\ldots,n-2 \}$ atau $\{ 1,2,\ldots,n-1 \}$. Kedua himpunan ini mempunyai kardinalitas yang sama, yaitu $n-1$. Karena terdapat $n$ peserta, maka berdasarkan Prinsip Sangkar Burung, senantiasa terdapat dua orang peserta dengan jumlah kenalan sama. Terbukti.

Tahun 2013 (Uraian)

Diberikan tujuh bilangan real. Tunjukkan bahwa selalu dapat dipilih dua di antaranya, sebut saja $a$ dan $b$, yang memenuhi $0 < \frac{a-b}{ab+1} < \sqrt{3}$.

Berikut adalah Proposisi yang kita gunakan

Untuk setiap bilangan real $x$, terdapat $y \in \left( -\frac{\pi}{2},\frac{\pi}{2} \right)$ sedemikian sehingga $x=\tan y$. Interval $\left( -\frac{\pi}{2},\frac{\pi}{2} \right)$ mempunyai panjang $\pi$. Kita bagi interval ini menjadi 6 bagian, sehingga panjang setiap bagian adalah $\frac{\pi}{6}$. Akibatnya, jarak terpanjang yang mungkin antara dua bilangan pada sebuah bagian adalah $\frac{\pi}{6}$.

Kita tidak perlu memperhatikan interval mana yang terbuka, tertutup, atau setengah tertutup. Karena interval-interval dengan kedua titik ujung sama, pasti memiliki panjang yang sama. Meskipun salah satu interval terbuka, sedangkan interval lainnya tertutup.

Berdasarkan Prinsip Sangkar Burung, jika diberikan tujuh bilangan real maka selalu ada dua bilangan, sebutlah $a$ dan $b$ dengan $a=\tan \alpha$ dan $b=\tan \beta$ untuk suatu $\alpha,\beta \in \left( -\frac{\pi}{2},\frac{\pi}{2} \right)$, di mana $\alpha$ dan $\beta$ terletak pada bagian yang sama. Tanpa mengurangi perumuman, kita misalkan $\alpha > \beta$. Karena terletak pada bagian interval yang sama, maka berlaku $0 < \alpha-\beta \leq \frac{\pi}{6}$.

Perhatikan bahwa fungsi tangen monoton naik pada interval $\left( -\frac{\pi}{2},\frac{\pi}{2} \right)$, sehingga$$\begin{aligned}\tan 0 &< \tan (\alpha-\beta) \leq \tan \frac{\pi}{6} \quad \quad &[ \text{Fungsi tangen monoton naik}] \\\Longleftrightarrow \quad \quad 0 &< \frac{\tan \alpha-\tan \beta}{\tan \alpha \tan \beta + 1} \leq \frac{\sqrt{3}}{3} &[\text{Proposisi 6}] \\\Longleftrightarrow \quad \quad 0 &< \frac{a-b}{ab + 1} \leq \frac{\sqrt{3}}{3} &[a=\tan \alpha \text{ dan } b=\tan \beta]\end{aligned}$$Karena $\frac{\sqrt{3}}{3} < \sqrt{3}$, maka diperoleh $0 < \frac{a-b}{ab + 1} < \sqrt{3}$. Terbukti.

Tahun 2014

Sebuah titik $(a_1,a_2,\ldots,a_k) \in \mathbb{R}^k$ dikatakan sebuah titik lattice jika $a_i$ adalah bilangan bulat untuk semua $i=1,2,\ldots,k$. Perlihatkan bahwa setiap himpunan $L_k$ yang terdiri dari $2^k+1$ buah titik lattices, 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.

Misalkan $x=(a_1,a_2,\ldots,a_k)$ adalah sebarang titik lattice pada $\mathbb{R}^k$. Kita akan menghitung banyaknya komposisi, berdasarkan ganjil-genapnya komponen-komponen suatu titik. Komponen pertama ($a_1$) dapat bernilai ganjil atau genap, begitupun dengan $a_2,a_3, \ldots, a_k$. Berdasarkan aturan perkalian, diperoleh banyaknya komposisi titik yang mungkin, yaitu $2^k$.

Misalkan $L_k$ adalah sebarang himpunan yang terdiri dari $2^k+1$ titik lattice. Karena terdapat $2^k$ komposisi yang mungkin, maka berdasarkan Prinsip Sangkar Burung, terdapat dua anggota $L_k$ yang memiliki komposisi sama. Misalkan kedua anggota tersebut adalah $l_1$ dan $l_2$, dengan $l_1=(u_1,u_2,\ldots,u_k)$ dan $l_2=(v_1,v_2,\ldots,v_k)$, untuk suatu bilangan bulat $u_1,u_2,\ldots,u_k,v_1,v_2,\ldots,v_k$.

Kita tahu bahwa jumlah dua bilangan ganjil adalah genap dan jumlah dua bilangan genap adalah genap. Karena $l_1$ dan $l_2$ memiliki komposisi sama, maka untuk $i=1,2,\ldots,k$ berlaku $u_i+v_i$ adalah bilangan genap. Kita misalkan $u_i+v_i=2w_i$, untuk suatu bilangan bulat $w_i$.

Titik tengah dari $l_1$ dan $l_2$ adalah$$\begin{aligned}\left( \frac{u_1+v_1}{2},\frac{u_2+v_2}{2}, \ldots, \frac{u_k+v_k}{2} \right) &= \left( \frac{2w_1}{2},\frac{2w_2}{2}, \ldots, \frac{2w_k}{2} \right) \\&= \left( w_1,w_2,\ldots,w_k \right)\end{aligned}$$Karena $w_1,w_2,\ldots,w_k$ adalah bilangan bulat, maka titik tengah dari $l_1$ dan $l_2$ adalah titik lattice. Terbukti.

Tahun 2015

Suatu graf $\Lambda$ disebut komplemen dari graf $\Gamma$ jika $V(\Lambda)=V(\Gamma)$ dan sisi $e=(u,v) \in E(\Lambda)$ jika dan hanya jika sisi $e=(u,v) \notin E(\Gamma)$. Komplemen dari graf $\Gamma$ ditulis $\overline{\Gamma}$. Tentukan bilangan positif terkecil $N$ sedemikian sehingga untuk sebarang graf $\Gamma$ dengan $N$ titik senantiasa memuat graf lengkap $K_3$ sebagai subgraf atau graf $\overline{\Gamma}$ memuat graf lengkap $K_3$ sebagai subgraf. Kemudian, buktikan.

Dalam solusi ini, kita memanfaatkan salah satu akibat dari Prinsip Sangkar Burung yang Diperumum.

Kita klaim bahwa bilangan positif terkecil $N$ yang memenuhi adalah 6.

Misalkan $\Gamma$ adalah sebarang graf dengan $6$ titik, dan $w$ adalah salah satu titik pada $\Gamma$. Lima titik lain dapat bertetangga atau tidak dengan $u$. Misalkan $A$ himpunan titik pada $\Gamma$ yang bertetangga dengan $w$ dan $B$ himpunan titik yang tidak bertetangga dengan $w$.

Kita akan mendistribusikan lima titik ke dalam dua himpunan. Perhatikan bahwa $5=2(3-1)+1$. Berdasarkan akibat 1, terdapat sedikitnya satu himpunan yang memuat tiga atau lebih titik. Artinya, salah satu dari kemungkinan berikut terjadi.

1. Sedikitnya tiga titik bertetangga dengan $w$
2. Sedikitnya tiga titik tidak bertetangga dengan $w$

Tanpa mengurangi perumuman, kita asumsikan bahwa kasus pertama terjadi. Bukti untuk kasus kedua identik dengan kasus pertama. Misalkan tiga titik yang bertetangga dengan $w$ adalah $x,y,z$. Jika di antara $x,y,z$ terdapat dua titik yang bertetangga, misalnya $x$ dan $y$, maka titik $w$, $x$, dan $y$ membentuk graf lengkap $K_3$. Dengan demikian, $\Gamma$ memuat graf lengkap $K_3$ sebagai subgraf.

Namun, bagaimana jika di antara $x,y,z$ tidak ada yang bertetangga? Jika tidak ada, maka $(x,y),(x,z),(y,z) \notin E(\Gamma)$. Akibatnya $(x,y),(x,z),(y,z) \in E(\overline{\Gamma})$. Titik $x,y,z$ dan ketiga sisi ini membentuk subgraf dari $\overline{\Gamma}$, yang merupakan graf lengkap $K_3$. Terbukti.

Tahun 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.

Berikut adalah proposisi yang akan kita gunakan.

Berdasarkan Proposisi 7, setiap bilangan bulat kongruen modulo 10 dengan tepat satu dari $\{0,1,2,\ldots,9\}$. Karenanya, kita dapat melakukan partisi pada $\mathbb{Z}$ menjadi $A_0,A_1,\ldots,A_5$ dengan$$A_i = \{ x \in \mathbb{Z} \mid x \equiv i \pmod{10} \text{ atau } x \equiv (10-i) \pmod{10} \}, \; \text{ untuk } i=0,1,\ldots,5$$

Secara sederhana, kita mengelompokkan bilangan bulat dengan satuan 0 ke $A_0$, satuan 1 dan 9 ke $A_1$, satuan 2 dan 8 ke $A_2$, satuan 3 dan 7 ke $A_3$, satuan 4 dan 6 ke $A_4$, serta satuan 5 ke $A_5$.

Kita telah membentuk 6 himpunan. Berdasarkan Prinsip Sangkar Burung, jika diberikan 7 bilangan bulat berbeda, maka terdapat dua bilangan yang berasal dari himpunan yang sama, sebut saja $A_k$ untuk suatu $k=0,1,\ldots,5$. Misalkan $x$ dan $y$ adalah dua anggota yang dimaksud. Perhatikan bahwa$$\begin{aligned}&x \in A_k \quad \Longrightarrow \quad x \equiv k \pmod{10} \text{ atau } x \equiv (10-k) \pmod{10} \\&y \in A_k \quad \Longrightarrow \quad y \equiv k \pmod{10} \text{ atau } y \equiv (10-k) \pmod{10}\end{aligned}$$

Jika $x \equiv k \pmod{10}$ dan $y \equiv k \pmod{10}$, maka berdasarkan Proposisi 8b diperoleh $x-y \equiv 0 \pmod{10}$, sehingga $10 \mid x-y$. Artinya, $x-y$ adalah kelipatan 10. Hal yang sama terjadi jika $x \equiv (10-k) \pmod{10}$ dan $y \equiv (10-k) \pmod{10}$.

Jika $x \equiv k \pmod{10}$ dan $y \equiv (10-k) \pmod{10}$, maka berdasarkan Proposisi 8a diperoleh $x+y \equiv 10 \pmod{10}$ yang ekuivalen dengan $x+y \equiv 0 \pmod{10}$. Akibatnya, $10 \mid x+y$ yang berarti $x+y$ kelipatan 10. Hal yang sama terjadi jika $x \equiv (10-k) \pmod{10}$ dan $y \equiv k \pmod{10}$. Dengan demikian, $x+y$ atau $x-y$ adalah kelipatan 10. Terbukti.

Tahun 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 periode waktu tersebut.

Misalkan $a_n$ menyatakan banyaknya latih tanding pada minggu ke-n. Kita definisikan $b_n$ sebagai banyaknya latih tanding yang dilakukan hingga minggu ke-$n$, artinya $b_n=a_1+a_2+\ldots+a_n$. Dalam satu minggu, terdapat sedikitnya satu latih tanding, namun dalam periode 75 minggu tidak boleh lebih dari 125 latih tanding, sehingga$$1 \leq b_1 < b_2 < \ldots < b_{75} \leq 125 \quad \ldots (1)$$Tambahkan 24 pada setiap ruas, sehingga diperoleh$$25 \leq b_1+24 < b_2+24 < \ldots < b_{75}+24 \leq 149$$

Perhatikan barisan$$b_1,b_2,\ldots,b_{75},b_1+24,b_2+24,\ldots,b_{75}+24$$yang terdiri dari 150 bilangan. Ada 149 nilai yang mungkin untuk bilangan-bilangan ini, yaitu $1,2,\ldots,149$. Berdasarkan Prinsip Sangkar Burung, terdapat dua bilangan yang bernilai sama. Namun, berdasarkan $(1)$ tidak ada bilangan yang sama di antara $b_1,b_2,\ldots,b_{75}$. Begitupun dengan $b_1+24,b_2+24,\ldots,b_{75}+24$. Dengan demikian, terdapat suatu $i,j \in \{1,2,\ldots,75\}$ sedemikian sehingga $b_i=b_j+24$. Artinya $b_i>b_j$, yang berakibat $i>j$. Perhatikan bahwa$$\begin{aligned}b_j+24 &= b_i \\24 &= b_i-b_j \\&= a_1+a_2+\ldots+a_j+a_{j+1}+\ldots+a_i)-(a_1+a_2+\ldots+a_j) \\&= a_{j+1}+\ldots+a_i\end{aligned}$$

Dengan demikian, terdapat tepat 24 latih tanding pada minggu ke-$j+1$ sampai dengan minggu ke-$i$. Terbukti.

Tahun 2018

Andaikan $G$ adalah sebuah graf sederhana (simple graph). Bila $e$ adalah sebuah sisi yang menghubungkan titik $u$ dan $v$ di $G$, maka dikatakan bahwa titik $u$ bertetangga dengan titik $v$. Derajat dari sebuah titik $v$ di $G$ adalah banyaknya titik-titik yang bertetangga dengan $v$. Perlihatkan bahwa pada sebuah graf sederhana $G$ terdapat sedikitnya dua titik dengan derajat sama.

Misalkan $G$ adalah graf sederhana dengan $n$ titik dan $x$ adalah sebarang titik pada $G$. Terdapat $n-1$ titik yang dapat bertetangga dengan $x$. Akibatnya, derajat yang mungkin dari $x$ adalah anggota dari $$\{ 0,1,2,\ldots,n-1 \}$$

Perhatikan bahwa graf $G$ tidak mungkin memuat dua titik dengan derajat 0 dan $n-1$ secara bersamaan. Artinya, jika $G$ mempunyai sebuah titik dengan derajat 0 maka pasti tidak ada titik lain dengan derajat $n-1$. Begitupun sebaliknya. Hal ini dapat dibuktikan dengan kontradiksi. Andaikan $G$ memuat titik $a$ dan $b$, yang secara berturut-turut berderajat 0 dan $n-1$. Titik $b$ memiliki derajat $n-1$, artinya titik $b$ bertetangga dengan semua titik lain pada $G$, termasuk $a$. Akibatnya, derajat dari titik $a$ minimal 1. Terjadi kontradiksi.

Dengan demikian, derajat yang mungkin dari titik-titik pada $G$ adalah anggota dari$$\{0,1,\ldots,n-2\} \text{ atau } \{1,2,\ldots,n-1\}$$Keduanya merupakan himpunan dengan $n-1$ anggota. Karena $G$ terdiri dari $n$ titik, maka berdasarkan Prinsip Sangkar Burung, terdapat sedikitnya dua titik yang memiliki derajat sama. Terbukti.

Tahun 2019

Misalkan $n$ merupakan bilangan bulat positif yang tidak habis dibagi oleh 2 dan 5. Perlihatkan bahwa terdapat bilangan bulat $q$ yang merupakan kelipatan dari $n$ sedemikian sehingga semua digit dari $q$ adalah 1. (Contoh: Bila $n=3$, maka $q=111$ adalah kelipatan dari 3 yang semua digitnya adalah 1).

Berikut adalah proposisi yang kita gunakan.

Misalkan $n$ adalah bilangan bulat positif yang tidak habis dibagi oleh 2 dan 5. Artinya $n$ tidak habis dibagi oleh 10. Dengan kata lain, $\text{FPB}(n,10)=1$ atau $n$ relatif prima dengan 10.

Kita misalkan pula $R(k)$ sebagai bilangan bulat dengan $k$ digit, yang seluruh digitnya adalah 1. Perhatikan$$R(1),R(2),\ldots,R(n+1)$$yang terdiri dari $n+1$ bilangan. Berdasarkan Algoritma Pembagian, setiap bilangan ini dapat ditulis secara tunggal sebagai $qn+r$, untuk suatu bilangan bulat $q$ dan $r$, dengan $0 \leq r \leq n-1$.

Terdapat $n+1$ bilangan dan $n$ nilai $r$ yang mungkin. Berdasarkan Prinsip Sangkar Burung, terdapat dua bilangan dengan nilai $r$ sama. Misalkan kedua bilangan itu $R(a)$ dan $R(b)$, untuk suatu $a,b \in \{1,2,\ldots,n+1\}$. Tanpa mengurangi perumuman, kita misalkan $a>b$.

Tulis $R(a)=q_1n+r$ dan $R(b)=q_2n+r$, untuk suatu bilangan bulat $q_1$ dan $q_2$. Dengan mengurangkan kedua persamaan, diperoleh $R(a)-R(b)=(q_1-q_2)n$. Akibatnya $n \mid R(a)-R(b)$.

Perhatikan bahwa $R(a)-R(b)$ dapat ditulis sebagai $R(a-b) \cdot 10^b$, sehingga $n \mid R(a-b) \cdot 10^b$. Pada awal pembahasan, kita peroleh $\text{FPB}(n,10)=1$ yang berakibat $\text{FPB}(n,10^b)=1$. Berdasarkan Proposisi 9, diperoleh $n \mid R(a-b)$. Dengan demikian, $R(a-b)$ merupakan kelipatan dari $n$ yang seluruh digitnya adalah 1. Terbukti.