Prinsip Sarang Merpati – Materi, Soal, dan Pembahasan

Prinsip sarang merpati

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 satu ekor burung saja?” Tentu saja, ini tidak mungkin terjadi. Lalu, ia bertanya lagi, “Berapa banyak 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 banyaknya burung dalam kandang akan maksimum, yaitu $10$ ekor. Nah, bagaimana caranya supaya banyaknya 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)

Salah satu jenis permainan tradisional: Congklak
Salah satu jenis permainan tradisional: Congklak

Persoalan tersebut sebenarnya cukup sederhana. Seperti bermain congklak, kita masukkan satu ekor burung ke dalam tiap kandang sehingga bakal tersisa satu ekor burung di luar.

Sekarang, mau tidak mau, kita harus memasukkan burung ini ke dalam satu dari sembilan kandang yang ada. Dengan demikian, banyaknya 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 dengan $n \in \mathbb{N},$ maka paling sedikit terdapat satu wadah yang berisi $2$ atau lebih objek.

Bukti

Hipotesis:
Sebanyak $(n+1)$ atau lebih objek ditempatkan dalam $n$ buah wadah dengan $n \in \mathbb{N}.$
Konklusi:

Paling sedikit terdapat satu wadah yang berisi $2$ atau lebih objek.


Kita akan membuktikan teorema tersebut dengan menggunakan metode kontradiksi. Andaikan tidak ada kotak yang memuat lebih dari $1$ objek. Karena terdapat $k$ kotak, objek paling banyak adalah $k$ (terjadi ketika setiap kotak berisi $1$ objek). Namun, hal ini kontradiktif dengan pernyataan bahwa kita memiliki paling sedikit $(k+1)$ objek. Jadi, pengandaian diingkari sehingga teorema terbukti benar.

[collapse]

Catatan sejarah menunjukkan bahwa prinsip sarang merpati muncul pertama kali pada tahun $1624$ dalam sebuah buku yang dikaitkan dengan Jean Leurechon (15911670), 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 (18051859), matematikawan berkebangsaan Jerman. Meskipun demikian, matematikawan tetap sepakat bahwa penemu prinsip sarang merpati adalah Jean Leurechon

Selanjutnya, teorema ini banyak diaplikasikan dalam ranah yang lain yang 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. Beberapa contoh kasus penerapan PSM adalah sebagai berikut.

  1. Jika suatu tim kesebelasan sepak bola (terdiri dari $11$ pemain) mencetak $12$ gol dalam satu kali pertandingan, maka paling sedikit ada seorang pemain yang mencetak gol sebanyak dua kali. Dalam kasus ini, pemain dianalogikan sebagai kotak, sedangkan gol dianalogikan sebagai merpati.
  2. Jika Anda mengambil $6$ mata kuliah yang berlangsung pada hari Senin sampai Jumat, maka paling sedikit ada satu hari yang memuat dua mata kuliah untuk dihadiri. Dalam kasus ini, hari dianalogikan sebagai kotak, sedangkan mata kuliah dianalogikan sebagai merpati.
  3. Dalam suatu kelompok yang beranggotakan $367$ orang, paling sedikit ada dua orang yang memiliki tanggal dan bulan lahir yang sama. Dalam kasus ini, hari dalam setahun dianalogikan sebagai kotak, sedangkan orang dianalogikan sebagai merpati.

Soal-soal terkait prinsip sarang merpati dapat diunduh dalam bentuk dokumen PDF. Untuk mengaksesnya, Anda dapat melakukan pendaftaran akses soal premium dari situs web mathcyber1997.com melalui tautan bit.ly/Akses_Soal. Akses ini diberikan untuk satu email dan berlaku selamanya (tidak dibatasi waktu).

Today Quote

Success is the sum of small efforts, repeated day in and day out.

Bagian Pilihan Ganda

Soal Nomor 1

Banyaknya 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

Banyaknya zodiak yang kita kenal ada $12$. Jika kita pilih $12$ siswa, ada kemungkinan zodiak mereka berbeda semua, tetapi jika 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

Banyaknya 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, banyaknya 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

Banyaknya 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, banyaknya siswa paling sedikit 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, $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 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 anak 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,$ 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, atau Minggu). Paling sedikit berapa orang yang memiliki hari lahir yang sama?
A. $124$                       D. $144$           
B. $142$                       E. $184$
C. $143$

Pembahasan

Hari dalam kalender ada $7$. Karena $\dfrac{1.000}{7} = 142$ dengan sisa $6$, 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 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 $22,$ kita hanya perlu menganggap $22$ 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 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).$ Andaikan kita dalam kondisi paling tidak beruntung. Ambil bilangan $1$ sampai $14.$ Dari $14$ bilangan tersebut, belum ada pasangan dua bilangan yang jumlahnya $28.$ Lebih lanjut, jika diambil satu bilangan lagi di antara pilihan bilangan $15$ sampai $20,$ pasti akan ada pasangan dua bilangan yang jumlahnya $28.$ Sebagai ilustrasi, jika bilangan $16$ diambil, didapat $(12, 16)$ sebagai pasangan dua bilangan yang jumlahnya $28.$ Dengan menggunakan prinsip sarang merpati, banyaknya bilangan yang perlu diambil supaya dipastikan terdapat pasangan dua bilangan yang memiliki jumlah $28$ adalah $\boxed{14+1=15}$
(Jawaban D)

[collapse]

Baca Juga: Masalah Kombinatorika: Mencari Banyak Rute

Soal Nomor 10

Dari bilangan bulat $10, 11, 12, \cdots, 70$, paling sedikit berapa 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 = \color{blue}{50}$ bilangan). Selanjutnya, kita ambil bilangan $10$ sampai $15$ (ada $\color{red}{6}$ bilangan, 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{\color{blue}{50}+\color{red}{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. $71$               E. $63$
B. $80$                 D. $70$

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, paling sedikit banyaknya bilangan yang harus dipilih adalah $\boxed{70+1=71}.$
(Jawaban C)

[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, sedangkan kartu nomor $9, 10, 11, \cdots, 20$ (ada 12 nomor) masing-masing diambil sebanyak $9$ kartu. 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 13

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 sumpit setidaknya yang perlu Anda ambil?
A. $8$                    C. $59$                 E. $63$
B. $58$                  D. $62$

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 cokelat. Kemudian, kita ambil lagi $1$ sumpit dan anggap kita peroleh $1$ sumpit cokelat. Terakhir, ambil $6$ sumpit lagi dan anggap kita peroleh $6$ sumpit kuning.
Catatan: Kasus boleh dibalik. Anggap mendapat $1$ sumpit kuning, kemudian mendapat $6$ sumpit cokelat.
Jadi, kita sudah peroleh 3 pasang sumpit yang bukan putih.

Jadi, paling sedikit perlu diambil $\boxed{52+1+6 = 59}$ sumpit.
(Jawaban C)

[collapse]

Soal Nomor 14

Sejumlah siswa mengikuti ujian dengan komposisi soal sebagai berikut.

  1. Bagian pertama terdiri dari $3$ soal dengan dua pilihan (Benar/Salah).
  2. Bagian kedua terdiri dari $5$ soal dengan lima pilihan (A, B, C, D, E).

Banyaknya siswa minimal agar senantiasa terdapat dua siswa dengan jawaban yang sama persis baik pada bagian pertama maupun kedua adalah $\cdots$ orang.
A. $3.126$                      D. $25.000$
B. $12.501$                    E. $25.001$
C. $24.999$

Pembahasan

Pertama, kita cari dahulu banyaknya kemungkinan jawaban berbeda yang dapat dijawab oleh siswa.

  1. Ada $3$ soal dengan $2$ pilihan jawaban sehingga banyaknya kemungkinan jawaban berbeda untuk bagian pertama adalah $2^3 = 8.$
  2. Ada $5$ soal dengan $5$ pilihan jawaban sehingga banyaknya kemungkinan jawaban berbeda untuk bagian kedua adalah $5^5 = 3.125.$

Dengan demikian, ada $8 \cdot 3.125 = 25.000$ jawaban berbeda yang mungkin. Jika ada $25.000$ siswa, maka masih ada kemungkinan bahwa tidak ada dua siswa yang jawabannya sama persis. Menurut prinsip sarang merpati, perlu ditambah satu siswa lagi agar dipastikan terdapat dua siswa yang jawabannya sama persis. Jadi, banyaknya siswa minimal adalah $\boxed{25.001~\text{orang}}.$
(Jawaban E)

[collapse]

Soal Nomor 15

Meja bundar akan diduduki melingkar oleh sejumlah anak. Anak tersebut terdiri dari laki-laki dan perempuan dengan total sebanyak $48$ orang yang akan duduk melingkar secara acak. Banyaknya anak perempuan paling sedikit sehingga pasti ada enam anak perempuan yang duduk berdekatan tanpa diselingi anak laki-laki adalah $\cdots$ orang.
A. $7$                    C. $41$              E. $43$
B. $21$                  D. $42$

Pembahasan

Susun dua kelompok yang terdiri dari 5 anak perempuan dan 1 anak laki-laki untuk ditempatkan pada posisi duduknya di meja melingkar tersebut. Buat kelompok sehingga semua anak tercakup secara keseluruhan sehingga nantinya akan ada 8 kelompok yang terdiri dari 5 anak perempuan dan 8 anak kelompok yang terdiri 5 anak laki-laki (jumlahnya tepat 48 anak). Posisi duduk mereka akan seperti gambar.
Posisi duduk mereka memang dibuat selang-seling per kelompok agar tidak ada 6 anak perempuan yang duduk berdekatan. Dengan menggunakan prinsip sarang merpati, tambahkan $1$ anak perempuan lagi sehingga akan ditemukan secara pasti $6$ anak perempuan yang duduk berdekatan. Jadi, banyak minimum anak perempuan adalah $8 \cdot 5 + 1 = 41$ anak, sisanya adalah anak laki-laki.
(Jawaban C)

[collapse]

Soal Nomor 16

Dari bilangan $1$ sampai $100$, paling sedikit berapa bilangan yang perlu diambil supaya dipastikan terdapat pasangan dua bilangan yang hasil kalinya $100$?
A. $85$                  C. $92$               E. $97$
B. $88$                  D. $96$

Pembahasan

Andaikan kita dalam kondisi paling tidak beruntung. Pertama, ambil terlebih dahulu bilangan-bilangan yang bukan faktor positif dari $100.$ Karena faktor dari $100$ adalah $1, 2, 4, 5,$ $10, 20,$ $25, 50,$ dan $100$ (ada $9$), ambil bilangan selain ini, yaitu sebanyak $100-9 = 91$ bilangan. Berikutnya, ambil bilangan $10$ karena $10$ tidak memiliki pasangan agar hasil kalinya $100.$ Sampai sejauh ini, sudah $92$ bilangan yang telah diambil. Terakhir, ambil bilangan $1, 2, 4,$ dan $5$ sehingga total bilangan yang terambil sekarang menjadi $92+4=96.$ Jika satu bilangan apa pun diambil lagi, dapat dijamin bahwa kita akan menemukan pasangan bilangan yang hasil kalinya $100.$ Oleh karena itu, paling sedikit bilangan yang perlu diambil supaya dipastikan terdapat pasangan dua bilangan yang hasil kalinya $100$ adalah $\boxed{96+1=97}.$
(Jawaban E)

[collapse]

Bagian Uraian

Soal Nomor 1

Di dalam kotak terdapat $8$ bola merah, $6$ bola putih, dan $5$ bola hitam. Tentukan banyaknya bola paling sedikit yang harus diambil agar dipastikan diperoleh:

  1. $1$ bola merah;
  2. $1$ bola putih;  
  3. $2$ bola hitam;
  4. $3$ bola merah dan $2$ bola hitam;
  5. 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 sebanyak mungkin 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 kaus kaki berbeda warna, yaitu $5$ pasang kaus kaki warna ungu, $6$ pasang warna kuning, $4$ pasang warna merah, dan $3$ pasang warna hitam. Dalam keadaan gelap dan asumsi bahwa kaus kaki kiri dan kanan disamakan, tentukan paling sedikit kaus kaki yang harus diambil agar seseorang pasti mendapatkan:

  1. $1$ pasang kaus kaki warna ungu;
  2. $1$ pasang kaus kaki warna hitam;
  3. $3$ pasang kaus kaki warna merah;
  4. kaus kaki dengan $4$ warna berbeda.

Pembahasan

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

[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 PSM, ambil $50+1 =51$ bilangan dan dipastikan terdapat $2$ bilangan yang selisihnya $50.$ $\blacksquare$

[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 $11.$
Untuk kasus ini, nilai $n = 9.$

  1. Dari bilangan $1$ sampai $22$, diambil bilangan $1, 2, \cdots, 11.$
  2. Dari bilangan $23$ sampai $44$, diambil bilangan $23, 24, \cdots, 33.$
  3. Dari bilangan $45$ sampai $66$, diambil bilangan $45, 46, \cdots, 55.$
  4. Dari bilangan $67$ sampai $88$, diambil bilangan $67, 68, \cdots, 77.$
  5. 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.$  

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

  1. Dari bilangan $1$ sampai $18$, diambil bilangan $1, 2, \cdots, 9.$
  2. Dari bilangan $19$ sampai $36$, diambil bilangan $19, 20, \cdots, 27.$
  3. Dari bilangan $37$ sampai $54$, diambil bilangan $37, 39, \cdots, 45.$
  4. Dari bilangan $55$ sampai $72$, diambil bilangan $55, 56, \cdots, 63.$
  5. 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 yang selisihnya $9$ bila kita mengambil $55$ bilangan secara acak. $\blacksquare$

[collapse]

Soal Nomor 6

Misalkan terdapat laci yang berisi selusin kaus kaki cokelat dan selusin kaus kaki hitam yang didistribusikan secara acak. Pada saat listrik padam (Anda dianggap tidak dapat melihat sekitar), berapa kaus kaki yang harus Anda ambil untuk memastikan bahwa di antaranya terdapat sepasang kaus kaki yang sewarna?
Catatan: kaus kaki kanan dan kiri dianggap sama.

Pembahasan

Untuk mendapatkan sepasang kaus kaki sewarna, berarti kita harus mengambil setidaknya $2$ kaus kaki, tetapi belum dapat dipastikan kita mendapatkannya.
Berdasarkan prinsip sarang merpati, untuk memastikan diperolehnya sepasang kaus kaki sewarna, kita hanya perlu mengambil paling sedikit $2 + 1 = 3$ kaus 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 delapan 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 delapan bilangan bulat itu ke dalam “kotak” sesuai dengan sisa hasil baginya oleh $12$. Karena terdapat $7$ buah kotak dan $8$ bilangan, menurut prinsip sarang merpati, terdapat setidaknya satu kotak yang memuat dua bilangan. Jika kotak itu adalah kotak berlabel $\{0\}$ atau $\{6\}$, maka selisih dua bilangan tersebut adalah kelipatan $12$, contohnya bilangan $6$ dan $18$ 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.$ $\blacksquare$ 

[collapse]

Soal Nomor 8

Tunjukkan bahwa untuk setiap bilangan bulat positif $n$, terdapat bilangan kelipatan $n$ yang digit-digitnya hanya tersusun dari angka $0$ dan $1.$

Pembahasan

Ambil sembarang bilangan bulat positif $n.$ Akan ditunjukkan bahwa terdapat bilangan kelipatan $n$ yang digit-digitnya hanya tersusun dari angka $0$ dan $1.$
Misalkan kita memiliki $(n+1)$ bilangan bulat positif, yaitu $1, 11, 111, \cdots, \underbrace{111…111}_{\text{ada}~n+1}.$ Perhatikan bahwa ketika suatu bilangan bulat dibagi oleh $n,$ akan ada $n$ sisa hasil bagi yang mungkin, yaitu $0, 1, 2, 3, \cdots, n-1.$ Karena kita mempunyai $(n+1)$ bilangan, menurut PSM, ada setidaknya $2$ bilangan yang memiliki sisa hasil bagi yang sama ketika dibagi $n,$ katakanlah $A$ dan $B$ dengan $A > B.$ Bilangan $A-B$ merupakan kelipatan $n$ yang digit-digitnya hanya tersusun dari angka $0$ dan $1.$ $\blacksquare$


Ilustrasi: Misalkan kita ingin mengecek apakah bilangan kelipatan $6$ memiliki digit-digit yang hanya tersusun dari angka $0$ dan $1.$ Konstruksi $7$ bilangan, yaitu $1, 11, 111,$ $1.111, 11.111,$ $111.111,$ dan $1.111.111.$ Sisa hasil bagi tujuh bilangan ini ketika dibagi $6$ secara berturut-turut adalah $1, 5, 3, 1, 5, 3,$ dan $5.$ Kita cukup memilih dua bilangan yang memiliki sisa hasil bagi yang sama, misalkan $1$ dan $1.111.$ Perhatikan bahwa selisihnya, $1.111-1 = 1.110$ merupakan bilangan kelipatan $6$ yang hanya tersusun dari angka $0$ dan $1.$ 

[collapse]

Soal Nomor 9

Buktikan bahwa dari $(n+1)$ bilangan berbeda pada himpunan $\{1, 2, 3, \cdots, 2n\}$, selalu ada satu bilangan yang membagi satu bilangan lainnya.

Pembahasan

Setiap bilangan bulat $n \ge 1$ dapat dinyatakan dalam bentuk $n = 2^a \cdot b$ dengan $b$ adalah faktor ganjil terbesar. Dari $2n$ bilangan yang ada pada himpunan, kita punya $n$ bilangan ganjil berbeda. Dengan menggunakan prinsip sarang merpati, jika kita memilih $(n+1)$ bilangan berbeda pada himpunan tersebut, paling sedikit dua di antara bilangan itu pasti memiliki faktor ganjil terbesar yang sama. Misalkan dua bilangan itu adalah $n_1 = 2^x \cdot b$ dan $n_2 = 2^y \cdot b$ sehingga jelas bahwa $n_1 \mid n_2$ jika $n_2 \ge n_1$ atau $n_2 \mid n_1$ jika $n_1 \ge n_2.$ $\blacksquare$

[collapse]

Soal Nomor 10

Tunjukkan bahwa di antara $n+1$ bilangan bulat positif yang nilainya tidak melebihi $2n$, selalu ada bilangan bulat yang membagi salah satu bilangan bulat yang lain.
Ilustrasi: Misalkan diambil $n = 7.$ Sebanyak $8$ bilangan bulat positif yang kita punya nilainya tidak boleh melebihi $14.$ Misalkan dipilih bilangan $$6, 7, 8, 9, 10, 11, 12, 13.$$Bilangan yang kita pilih tidak harus berbeda. Perhatikan bahwa kita menemukan bilangan bulat yang membagi bilangan bulat lainnya, yaitu $6 \mid 12.$

Pembahasan

Ide yang kita gunakan adalah fakta bahwa setiap bilangan bulat positif dapat dituliskan sebagai perkalian perpangkatan $2$ dan suatu bilangan ganjil (ambil sebesar mungkin). Contoh: $30 = 2 \times 15$ dan $40 = 2^3 \times 5.$
Misalkan kita punya $n+1$ bilangan bulat positif, yaitu $a_1, a_2, \cdots, a_n, a_{n+1}.$ Nyatakan semua bilangan ini dalam bentuk $a_j = 2^{k_j} \cdot q_j$ untuk $j = 1, 2, \cdots, n+1$ dengan $k_j$ merupakan bilangan bulat nonnegatif dan $q_j$ merupakan bilangan ganjil. Bilangan bulat $q_1, q_2, \cdots, q_{n+1}$ merupakan bilangan ganjil positif yang nilainya kurang dari $2n.$ Namun, hanya ada $n$ bilangan ganjil positif berbeda yang nilainya kurang dari $2n.$ Menurut PSM, ada setidaknya dua bilangan ganjil dari $q_1, q_2, \cdots, q_{n+1}.$ Dengan kata lain, ada bilangan bulat berbeda $i$ dan $j$ sedemikian sehingga $q_i = q_j.$ Misalkan $q = q_i = q_j$ sehingga $a_i = 2^{k_i} \cdot q$ dan $a_j = 2^{k_j} \cdot q.$ Akibatnya, jika $k_i < k_j,$ maka $a_i$ membagi $a_j.$ Sebaliknya, jika $k_j < k_i,$ maka $a_j$ membagi $a_i.$
Jadi, terbukti bahwa di antara $n+1$ bilangan bulat positif yang nilainya tidak melebihi $2n$, selalu ada bilangan bulat yang membagi salah satu bilangan bulat yang lain. $\blacksquare$

[collapse]

Soal Nomor 11

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, diperoleh
$$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,\cdots, a_{75}, a_1+24,$ $a_2+24, \cdots, a_{75}+24$ terdiri dari $75+75=150$ bilangan, 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. $\blacksquare$

[collapse]