The average length of strings in finite free set

Question

A finite set $S$ of binary strings is called free if no string is a prefix of other string in $S$. I need to show that the average length of string in $S$ is at least $\log n$, where $n$ is the number of string in $S$.
For example, $S=(01,101,111)$ is free, $S'=(01,011)$ isn't free, because $01$ is prefix of $011$.
Any ideas how to do it?

Answer 1

SKETCH: Let $n=|S|$, and let the lengths of the words in $S$ be $\ell_1,\ldots,\ell_n$. Then

$$\sum_{k=1}^n2^{-\ell_k}\le 1\tag{1}$$

by the Kraft-McMillan inequality. $(1)$ implies that

$$\frac{n}{\frac1{2^{\ell_1}}+\frac1{2^{\ell_2}}+\ldots+\frac1{2^{\ell_n}}}\ge n\;,\tag{2}$$

where the lefthand side of $(2)$ is the harmonic mean of the numbers $2^{\ell_1},\ldots,2^{\ell_n}$. To complete the argument, just use the fact that the harmonic mean of a set of positive real numbers is less than or equal to the geometric mean of those numbers.