Comment by paulddraper

The first time I saw the Pigeonhole Principle was in the following:

Problem: A plane has every point colored red, blue, or yellow. Prove that there exists a rectangle whose vertices are the same color.

Solution: Consider a grid of points, 4 rows by 82 columns. There are 3^4=81 possible color patterns of columns, so by the Pigeonhole Principle, at least two columns have the same color pattern. Also by the Pigeonhole Principle, each column of 4 points must have at least two points of the same color. The two repeated points in the two repeated columns form a rectangle of the same color. QED.

The Pigeonhole Principle is very neat. It would be hard not to use it for the proof.

Partly that article argues against proof by contradiction which does seem to be overused.