Problem

Source: Iranian National Olympiad (3rd Round) 2002

Tags: combinatorics proposed, combinatorics



15000 years ago Tilif ministry in Persia decided to define a code for $n\geq2$ cities. Each code is a sequence of $0,1$ such that no code start with another code. We know that from $2^{m}$ calls from foreign countries to Persia $2^{m-a_{i}}$ of them where from the $i$-th city (So $\sum_{i=1}^{n}\frac1{2^{a_{i}}}=1$). Let $l_{i}$ be length of code assigned to $i$-th city. Prove that $\sum_{i=1}^{n}\frac{l_{i}}{2^{i}}$ is minimum iff $\forall i,\ l_{i}=a_{i}$