Asked in Germany in WW2Math and ArithmeticMathematicians
How do you explain the pigeonhole principle?
August 04, 2011 12:07AM
The pigeonhole principle is merely the following observation - "If we are to place N balls into M boxes where N > M, at least one box will contain at least two balls."
A generalized version of the pigeonhole principle says that if we place at least nk + 1 balls into n boxes, then at least one box will contain at least k+1 balls. I say "at least" a lot because these numbers are arbitrary and lower bounds.