Lompat ke konten utama
Kelas
Matematika DiskritPelajaran 7 dari 16 · Modul 2, Kombinatorika

Modul 2 · Kombinatorika

Prinsip sarang merpati

Setelah pelajaran ini kamu bisa memakai prinsip sarang merpati, termasuk bentuk umumnya, untuk menjamin adanya dua objek atau lebih di kelompok yang sama.

  • ±13 menit
  • 3 latihan
  • Diperiksa 27 Sep 2026

Latihan di pelajaran ini butuh akun gratis. Progres, kode, dan catatanmu hanya tersimpan di browser ini. Masuk untuk menyimpannya

Materi

Prinsip sarang merpati berbunyi: bila lebih dari n merpati masuk ke n sarang, paling sedikit satu sarang berisi dua merpati atau lebih. Buktinya singkat: kalau setiap sarang berisi paling banyak satu merpati, merpatinya paling banyak n ekor, padahal jumlahnya lebih dari n. Bentuk umumnya: bila N objek dibagi ke k kelompok, paling sedikit satu kelompok berisi ⌈N ÷ k⌉ objek atau lebih, dengan ⌈x⌉ berarti x dibulatkan ke atas. Prinsip ini menjamin keberadaan, tetapi tidak menunjuk kelompok mana yang penuh.

Prinsip ini dipakai untuk menjawab pertanyaan “paling sedikit berapa yang harus diambil supaya pasti…”, dan untuk membuktikan bahwa tabrakan tidak terhindarkan: kode pendek yang dipakai untuk terlalu banyak barang pasti ada yang kembar. Contoh: di antara 13 orang pasti ada dua yang lahir di bulan yang sama, karena bulannya hanya 12. Contoh bentuk umum: 40 dadu dilempar, dan setiap dadu mendarat di salah satu dari 6 sisi, sehingga paling sedikit ⌈40 ÷ 6⌉ = 7 dadu menunjukkan angka yang sama. Di Python, pembulatan ke atas ditulis math.ceil.

import math

print(math.ceil(40 / 6))   # 7

Latihan

Jawaban diperiksa di server. Lulus berarti kamu memahami contohnya, bukan penilaian seluruh pekerjaanmu.

Latihan 1 dari 3

Sebuah laci berisi kaus kaki lepas dalam empat warna, masing-masing banyak. Dalam gelap, paling sedikit berapa kaus kaki yang harus diambil supaya pasti ada dua yang warnanya sama?

Latihan 2 dari 3

Ujian diikuti 250 peserta, dan nilainya bilangan bulat dari 0 sampai 100. Berapa angka terbesar yang pasti benar untuk kalimat “paling sedikit … peserta mendapat nilai yang sama”?

Latihan 3 dari 3

Sebuah sekolah punya 400 siswa. Pernyataan: “Pasti ada paling sedikit dua siswa yang berulang tahun pada tanggal dan bulan yang sama.” Bagaimana menilainya?

Pilih satu jawaban

Catatanmu

Memuat catatan…

tersimpan otomatis, ikut tercetak · 0/4.000

Lanjutkan ke

Tampilkan 1 lagi