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. Oleh karena itu, kami tertarik untuk membuat tulisan khusus mengenai topik ini. Kami telah menulis pembahasan setiap soal secara terpisah di website MathPro.id. Jadi, kami tidak menulis ulang pembahasan tersebut di sini. Kami hanya menyediakan pranala (link) menuju pembahasan soal yang bersesuaian.

Semoga pembahasan yang kami sajikan dapat dimengerti dengan baik. Jika pembaca menemukan kekeliruan dalam pembahasan yang kami tulis, jangan sungkan untuk memberi kritik melalui komentar. Komentar tersebut boleh dituliskan pada halaman ini, dan juga boleh pada pembahasan soal yang dimaksud. Terima kasih.

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 (Uraian)

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.

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Titik Tengah Berkoordinat Bulat.

Tahun 2007 (Uraian)

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

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Dua Bilangan dengan Selisih Kelipatan 10.

Tahun 2008 (Uraian)

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

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Dua Bilangan dengan Selisih Tidak Lebih dari $m-1$.

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.

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Sebuah Bilangan Membagi Bilangan yang Lain.

Tahun 2010 (Uraian)

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

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Beberapa Suku Berurutan yang Jumlahnya Habis dibagi $m$.

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.

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Dua Peserta Seminar dengan Jumlah Kenalan Sama.

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}$.

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Bilangan Real $a$ dan $b$ dengan $0 < \frac{a-b}{ab+1} < \sqrt{3}$.

Tahun 2014 (Uraian)

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.

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Dua Titik Lattice dengan Titik Tengah Lattice.

Tahun 2015 (Uraian)

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.

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Graf $G$ atau Komplemennya Memuat Subgraf Lengkap $K_3$.

Tahun 2016 (Uraian)

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.

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Dua Bilangan dengan Jumlah atau Selisih Kelipatan 10.

Tahun 2017 (Uraian)

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.

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Periode Waktu dengan Tepat 24 Latih Tanding.

Tahun 2018 (Uraian)

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.

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Dua Titik Berderajat Sama Pada Graf Sederhana.

Tahun 2019 (Uraian)

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

Pembahasan

Pembahasan dapat dilihat pada tulisan berjudul Bilangan Bulat dengan Semua Digit 1.