Proofs of Existence and Optimality · Non-constructive Proofs of Existence
Lesson 3
Another popular method for non-constructive proofs is the pigeonhole principle. It states that if there are \(n+1\) pigeons in \(n\) holes, then one of the holes must contain more than one pigeon. As you can see, we show that a hole with more than one pigeon exists, but we do not explicitly present it. A more general statement is: if \(nm+1\) objects are divided into \(n\) classes, then one of the classes must contain at least \(m+1\) objects.
