　一般に $a_0, a_1, \ldots, a_n$ について，以下の $2^n$ 種類の値の平均を考える．
$$(a_0 \pm a_1 \pm \cdots \pm a_n)^2$$
相異なる $i,j$ について，展開した時の $a_ia_j$ の係数が $2$ であるような符号の選び方と，$-2$ であるような符号の選び方が同数ずつ存在することから，この平均は $a_0,a_1, \ldots, a_n$ の $2$ 乗の総和に等しい．\
　本問は $n=3123$ かつ
$$a_0=\overbrace{66\cdots6}^{n桁}=\frac{2(10^n-1)}{3},\quad a_1=2,\quad a_2=20,\quad\dots,\quad a_n=2\overbrace{00\cdots0}^{n-1桁}=2\times 10^{n-1}$$
の場合であるから，次のように計算できる．
$$\begin{aligned}
M&= {\overbrace{666\cdots6^2}^{3123桁}}+\overbrace{4040\cdots4}^{6245桁} \\\\
&= \overbrace{444\cdots4}^{3122桁}3\overbrace{555\cdots5}^{3122桁}6+\overbrace{4040\cdots4}^{6245桁} \\\\
&=\overbrace{4848\cdots48}^{3122桁}3\overbrace{9595\cdots95}^{3120桁}960
\end{aligned}$$
よって求める値は $\bf{40590}$ である．
公式解説
https://onlinemathcontest.com/contests/omc083/editorial/3123
桁数が $n$ であったときの, 求める値 $M$ を $M_n$ とし, $M_n$ に関する漸化式を立てて求めよう.\
$n$ を固定し, $n$ 桁の正整数で各桁の数字が $4$ または $8$ であるようなものを $x_1,x_2\ldots x_{2^n}$ とし, $ S_n=\sum_{i=1}^{2^n} x_i^2 =2^nM_n$ とする.

$S_{n+1}$ は, 最上位が $4$ のものと $8$ のものに分けて以下のように求められる.
$$\begin{aligned}
S_{n+1} & = \sum_{i=1}^{2^n} (4\cdot 10^n+x_i)^2+(8\cdot 10^n+x_i)^2 \\\\
& = \sum_{i=1}^{2^n} 2 x_i^2 + 24\cdot 10^nx_i + 8\cdot 10^{2n+1} \\\\
& = 2 S_n + 2^{n+1} \cdot 12\cdot 10^n \cdot \frac{2}{3}(10^n-1) + 2^{n+1}\cdot 4\cdot 10^{2n+1}
\end{aligned}$$
ただし $x_i$ の相加平均は $\dfrac{2}{3}(10^n-1) $ である. $S_n=2^nM_n$ を代入すると, 所望の漸化式 $$
M_{n+1} = M_n + 48\cdot 10^{2n} - 8\cdot 10^n
$$
を得る. $M_1=40$ などを用いて $M_n$ が $10$ 進表記で求められる.
ユーザー解説
https://onlinemathcontest.com/contests/omc083/editorial/3123/40
※ $\mathrm P,\\, \mathrm E,\\, \mathrm V$ はそれぞれ確率，期待値，分散を表す．

　$3123$ を一般に $n$ とおく．各 $i$ に対し確率変数 $X_i$ を，それぞれ独立に
$$ \mathrm P[X_i = 4] = \mathrm P[X_i = 8] = \frac12 $$
となるように定め，また $X$ を
$$ X := \sum_{i=0}^{n-1} 10^i\\, X_i $$
で定める．このとき
$$ M = \mathrm E\mathopen{}\left[X^2\right] = \mathrm V[X] + \mathrm E[X]^2 $$
となるが，各 $X_i$ が独立であることから
$$ \mathrm V[X] = \mathrm V\mathopen{}\left[\sum_{i=0}^{n-1} 10^i\\, X_i\right] = \sum_{i=0}^{n-1} \mathrm V\mathopen{}\left[10^i\\, X_i\right] = \sum_{i=0}^{n-1} 10^{2i}\\, \mathrm V\mathopen{}\left[X_i\right] = 4\sum_{i=0}^{n-1} 10^{2i} = \frac4{99} \times \left(10^{2n} - 1\right)\mathclose{}, $$
また
$$ \mathrm E[X] = \mathrm E\mathopen{}\left[\sum_{i=0}^{n-1} 10^i\\, X_i\right] = \sum_{i=0}^{n-1} 10^i\\, \mathrm E\mathopen{}\left[X_i\right] = 6\sum_{i=0}^{n-1} 10^i = \frac23 \times \left(10^n - 1\right) $$
より
$$ M = \frac4{99} \times \left(10^{2n} - 1\right) + \left(\frac23 \times \left(10^n - 1\right)\right)^2 = 48 \times \frac{10^{2n} - 1}{10^2 - 1} - 8 \times \frac{10^n - 1}{10 - 1} = \overbrace{4848 \cdots 48}^{2n\text{桁}} - \overbrace{88 \cdots 8}^{n\text{桁}} $$
を得る．後は $n = 3123$ を入れることで，$M$ の桁和が $\mathbf{40590}$ と求まる．

　桁の数字の候補を増やしたり，桁の数字に重みを付けた場合でも，同様に $M$ を求めることができる．
確率論
https://onlinemathcontest.com/contests/omc083/editorial/3123/41
　$3123$ 桁の正整数であって，どの桁の数字も $4$ または $8$ であるようなものすべてについて，それぞれの $2$ 乗の（相加）平均は正整数 $M$ になることが証明できます．$M$ の各桁の和を解答してください．