The problem goes as follows:
A bag contains 16 balls of following colors: 8 red, 4 blue, 2 green, 1 black and 1 white. Alice picks a ball randomly from the bag and messages Bob its color using a string of zeros and ones. She replaces the ball in the bag and repeats this experiment many times. What is the minimum expected length of the message she has to convey to Bob per experiment?
Now, what I thought was that since we have to find the expected length of message, we can design an encoding for the colour of the balls.
So, we can represent it as:
Red = 0, Blue = 1, Green = 01, Black = 11 and White = 100.
Using this, I got the expected number of bits as:
$8 \times 1 + 4 \times 1 +2 \times 2 + 1 \times 2 + 1 \times 3 = 21$, and dividing this 16 for the total number of draws, I got the answer as $21/16$.
However, this does not match with the solution.
What should be the correct approach?
You should be able to use some kind of compression when sending your data.
Because there are a different number of each color of ball i would suggest using A binary tree type of compression. Huffman compression is ideal for this.
Here's a great video on it Link
If you pre-compute the tree (and both Bob and Alice have access to it) that should be the best possible message size