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