HMMT-Nov 2017 thm, Problem 7

On a blackboard a stranger writes the values of $s_{7}(n)^{2}$ for $n=0,1, \ldots, 7^{20}-1$, where $s_{7}(n)$ denotes the sum of digits of $n$ in base 7. Compute the average value of all the numbers on the board.

Solution: Solution 1: We solve for 0 to $b^{n}-1$ and $s_{b}(n)^{2}$ (i.e. base $b$ ). Let $n=d_{1} \ldots d_{n}$ in base $b$, where there may be leading zeros. Then $s_{b}(n)=d_{1}+\cdots+d_{n}$, regardless of the leading zeros. \[ \mathbb{E}\left[s_{d}(n)^{2}\right]=\mathbb{E}\left[\left(d_{1}+\cdots+d_{n}\right)^{2}\right]=\sum_{1 \leq i \leq n} \mathbb{E}\left[d_{i}^{2}\right]+2 \sum_{1 \leq i<j \leq n} \mathbb{E}\left[d_{i} d_{j}\right] \] and now notice that we can treat choosing $n$ uniformly as choosing the $d_{i}$ uniformly independently from $\{0, \ldots, b-1\}$. Thus this simplifies to \[ \mathbb{E}\left[s_{d}(n)^{2}\right]=n \mathbb{E}\left[d_{1}^{2}\right]+n(n-1) \mathbb{E}\left[d_{1}\right]^{2} \] Now \[ \begin{gathered} \mathbb{E}\left[d_{1}^{2}\right]=\frac{0^{2}+\cdots+(b-1)^{2}}{b}=\frac{(b-1)(2 b-1)}{6} \\ \mathbb{E}\left[d_{1}\right]=\frac{0+\cdots+(b-1)}{b}=\frac{b-1}{2} \end{gathered} \] so the answer is \[ n \cdot \frac{(b-1)(2 b-1)}{6}+n(n-1) \cdot\left(\frac{b-1}{2}\right)^{2} \] Plugging in $b=7, n=20$ yields the result. Solution 2: There are two theorems we will cite regarding variance and expected value. The first is that, for any variable $X$, \[ \operatorname{Var}(X)=E\left[X^{2}\right]-E[X]^{2} \] The second is that, for two independent variables $X$ and $Y$, \[ \operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y) \] Let $X$ be the sum of all of the digits. We want to find $E\left[X^{2}\right]$. The expected of a single digit is $\frac{1}{7}(0+1+2+3+4+5+6)=3$. Thus, the expected value of the sum of the digits is $E[X]=20 \times 3=60$, so $E[X]^{2}=3600$. The variance of a single digit is $\frac{1}{7}\left[(0-3)^{2}+(1-3)^{2}+\ldots+(6-3)^{2}\right]=\frac{9+4+1+0+1+4+9}{7}=4$. Since the digits are independent, their variances add by the second theorem above. Therefore, the variance of the sum of all of the digits is $\operatorname{Var}(X)=20 \times 4=80$. Finally, using the first theorem, we have $E\left[X^{2}\right]=E[X]^{2}+\operatorname{Var}(X)=3680$. $\fbox{3680}$.

Answer: 3680