MathDB

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}

22