Prinsip Sarang Merpati – Materi, Soal, dan Pembahasan

Teorema yang termuat dalam materi kombinatorika ini diambil namanya dari kejadian menempatkan $10$ burung merpati ke dalam $9$ sangkar burung. Si pemilik burung bertanya, “Apakah ada kemungkinan setiap kandang berisi cukup $1$ burung saja?” Tentu saja, ini tidak mungkin terjadi. Lalu, ia bertanya lagi, “Berapa jumlah burung paling sedikit yang dapat menempati kandang-kandang tersebut?

Prinsip Sarang Merpati

Pertanyaan ini sungguh memicu berjalannya logika. Jika kita menempatkan semua burung ke dalam satu kandang, berarti jumlah burung dalam kandang akan maksimum, yaitu $10$. Nah, bagaimana caranya supaya jumlah burung di kandang itu minimum? Persoalan inilah yang melatarbelakangi terciptanya teorema yang dikenal orang dengan istilah Prinsip Sarang Merpati, disingkat PSM (Pigeonhole Principle atau juga sering disingkat PHP), kadang juga disebut Prinsip Sarang Burung

Baca Juga: Soal dan Pembahasan – Peluang dan Kombinatorika (Tingkat SMA)

Persoalan tersebut sebenarnya cukup sederhana. Seperti bermain congklak, kita masukkan $1$ burung ke dalam tiap kandang, sehingga bakal tersisa $1$ burung di luar.
Sekarang, mau tidak mau, kita harus memasukkan burung ini ke dalam satu dari sembilan kandang yang ada. Dengan demikian, jumlah burung paling sedikit dalam kandang adalah $2$ ekor. Dengan memperhatikan kasus ini, kita harus menempatkan diri dalam kondisi terburuk untuk menyelesaikan persoalan terkait PSM.

Teorema: Prinsip Sarang Merpati

Jika $(n+1)$ atau lebih objek ditempatkan dalam $n$ buah wadah untuk $n$ bilangan asli, maka paling sedikit terdapat satu wadah yang berisi $2$ atau lebih objek.

      Catatan sejarah menunjukkan bahwa prinsip sarang merpati muncul pertama kali pada tahun $1624$ dalam sebuah buku yang dikaitkan dengan Jean Leurechon (1591 – 1670), seorang pendeta dan matematikawan berkebangsaan Prancis. Namun sekarang teorema tersebut lebih umum dikenal sebagai Prinsip Laci Dirichlet (Dirichlet’s Drawer Principle atau Dirichlet’s Box Principle) setelah eksperimen teorema dilakukan oleh Peter Gustav Lejeune Dirichlet (1805 – 1859), matematikawan berkebangsaan Jerman. Meskipun demikian, dunia tetap sepakat bahwa penemu prinsip sarang merpati adalah Jean Leurechon

      Selanjutnya, teorema ini banyak diaplikasikan dalam ranah yang lain, tentu saja tidak hanya masalah menempatkan burung seperti kasus pertama. Teorema ini juga bermanfaat dalam bidang komputer karena dapat menghasilkan pengkodean atau program yang lebih mangkus dan sangkil (efektif dan efisien).

Bagian Pilihan Ganda

Soal Nomor 1
Jumlah siswa minimal dalam satu kelas agar didapat $2$ siswa dengan zodiak yang sama adalah $\cdots \cdot$
A. $2$                    C. $12$                  E. $24$
B. $3$                    D. $13$

Pembahasan

Jumlah zodiak yang kita kenal ada $12$. Jika kita pilih $12$ siswa, ada kemungkinan zodiak mereka berbeda semua, namun bila kita pilih $\boxed{12+1=13}$ siswa, dipastikan setidaknya ada $2$ siswa dengan zodiak yang sama.
(Jawaban D)

[collapse]

Baca Juga: Soal dan Pembahasan – Kombinatorika (Tingkat Lanjut)

Soal Nomor 2
Jumlah orang minimal yang harus ada agar dipastikan terdapat $4$ orang dengan tanggal kelahiran yang sama adalah $\cdots \cdot$
A. $31$                   C. $94$                  E. $125$
B. $63$                   D. $120$

Pembahasan

Tanggal lahir dimulai dari $1$ dan berakhir paling lama sampai tanggal $31$. Jika kita pilih $3 \times 31 = 93$ orang, ada kemungkinan masing-masing $3$ orang memiliki tanggal lahir yang sama, namun bila ditambah $1$ orang lagi, sudah dipastikan akan ada $4$ orang yang memiliki tanggal lahir yang sama.
Jadi, jumlah orang yang dimaksud adalah $\boxed{94}$ orang.
(Jawaban C)

[collapse]

Soal Nomor 3
Banyaknya siswa paling sedikit yang perlu dipilih supaya pasti diperoleh setidaknya $4$ siswa dengan bulan kelahiran yang sama adalah $\cdots \cdot$
A. $13$                    C. $25$                 E. $49$
B. $18$                    D. $37$

Pembahasan

Banyak kemungkinan bulan ada $12$. Jika diratakan terdapat masing-masing $3$ siswa yang memiliki bulan lahir yang sama, maka akan ada $36$ siswa. Berdasarkan Prinsip Sarang Merpati, tambahkan seorang siswa lagi sehingga dipastikan akan ada $4$ siswa yang mempunyai bulan lahir yang sama.
Jadi, minimal banyak siswanya adalah $\boxed{37}$ orang.
(Jawaban D)

[collapse]

Soal Nomor 4
Di dalam kelas terdapat $38$ siswa. Paling sedikit berapa siswa yang memiliki tanggal lahir yang sama di kelas tersebut?
A. $1$                     C. $3$                 E. $12$
B. $2$                     D. $4$

Pembahasan

Tanggal lahir dimulai dari $1$ dan berakhir paling lama sampai tanggal $31$. Ada kemungkinan $31$ siswa memiliki tanggal lahir yang berbeda-beda. Karena ada $38$ siswa, maka $7$ siswa tersisa dianggap memiliki tanggal lahir yang berbeda-beda, sehingga paling sedikit ada $\boxed{2}$ siswa yang bulan lahirnya sama.
(Jawaban B)

[collapse]

Soal Nomor 5
Suatu sekolah menengah pertama (SMP) terdiri dari $111$ siswa. Paling sedikit berapa banyak siswa yang berada pada tingkat (jenjang) yang sama?
A. $30$                   C. $37$                  E. $111$
B. $35$                   D. $38$

Pembahasan

Ada $3$ jenjang pada SMP, yaitu kelas $7$, kelas $8$, dan kelas $9$. Karena $\dfrac{111}{3} = 37$ (tanpa sisa), berarti dapat dianggap ada $37$ siswa kelas 7, $37$ siswa kelas 8, dan $37$ siswa kelas $9$. Artinya, paling sedikit ada $37$ siswa yang berada pada jenjang yang sama.
(Jawaban C) 

[collapse]

Soal Nomor 6
Paling sedikit berapa banyak dari $119$ anak yang lahir pada bulan yang sama?
A. $9$                    C. $11$                  E. $15$
B. $10$                  D. $12$

Pembahasan

Bulan kelahiran dalam kalender ada $12$. Karena $\dfrac{119}{12} = 9$ dengan sisa $11$, maka akan ada paling sedikit $\boxed{9+1 = 10}$ anak yang lahir pada bulan yang sama.
(Jawaban B)

[collapse]

Baca Juga: Soal dan Pembahasan – Peluang (Tingkat SMP/Sederajat)

Soal Nomor 7
Sebanyak $1.000$ orang mengikuti survei dan mereka diminta untuk mengisi rumpang berupa hari lahir mereka (Senin, Selasa, Rabu, Kamis, Jumat, Sabtu, dan Minggu). Paling sedikit ada berapa orang yang memiliki hari lahir yang sama?
A. $124$                    C. $143$                  E. $184$
B. $142$                    D. $144$

Pembahasan

Hari dalam kalender ada $7$. Karena $\dfrac{1.000}{7} = 142$ dengan sisa $6$, maka kita hanya perlu menganggap $6$ orang ini memiliki hari lahir yang berbeda-beda. Akibatnya, paling sedikit kita temukan ada $\boxed{142+1=143}$ orang dengan hari lahir yang sama.
(Jawaban C)

[collapse]

Soal Nomor 8
Dari $100$ orang, setidaknya berapa banyak orang yang memiliki nama dengan huruf depan yang sama?
A. $3$                    C. $5$                 E. $8$
B. $4$                    D. $6$

Pembahasan

Huruf yang kita gunakan (English Alphabet) ada $26$.
Karena $\dfrac{100}{26} = 3$ dengan sisa $24$, maka kita hanya perlu menganggap $24$ orang ini memiliki nama dengan huruf depan yang berbeda-beda. Akibatnya, paling sedikit kita temukan ada $\boxed{3+1=4}$ orang yang memiliki nama dengan huruf depan yang sama.
(Jawaban B)

[collapse]

Soal Nomor 9
Dari bilangan $1$ sampai $20$, paling sedikit berapa banyak bilangan yang perlu diambil supaya dipastikan terdapat pasangan dua bilangan yang memiliki jumlah $28$?
A. $7$                     C. $13$                   E. $18$
B. $10$                   D. $15$

Pembahasan

Contoh pasangan dua bilangan yang jumlahnya $28$ adalah $(8, 20)$, $(9, 19)$, $(10, 18)$, dan seterusnya, sampai $(13, 15)$.
Kita ambil bilangan $1$ sampai $7$ terlebih dahulu. Selanjutnya, jika kita ambil bilangan $8, 9, 10, 11, 12, 13$, dan $14$, belum ada ditemukan pasangan bilangan yang berjumlah $28$. Sekarang, tersisa bilangan $15$ sampai $20$. Jika kita ambil salah satu dari bilangan ini, dipastikan terdapat dua bilangan dengan jumlah $28$. Jadi, paling sedikit banyak bilangan yang perlu diambil adalah $\boxed{14+1=15}$
(Jawaban D)

[collapse]

Soal Nomor 10
Dari bilangan bulat $10, 11, 12, \cdots, 70$, paling sedikit berapa banyak bilangan yang perlu dipilih secara acak untuk memastikan terdapat dua bilangan yang jumlahnya $30$?
A. $49$                    C. $53$                  E. $57$
B. $51$                    D. $55$

Pembahasan

Pasangan bilangan yang memiliki jumlah $30$ adalah $(10, 20)$, $(11, 19)$, $(12, 18)$, $(13, 17)$, $(14, 16)$. Bilangan $21$ dan seterusnya sampai $70$ tidak memiliki pasangan untuk membentuk jumlah $30$ sehingga kita ambil terlebih dahulu (sebanyak $70-21+1 = 50$ bilangan). Selanjutnya, kita ambil bilangan $10$ sampai $15$, dan tetap belum ditemukan pasangan berjumlah $30$. Jika kita ambil satu bilangan lagi, apapun bilangan itu, kita peroleh dua bilangan berjumlah $30$.
Jadi, bilangan yang perlu dipilih sebanyak $\boxed{50+6+1=57}$
(Jawaban E)

[collapse]

Soal Nomor 11
Diketahui $X$ adalah barisan bilangan bulat dari $1$ sampai $123$. Paling sedikit berapa bilangan yang perlu dipilih secara acak dari $X$ supaya dipastikan terdapat dua bilangan yang selisihnya $70$?
A. $122$                  C. $70$                  E. $63$
B. $80$                    D. $69$

Pembahasan

Dengan memperhatikan kondisi terburuk, kita mengambil $n$ bilangan dari $2n$ bilangan sehingga kita tidak peroleh dua bilangan yang selisihnya $70$.
Untuk kasus ini, nilai $n = 70$.
Dari bilangan $1$ sampai $123$, dipilih bilangan $1, 2, \cdots, 70$ (sebanyak $70$ bilangan). Jika kita ambil satu bilangan apapun lagi, sudah dipastikan terdapat pasangan bilangan yang berselisih $70$. Jadi, minimal banyak bilangan yang harus dipilih adalah $\boxed{70}$

[collapse]

Soal Nomor 12
Suatu kotak berisi sejumlah kartu bernomor. Ada satu kartu bernomor $1$, dua kartu bernomor $2$, tiga kartu bernomor $3$, dan seterusnya sampai dua puluh kartu bernomor $20$. Agar dapat dipastikan bahwa kartu yang kita ambil dari kotak tersebut ada $10$ kartu bernomor sama, paling tidak kita harus mengambil sebanyak $\cdots$ kartu.
A. $143$                    C. $145$                  E. $210$
B. $144$                    D. $146$

Pembahasan

Dengan menganggap kita dalam kondisi yang paling tidak beruntung, kita mendapatkan tepat $9$ kartu untuk masing-masing nomor dari $1$ sampai $20$. Khusus untuk kartu bernomor $1$ sampai $8$, kita ambil semua kartu yang ada sesuai banyaknya di kotak. Jadi, kita peroleh kartu sebanyak
$\begin{aligned} & 1+2+3+\cdots+8+\underbrace{9+9+\cdots+9}_{\text{ada}~12} \\ & = (1+8) \times 4 + 12 \times 9 = 36 + 108 = 144 \end{aligned}$
Sampai sini, kita masih belum mendapatkan $10$ kartu bernomor sama, tetapi dengan mengambil satu kartu lagi di dalam kotak, kita dipastikan mendapatkannya.
Jadi, paling sedikit kita harus mengambil $\boxed{144+1=145}$ kartu.
(Jawaban C)

[collapse]

Soal Nomor 0 (TIMO 2019 – Tingkat SMA)
Terdapat 52 sumpit putih, 66 sumpit kuning, dan 15 sumpit cokelat yang dicampur bersama. Jika dengan menutup mata, Anda ingin mendapatkan 1 pasang sumpit yang bukan cokelat dan 3 pasang sumpit yang bukan putih, maka berapa banyak sumpit setidaknya yang perlu Anda ambil?
A. $8$                      C. $48$                  E. $68$
B. $12$                    D. $58$

Pembahasan

Menurut PSM, kita harus menempatkan posisi kita dalam keadaan terburuk dalam pengambilan sumpit. Saat kita ambil acak $52$ sumpit, kita mendapatkan $52$ sumpit putih. Artinya, kita sudah mendapatkan 1 pasang sumpit bukan coklat.
Jika diambil 6 sumpit lagi sisanya, maka dipastikan kita sudah memperoleh 3 pasang sumpit bukan warna putih (karena hanya tersisa sumpit kuning dan cokelat).
Jadi, paling sedikit perlu diambil $\boxed{52+6 = 58}$ sumpit.
(Jawaban D)

[collapse]

Bagian Uraian

Soal Nomor 1
Di dalam kotak terdapat $8$ bola merah, $6$ bola putih, dan $5$ bola hitam. Tentukan jumlah bola paling sedikit yang harus diambil agar dipastikan diperoleh:
a. $1$ bola merah;
b. $1$ bola putih;
c. $2$ bola hitam;
d. $3$ bola merah dan $2$ bola hitam;
e. bola dengan tiga warna berbeda.

Pembahasan

Jawaban a)
Dalam keadaan terburuk, kita mengambil $6$ bola putih dan $5$ bola hitam, lalu diikuti dengan pengambilan sebuah bola merah. Jadi, minimal bola yang harus diambil adalah $\boxed{6+5+1=12}$
Jawaban b)
Dalam keadaan terburuk, kita mengambil $8$ bola merah dan $5$ bola hitam, lalu diikuti dengan pengambilan sebuah bola putih. Jadi, minimal bola yang harus diambil adalah $\boxed{8+5+1=14}$
Jawaban c)
Dalam keadaan terburuk, kita mengambil $8$ bola merah dan $6$ bola putih, lalu diikuti dengan pengambilan $2$ bola hitam. Jadi, minimal bola yang harus diambil adalah $\boxed{8+6+2=16}$
Jawaban d)
Dalam keadaan terburuk, kita mengambil $6$ bola putih, disusul dengan pengambilan $8$ bola merah, dan terakhir $2$ bola hitam. Jadi, minimal bola yang harus diambil adalah $\boxed{6+8+2=16}$
Jawaban e)
Dalam keadaan terburuk, kita dianggap mengambil bola yang jumlahnya paling banyak terlebih dahulu, yaitu $8$ bola merah, lalu $6$ bola putih, dan terakhir cukup $1$ bola hitam. Jadi, minimal bola yang harus diambil adalah $\boxed{8+6+1=15}$

[collapse]

Soal Nomor 2
Di dalam laci terdapat sejumlah pasang kaos kaki berbeda warna, yaitu $5$ pasang kaos kaki warna ungu, $6$ pasang warna kuning, $4$ pasang warna merah, dan $3$ pasang warna hitam. Dalam keadaan gelap dan asumsikan bahwa kaos kaki kiri dan kanan disamakan, tentukan paling sedikit kaos kaki yang harus diambil agar pasti mendapat:
a. $1$ pasang kaos kaki warna ungu;
b. $1$ pasang kaos kaki warna hitam;
c. $3$ pasang kaos kaki warna merah;
d. kaos kaki dengan $4$ warna berbeda.

Pembahasan

Jawaban a)
Dalam keadaan terburuk, kita mengambil $6$ pasang kaos kaki warna kuning, $4$ pasang warna merah, dan $3$ pasang warna hitam. Kemudian barulah diambil $1$ pasang kaos kaki warna ungu.
Jadi, paling sedikit kaos kaki yang perlu diambil adalah $\boxed{2(6)+2(4)+2(3)+2(1) = 28}$
Jawaban b)
Dalam keadaan terburuk, kita mengambil $6$ pasang kaos kaki warna kuning, $4$ pasang warna merah, dan $5$ pasang warna ungu. Kemudian barulah diambil $1$ pasang kaos kaki warna hitam.
Jadi, paling sedikit kaos kaki yang perlu diambil adalah $\boxed{2(6)+2(4)+2(5)+2(1) = 32}$
Jawaban c)
Dalam keadaan terburuk, kita mengambil $6$ pasang kaos kaki warna kuning, $5$ pasang warna ungu, dan $3$ pasang warna hitam. Kemudian barulah diambil $3$ pasang kaos kaki warna merah.
Jadi, paling sedikit kaos kaki yang perlu diambil adalah $\boxed{2(6)+2(5)+2(3)+2(3) = 34}$
Jawaban d)
Dalam keadaan terburuk, kita dianggap mengambil pasang kaos kaki yang paling banyak terlebih dahulu, yaitu $6$ pasang kaos kaki warna kuning, lalu $5$ pasang kaos kaki warna ungu, diikuti oleh $4$ pasang kaos kaki warna merah, dan terakhir cukup $1$ pasang kaos kaki warna hitam.
Jadi, paling sedikit kaos kaki yang perlu diambil adalah $\boxed{2(6)+2(5)+2(4)+2(1) = 32}$

[collapse]

Soal Nomor 3
Diberikan barisan bilangan $1, 2, 3, \cdots, 100$. Jika dari barisan bilangan tersebut diambil $51$ bilangan secara acak, buktikan bahwa setidaknya ada $2$ bilangan yang selisihnya $50$.

Pembahasan

Pasangan $2$ bilangan yang memiliki selisih $50$ adalah $(1, 51)$, $(2, 52)$, $(3, 53)$, $\cdots$, $(49, 99)$, dan $(50, 100$). Kita menemukan ada $50$ pasangan. Jika kita mengambil tepat $50$ bilangan, ada kemungkinan kita mendapatkan bilangan $1, 2, 3, \cdots, 49, 50$ sehingga tidak ada pasangan bilangan yang berselisih $50$. Berdasarkan PHP, ambil $50+1 =51$ bilangan dan dipastikan terdapat $2$ bilangan yang selisihnya $50$.

[collapse]

Soal Nomor 4
Diberikan barisan bilangan $1, 2, 3, \cdots, 100$. Jika dari barisan bilangan tersebut diambil $55$ bilangan secara acak, buktikan bahwa belum tentu ada $2$ bilangan yang selisihnya $11$.

Pembahasan

Dengan memperhatikan kondisi terburuk, kita mengambil $n$ bilangan dari $2n$ bilangan sehingga kita tidak peroleh dua bilangan yang selisihnya $9$.
Untuk kasus ini, nilai $n = 11$.
Dari bilangan $1$ sampai $22$, diambil bilangan $1, 2, \cdots, 11$.
Dari bilangan $23$ sampai $44$, diambil bilangan $23, 24, \cdots, 33$.
Dari bilangan $45$ sampai $66$, diambil bilangan $45, 46, \cdots, 55$.
Dari bilangan $67$ sampai $88$, diambil bilangan $67, 68, \cdots, 77$.
Dari bilangan $89$ sampai $100$, diambil bilangan $89, 90, \cdots, 99$.
Banyaknya bilangan yang kita ambil seluruhnya adalah $11+11+11+11+11=55$, dan tidak ditemukan adanya $2$ bilangan yang berselisih $11$ (terbukti).

[collapse]

Soal Nomor 5
Diberikan barisan bilangan $1, 2, 3, \cdots, 100$. Jika dari barisan bilangan tersebut diambil $55$ bilangan secara acak, buktikan bahwa setidaknya ada $2$ bilangan yang selisihnya $9$.

Pembahasan

Dengan memperhatikan kondisi terburuk, kita mengambil $n$ bilangan dari $2n$ bilangan sehingga kita tidak peroleh dua bilangan yang selisihnya $9$.
Untuk kasus ini, nilai $n = 9$.
Dari bilangan $1$ sampai $18$, diambil bilangan $1, 2, \cdots, 9$.
Dari bilangan $19$ sampai $36$, diambil bilangan $19, 20, \cdots, 27$.
Dari bilangan $37$ sampai $54$, diambil bilangan $38, 39, \cdots, 46$.
Dari bilangan $55$ sampai $72$, diambil bilangan $55, 56, \cdots, 63$.
Dari bilangan $73$ sampai $90$, diambil bilangan $73, 74, \cdots, 81$.
Dari bilangan $91$ sampai $100$, diambil semua bilangan yang ada, kecuali $100$.
Banyaknya bilangan yang kita ambil seluruhnya adalah $9+9+9+9+9+9 =54$. Jika kita mengambil satu bilangan tersisa secara acak (berapapun nilainya), dipastikan akan ada dua bilangan yang berselisih $9$. Jadi, terbukti bahwa setidaknya terdapat $2$ bilangan secara acak bila kita mengambil $55$ bilangan.

[collapse]

Soal Nomor 6 (Soal ON MIPA-PT Universitas Tanjungpura Tahun 2018)
Misalkan terdapat laci yang berisi selusin kaos kaki coklat dan selusin kaos kaki hitam yang didistribusikan secara acak. Pada saat listrik padam (Anda dianggap tidak dapat melihat sekitar), berapa kaos kaki yang harus Anda ambil untuk memastikan bahwa di antaranya terdapat sepasang kaos kaki yang sewarna?
Catatan: kaos kaki kanan dan kiri dianggap sama.

Pembahasan

Untuk mendapatkan sepasang kaos kaki sewarna, berarti kita harus mengambil setidaknya $2$ kaos kaki, tetapi belum dapat dipastikan kita mendapatkannya.
Berdasarkan Prinsip Sarang Merpati (Pigeonhole Principle), untuk memastikan diperolehnya sepasang kaos kaki sewarna, maka kita hanya perlu mengambil paling sedikit $2 + 1 = 3$ kaos kaki.

[collapse]

Soal Nomor 7
Diberikan $8$ bilangan bulat. Tunjukkan bahwa terdapat $2$ bilangan di antaranya yang jumlah atau selisihnya habis dibagi $12$.

Pembahasan

Jika kedelapan bilangan bulat tersebut dibagi $12$, maka kemungkinan sisanya adalah $\{0,1,2,\cdots, 12\}$. Sekarang siapkan $7$ buah “kotak” dan beri label seperti berikut.
$$\{0\}, \{1,11\}, \{2,10\}, \{3,9\}, \{4,8\}, \{5,7\}, \{6\}$$Kemudian kita masukkan kedelapan bilangan bulat itu ke dalam “kotak” sesuai dengan sisa hasil baginya oleh $12$. Karena terdapat $7$ buah kotak dan $8$ bilangan, maka menurut Prinsip Sarang Merpati, terdapat setidaknya satu kotak yang memuat dua bilangan. Jika kotak itu adalah kotak berlabel $\{0\}$ dan $\{6\}$, maka selisih dua bilangan tersebut adalah kelipatan $12$, contohnya bilangan $6$ dan $12$ yang masuk ke kotak berlabel $\{6\}$ (karena sisa hasil baginya oleh $12$ adalah $6$) memiliki selisih $12$. Di lain sisi, jika yang memuat dua bilangan itu kotak lainnya, maka hasil penjumlahan dua bilangan tersebut habis dibagi $12$, contohnya bilangan $2$ dan $22$ masuk ke dalam kotak berlabel $\{2,10\}$ memiliki jumlah $24$, yang merupakan kelipatan $12$ (Terbukti). $\blacksquare$

[collapse]

Soal Nomor 8 (Soal ON MIPA-PT Seleksi Wilayah Tahun 2015)
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 boleh lebih dari $125$ latih tanding dalam periode $75$ minggu. Perlihatkan bahwa ada periode waktu yang terdiri atas beberapa minggu berurutan sehingga terdapat tepat $24$ latih tanding.

Pembahasan

Misalkan $a_1$ adalah banyaknya latih tanding yang telah dilakukan petinju sampai hari ke-$i$ dengan $i = 1,2,3,\cdots, 75$, sehingga diperoleh
$1 \leq a_1 < a_2 < a_3 < \cdots < a_{75} \leq 125$
dan dengan menambahkan $24$ di setiap ruas, diperolehlah
$$25 \leq a_1 + 24 < a_2+24< \cdots < a_{75} + 24 \leq 149$$Karena ada 149 bilangan terhitung dari 1 sampai 149, sedangkan $a_1,a_2,a_{75},a_1+24,a_2+24, \cdots, a_{75}+24$ ada 150 bilangan, maka menurut Prinsip Sarang Merpati, setidaknya ada 2 bilangan yang sama dari barisan tersebut, yakni ada $i$ dan $j$ sedemikian sehingga $a_i = a_j +24$
Dengan kata lain, pada hari ke $j+1,j+2,\cdots, i$, si petinju tepat latih tanding sebanyak $24$ kali.

[collapse]