Contoh 1.4.17.
Prinsip Sarang Merpati: Jika lebih dari \(n\) merpati terbang memasuki \(n\) kandang, maka setidaknya satu kandang akan memuat sedikitnya dua merpati. Buktikan pernyataan ini!
Penyelesaian.
Bukti.
Andaikan, berlawanan dengan ketentuan, bahwa setiap kandang memuat paling banyak satu merpati. Maka paling banyak terdapat \(n\) merpati. Namun, kita mengandaikan bahwa terdapat lebih dari \(n\) merpati, sehingga hal ini mustahil. Dengan demikian, pasti ada sebuah kandang yang memuat lebih dari satu merpati.
Walaupun kita merumuskan pembuktian ini sebagai pembuktian dengan kontradiksi, kita juga dapat menggunakan pembuktian melalui kontraposisi karena kontradiksi kita hanyalah negasi dari hipotesis. Kadang-kadang hal ini terjadi; dalam kasus demikian, Anda dapat menggunakan salah satu gaya pembuktian. Namun, ada pula contoh ketika kontradiksi muncul “jauh” dari pernyataan semula.