The Omega(n log n) Comparison-Sort Bound
A decision tree with n! leaves must be log(n!) deep, and log(n!) = Theta(n log n) by the (n/2)^(n/2) trick — the one step that costs this post its L1.
A decision tree with n! leaves must be log(n!) deep, and log(n!) = Theta(n log n) by the (n/2)^(n/2) trick — the one step that costs this post its L1.
n+1 items, n boxes, one collision. The cheapest impossibility argument in existence, and the seed for No universal lossless compressor and The birthday bound.