I have a given number $N$ of binary numbers, that are stored using a given number $B$ of bits. $B$ is the same for all the numbers.
For example, thease values where $N = 4, B = 4$.
0000 (zero)
0001 (one)
1111 (fifteen)
1001 (nine)
Q: I take the average, how many bits $R$ do I need to store the result with an ordinary binary number?
My workings before the answer:
The average of the above example, adding extra bits to the result:
0000 (zero)
0001 (one)
1111 (fifteen)
1001 (nine)
=
0110.01 (6.25)
One might assume that combining all four, 4 bit numbers requires 16 bits, $R = N * B$, however many of thease values will represent impossible results. For example when $N = B = 4$, $R$ cannot equal $0000.000000000001$.
So I know that in just the case where $N = B = 4$, that $5 < R < 16$.
Suppose $p\neq 2$ is a prime factor of $N$ and choose $N$ numbers such that their sum is ${N \over p}$, then the result is ${ 1\over p}$ which has a non terminating binary expansion. Hence the only non problematic $N$ are those that are powers of $2$.
So, suppose $N = 2^n$ for some $n$ (hence dividing by $N$ corresponds to a right shift of $\log_2 N$ bits). Since the sum of the numbers must lie between $0$ and $2^n (2^{B+1}-1)\le 2^{n+B+1} -1$, we see that at most $n+B$ bits are required, and by considering $2^n-1 $ copies of the number $2^B$ and one number of $2^B+1$, we see that the sum is $1+2^{n+B}$, hence at least $n+B$ bits are required, hence we see that $B+\log_2 N$ bits are required.