[I copied over Alkjash's post, which linked to a PDF to LessWrong, to test our editor and generally show that it's not super hard to copy over things from existing LaTeX material. It took me about 8 minutes to convert the PDF to our formatting]

Introduction

This is the start of a sequence on the entropy method in combinatorics. As with any method in combinatorics, it's best explained by solving a series of problems. The best references on the subject are Chapter 14 of Alon and Spencer [1] and Radhakrishnan's expository paper [2].

Today, we solve three toy problems to motivate the definition of entropy.

1. Sorting

At his summer job at Ollivander's, Harry is given $n$ wands of unknown weight $w_{1}, \dots, w_{n}$ which he is to sort in increasing order. All Harry has to work with is a balance scale which determines the relative masses of any two wands $w_{i}$ and $w_{j}$ . How many weighings does Harry need?

Take a minute to think about this problem if you haven't seen it before.

1.1 Solution

In the beginning, Harry is agnostic about which of $n!$ possible orderings is the true answer. In his mind there are $n!$ possible worlds, one for each ordering of the wands.

After some number of weighings, suppose Harry sees a set $S$ of possible worlds before he weighs $w_{i}$ and $w_{j}$ against each other. The answer lets him distinguish between the set of worlds $S_{<}$ in which $w_{i} < w_{j}$ and the set of worlds $S_{>}$ in which $w_{i} > w_{j}$ . Either way, he gets to eliminate one or the other.

But Harry may be unlucky and only eliminate the smaller of $S_{<}$ and $S_{>}$ at each step. He will be left with the larger of $S_{<}$ and $S_{>}$ , which is at least half the size of $S$ . That is, each weighing decreases the total number of possible worlds by at most a factor of two.

Thus, he needs $l o g_{2} n!$ steps to halve the total number of possible worlds down to a unique one.

1.2 Exercises

1. Check that $l o g_{2} n! = Θ (n l o g n)$ , so this lower bound matches the best possible sorting algorithm runtime.

2. Check that being allowed to weigh any set of weights against any other set doesn't help - Harry still needs $l o g_{2} n!$ weighing operations.

3. What is the exact number of weighings needed to sort 5 wands?

4. The solution suggests that a good sorting algorithm balances the sizes of $S_{<}$ and $S_{>}$ as closely as possible at each step. How does your favorite sorting algorithm do in this regard?

2. Twenty Questio

... ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,