I've just come across this proof of the Graham-Pollak Theorem by Sundar Vishwanathan (thanks to Konrad Swanepoel's sporadic comments about it on this site), that must be called beautiful after its author. The paper mentions (after lemma 3) that certain other linear algebra proofs can also be replaced by similar pigeonhole principle applications. But I couldn't find any, so I thought that we should collect some similar beautiful proofs here. I don't mind if it also uses parity or other tricks, but linear algebra should be replaced! For example, can anyone prove the Oddtown theorem?