Prinsip Sarang Merpati untuk Pemula Olimpiade Matematika

Banyaknya siswa minimal dalam satu kelas agar pasti terdapat dua siswa dengan zodiak yang sama dapat dianalisis menggunakan Prinsip Pigeonhole.

Terdapat \(12\) zodiak, sehingga jika setiap siswa diandaikan menempati satu jenis zodiak yang berbeda maka jumlah siswa maksimal yang dapat ditempatkan tanpa adanya pengulangan adalah \(12\). Dengan kata lain, selama jumlah siswa masih \(≤12\) masih mungkin semua siswa memiliki zodiak yang berbeda-beda.

Tujuan kita adalah menjamin terjadinya pengulangan, yaitu agar terdapat sedikitnya dua siswa yang memiliki zodiak sama. Banyaknya siswa minimal \(N\) yang harus hadir agar kondisi tersebut pasti terjadi dinyatakan sebagai nilai \(N\) terkecil dengan: \(\left\lceil \dfrac{N}{12} \right\rceil=2\)

Agar \(\left\lceil \dfrac{N}{12} \right\rceil=2\) diperlukan \(\left\lceil \dfrac{N}{12} \right\rceil>1\) sehingga nilai \(N\) harus lebih besar dari \(12\).
Maka diperoleh kesimpulan bahwa jumlah minimal siswa agar pasti ada dua orang dengan zodiak sama adalah \(N=13\).

Dengan \(N=13\) siswa dan hanya \(N=12\) jenis zodiak, pembagian tidak mungkin dilakukan semuanya tanpa pengulangan. Artinya, pasti terdapat minimal dua siswa yang memiliki zodiak yang sama.

Sehingga jawaban yang benar adalah \(13\) (opsi D).

Inline: (a+b)

Display:
[\frac{1}{2}]

Inline: $a+b$

Display:
\frac{1}{2}

Pada soal ini, yang diperhatikan hanyalah tanggal kelahiran (1 sampai 31),
jadi ada 31 kemungkinan tanggal yang berbeda.

Kita ingin memastikan ada 4 orang yang memiliki tanggal kelahiran yang sama.
Artinya, jika setiap tanggal “boleh diisi” paling banyak 3 orang,
maka belum ada yang mencapai 4 orang.

Banyak orang maksimum yang masih mungkin tanpa ada 4 orang pada tanggal yang sama adalah:
3 orang per tanggal × 31 tanggal = 3 × 31 = 93 orang.

Dengan 93 orang, masih mungkin setiap tanggal hanya berisi paling banyak 3 orang.

Begitu kita menambah 1 orang lagi, menjadi:
N = 3 × 31 + 1 = 94 orang,

maka berdasarkan Prinsip Pigeonhole, pasti ada sedikitnya satu tanggal
yang ditempati oleh 4 orang.

Jadi banyaknya orang minimal yang harus ada agar dipastikan terdapat
4 orang dengan tanggal kelahiran yang sama adalah 94.

Jawaban: C. 94

Yang diperhatikan hanya bulan kelahiran, sehingga ada 12 kemungkinan bulan yang berbeda.

Kita ingin memastikan ada sekurang-kurangnya 4 siswa yang lahir pada bulan yang sama.
Jika setiap bulan hanya ditempati oleh paling banyak 3 siswa, maka belum ada bulan
yang memiliki 4 siswa.

Jumlah siswa maksimum yang masih mungkin tanpa ada 4 siswa pada bulan yang sama adalah:
3 siswa per bulan × 12 bulan = 3 × 12 = 36 siswa.

Dengan 36 siswa, masih mungkin setiap bulan berisi paling banyak 3 siswa.
Agar pasti ada satu bulan yang berisi sedikitnya 4 siswa, kita harus menambah 1 siswa lagi:

N = 3 × 12 + 1 = 37.

Jadi banyaknya siswa paling sedikit yang perlu dipilih adalah 37.

Jawaban: D. 37

Tanggal lahir memiliki 31 kemungkinan (1–31). Jika setiap tanggal hanya ditempati
oleh 1 siswa, maka jumlah siswa maksimum yang masih mungkin semuanya berbeda
tanggal lahir adalah 31.

Namun pada soal terdapat 44 siswa. Karena 44 > 31, maka setelah 31 siswa
mengisi tanggal lahir yang berbeda, siswa ke-32 pasti memiliki tanggal lahir
yang sama dengan salah satu dari 31 siswa sebelumnya.

Maka paling sedikit ada 2 siswa yang memiliki tanggal lahir yang sama.

Jawaban: B. 2

🕊 Menggunakan Prinsip Sarang Merpati (Pigeonhole Principle)

Sebelum menyelesaikan soal, kita perlu menetapkan:

• Objek (merpati) = siswa
• Wadah (sarang merpati) = jenjang kelas

Jadi kita sedang memasukkan 115 siswa ke dalam 3 jenjang kelas.

Jika terdapat: N objek dan K wadah

maka paling sedikit jumlah objek yang dijamin berada dalam satu wadah adalah:

$$
\left\lceil \frac{N}{K} \right\rceil
$$

di mana tanda \(\lceil \ \rceil\) berarti pembulatan ke atas (ceiling).

▶ Menerapkan ke soal

Total siswa (objek) \(N = 115\)
Jumlah jenjang kelas (wadah) \(K = 3\)

Maka: \(\left\lceil \dfrac{115}{3} \right\rceil\) =⌈38,33…⌉=39

Karena hasil pembagian tidak bulat, maka harus dibulatkan ke atas menjadi 39.
Artinya meskipun pembagian siswa dibuat seadil mungkin, tetap akan ada satu jenjang yang punya paling sedikit 39 siswa.

Terdapat 121 anak dan setiap anak pasti lahir pada salah satu dari 12 bulan.
Dalam konteks prinsip sarang merpati:

• Objek (merpati) = anak
• Wadah (sarang) = bulan lahir
  → jumlah wadah = 12

Kita gunakan rumus:

\(\left\lceil \dfrac{N}{K}\right\rceil=\left\lceil\dfrac{121}{12} \right\rceil\)

Hitung: \(\dfrac{121}{12}=10,0833…\)

Karena hasil pembagian tidak bulat, maka dibulatkan ke atas, menjadi: \(\boxed{11}\)

1. Tentukan “merpati” dan “sarang”

Sesuai Prinsip Sarang Merpati (Pigeonhole Principle):

Total peserta = 780
Total wadah (hari) = 7

2. Terapkan rumus pigeonhole

Kita ingin mengetahui paling sedikit jumlah orang yang pasti sama hari lahirnya, meskipun pembagian dibuat seadil mungkin.

Gunakan perhitungan:

⌈ 780 / 7 ⌉

Hitung dulu pembagiannya:

780 / 7 = 111,428...

Karena hasilnya tidak bulat, ambil pembulatan ke atas (ceiling):

⌈ 111,428... ⌉ = 112

3. Makna hasilnya

Jika setiap hari memiliki tepat 111 peserta, total baru:

7 × 111 = 777 peserta

Masih ada 3 peserta tersisa, dan mereka harus masuk ke salah satu hari lahir.

Sehingga pasti ada hari yang berisi:

111 + 1 = 112 peserta

Itulah jumlah minimal yang terjamin pasti terjadi.

Jadi, paling sedikit 112 peserta lahir pada hari yang sama.

Bayangkan kita coba “menghemat” supaya tidak ada huruf yang dipakai terlalu banyak orang.

• Misalkan setiap huruf awal nama dipakai maksimal 4 orang.
• Total orang yang bisa ditampung dengan aturan ini: 26 × 4 = 104 orang

Padahal kita punya 120 orang.
Masih ada 120 − 104 = 16 orang yang belum “kebagian huruf”.

Begitu 1 saja dari sisa 16 orang itu ditambahkan ke salah satu huruf, huruf tersebut langsung punya 5 orang. Jadi mustahil kalau semua huruf dipakai paling banyak 4 orang saja.

Jadi kesimpulannya benar:
pasti ada huruf depan nama yang digunakan oleh sedikitnya 5 orang.

1) Tabel Pasangan Bilangan Jumlah 30

(pasangan diberi warna agar langsung terlihat hubungannya)

🔹 Ada 9 pasang bilangan yang jumlahnya 30
🔹 Mengambil dua bilangan dalam warna yang sama → otomatis jumlahnya 30

2) Bilangan Aman (Tidak Memiliki Pasangan Jumlah 30)

Total 6 angka aman

Semua angka ini boleh diambil tanpa membentuk jumlah 30.

3) Blok Pigeonhole

Visual interpretasi:

• Total sarang = 10
  • 9 sarang pasangan
  • 1 sarang untuk bilangan aman (6 angka)

4) Cara Kerja Pigeonhole-nya

Untuk menghindari pasangan 30:

✔ Ambil semua bilangan aman → 6 angka
✔ Ambil satu saja dari tiap pasangan → 9 angka
Total masih aman = 6 + 9 = 15 bilangan

Namun…

Saat memilih bilangan ke-16, kita pasti mengambil angka dari pasangan yang satunya → terbentuk jumlah 30

Rentang bilangan: 15 s.d. 80
Total bilangan = 80 − 15 + 1 = 66 bilangan

Kita cari pasangan jumlah 60

(15,45), (16,44), (17,43), (18,42), (19,41),
(20,40), (21,39), (22,38), (23,37), (24,36),
(25,35), (26,34), (27,33), (28,32), (29,31)

Ada 15 pasangan

Bilangan yang tidak bisa membentuk jumlah 60 totalnya:

30 → 1 bilangan
46–80 → 35 bilangan
Sehingga bilangan aman = 36

Untuk menghindari jumlah 60 selama mungkin:

• Ambil semua bilangan aman → 36
• Ambil satu dari tiap pasangan → 15

Maksimal tanpa terbentuk pasangan = 36 + 15 = 51

Maka bilangan ke-52 pasti membentuk pasangan berjumlah 60.

Jawaban: 52 (opsi D)

Untuk menghindari agar tidak ada dua bilangan yang selisihnya 80, kita harus mengambil bilangan dengan jarak maksimal 80, yaitu: 1,  2,  3,  …,  80 (sebanyak 80 bilangan)

Selama kita hanya mengambil bilangan 1–80, belum ada yang berpasangan membentuk selisih 80.

Namun, jika kita mengambil satu bilangan lagi saja, yaitu salah satu dari: 81,  82,  83,  …,  150

maka pasti ada bilangan yang membentuk selisih 80, misalnya: (1,  81),  (2,  82),  (3,  83),  …,  (70,  150)

Artinya, kita tidak bisa menghindari terbentuknya pasangan selisih 80 lagi.

Jadi, paling sedikit bilangan yang harus dipilih agar pasti terdapat dua bilangan yang selisihnya 80 adalah 81.

Jawaban yang benar: C

Kita ingin memastikan ada nomor tertentu yang muncul minimal 10 kali.
Untuk menjamin hal ini, kita harus pertimbangkan kondisi paling buruk (terburuk/paling apes), yaitu:

kita mengambil kartu sebanyak mungkin tetapi belum ada satu pun nomor yang muncul sampai 10 buah.

Artinya, kita ambil dari setiap nomor maksimal 9 kartu dulu, supaya tidak ada nomor yang mencapai 10.

Tapi…

Jumlah kartu tiap nomor berbeda-beda, jadi tidak semua nomor punya 9 kartu.
Maka kita ambil sebanyak mungkin kartu, tetapi jumlah dari setiap nomor ≤ 9.

🔥 Nomor yang punya ≥10 kartu hanya mulai dari kartu bernomor 10

Mari hitung:

1. Ambil semua kartu nomor 1 s.d. 9 (belum mencapai 10)

\(1+2+3+\cdots+9 = \dfrac{9 \cdot 10}{2}=45\)

2. Ambil 9 kartu dari nomor 10 sampai nomor 20

Nomor yang ≥10 yaitu 10–20 → total 11 nomor \(11 \cdot 9 = 99\)

Sampai di sini total kartu yang sudah diambil tetapi belum ada yang mencapai 10 adalah: 45+99=144

Jika kita mengambil 1 kartu lagi, kartu itu pasti membuat salah satu nomor mencapai 10 buah.

Jadi jumlah minimal kartu agar pasti ada 10 kartu bernomor sama adalah:

\(\boxed{145}\)

✔ pilihan jawaban yang benar: C. 145

Ambil kondisi paling buruk:

• Ambil 52 sumpit → semuanya putih
  Hasil: sudah ada 1 pasang non-cokelat

Poin penting: terpenuhi hanya dengan 2 putih, tetapi saat kita ambil 52 sekaligus, pasangan itu sudah muncul otomatis.

Maka komponen yang memicu pasangan non-cokelat adalah 2 sumpit
→ namun karena pengambilan acak bisa saja kita mengambil semua putih dulu, maka batas yang aman untuk memastikan kondisi sudah lewat adalah: 52

2) Untuk memenuhi 3 pasang bukan putih = 6 sumpit non-putih

Bukan putih = kuning + cokelat = 81 sumpit

Agar belum mencapai 6 sumpit non-putih, ambil sebanyak mungkin putih terlebih dahulu: \(52\text{ putih} + 6\text{ non putih} = 58\)

Tetapi…

Jika 6 non-putih sudah didapat, kondisi ini terpenuhi.
Namun kita juga wajib memastikan kondisi pasangan bukan cokelat juga terpenuhi, yaitu minimal 2 non-cokelat.

Maka bila 1 sumpit berikutnya (setelah 58) adalah kuning atau putih, pasangan non-cokelat langsung terjamin. 58+1=59

Jadi jumlah sumpit minimal yang harus diambil untuk memenuhi kedua kondisi adalah \(\boxed{59}\)

Jawaban: C. 59

◉ Bagian I → 8 soal B/S

Setiap soal punya 2 kemungkinan.
Maka banyak pola jawaban di Bagian I: 256 kemungkinan jawaban diperoleh dari \(2^8 = 256 \text{ kemungkinan jawaban}\) kemungkinan jawaban

Artinya, 256 siswa masih bisa saja punya jawaban yang semuanya berbeda, asalkan semua memilih pola yang berbeda-beda.

◉ Bagian II → 1 soal, 3 pilihan jawaban

3 kemungkinan jawaban diperoleh dari \(3^1 = 3 \text{ kemungkinan jawaban}\)

🔥 Gabungan Jawaban Lengkap

Setiap siswa mengisi Bagian I dan Bagian II → Jawaban final seorang peserta adalah kombinasi keduanya.

Total kombinasi jawaban siswa: \(256 \times 3 = 768\)

Ini berarti:

🔹 Jumlah pola jawaban unik maksimum adalah 768.
🔹 Jika tepat 768 siswa mengikuti ujian, masih mungkin seluruhnya berbeda.

Belum ada jaminan dua siswa sama jawabannya.

🎯 Prinsip Sarang Merpati (Pigeonhole Principle)

Jika kita memiliki:

• 768 kotak jawaban
• 769 siswa

maka menurut Pigeonhole Principle:

Jika jumlah objek (siswa) lebih banyak daripada jumlah kotak (pola jawaban), maka pasti ada kotak yang terisi ≥ 2 siswa.

Artinya: 768+1=769

Dengan 769 peserta, mustahil semuanya berbeda.
Pasti ada minimal dua siswa yang memiliki pola jawaban yang sama persis dari awal sampai akhir.

📌 Jawaban Akhir

\(\boxed{769}\)

Pilihan yang benar → D. 769

🧠 Kalimat yang paling sederhana:

768 siswa masih bisa saja berbeda semua.
Siswa ke-769 pasti meniru pola salah satu siswa sebelumnya.

Itulah inti Pigeonhole Principle.

bahas

bahas

bahas

bahas

bahas

bahas