Information Theory used to prove neat combinatorial statements?
Moser's proof of the constructive Lovasz Local Lemma.  He basically shows that, under the conditions of the local lemma, the second-simplest algorithm for SAT you can think of works.  (The first simplest might be to just try a random assignment until one works.  The second simplest is took pick a random assignment, find an unsatisfied clause, satisfy it, then see what other clauses you broke, recurse, and repeat until done.)  The proof that this runs in polynomial time is perhaps the most elegant use of information theory (or Kolmogorov complexity, whatever you want to call it in this case) I've ever seen.