JMO2022予選11

JMO2022予選11の解説をしようと思います。 (問題はこちら)
解答はすでにツイートしているので、ここでは思考の過程を書いていこうと思います。

まず、問題の条件から、$n=10^{99}a_1+10^{98}a_2+\cdots+a_{100}$$(0\leq a_i\leq9)$に対して各桁の和は$a_1+a_2+\cdots+a_{100}$なので$f(n)=(-1)^{a_1+a_2+\cdots+a_{100}}(10^{99}a_1+10^{98}a_2+\cdots+a_100)^100$であり、
$S$は
$\displaystyle\sum_{a_1=0}^9\sum_{a_2=0}^9\cdots\sum_{a_{100}=0}^9(-1)^{a_1+a_2+\cdots+a_{100}}(10^{99}a_1+10^{98}a_2+\cdots+a_{100})^{100}$
と表すことができます。

私はこの式を見て、これに似ているなと思いました。(後の説明で出てくるのでこれを式Aと呼びます)

ここで$S$を求めるためにどうすればいいかを考えるのですが、$S$が直接は求まらないけど$5$で割りきれる回数だけは求まるという可能性も考えて漸化式を立てるのがよさそうだと結論しました。

漸化式を立てるために文字で置いていきます。文字で置けそうなところは足す範囲($0$から$9$まで)、変数の数$100$、次数$100$の3つですが、足す範囲は変わらなそうで、変数の数と次数は必ずしも一致してなくてもよさそうなので変数の数と次数をそれぞれ$n$と$k$で置くことにしました。

$\displaystyle A_{n,k}=\sum_{a_1=0}^9\sum_{a_2=0}^9\cdots\sum_{a_n=0}^9(-1)^{a_1+a_2+\cdots+a_n}(10^{n-1}a_1+10^{n-2}a_2+\cdots+a_n)^k$とします。このとき、$S=A_{100,100}$です。

一番内側のシグマから計算していきましょう。
見やすくするために$X=10^{n-1}a_1+10^{n-2}a_2+\cdots+10a_{n-1}$とおきます。(ツイートのものとは文字の置き方を変えています)

$\displaystyle\sum_{a_n=0}^9(-1)^{a_1+a_2+\cdots+a_n}(10^{n-1}a_1+10^{n_2}a_2+\cdots+a_n)^k \\\displaystyle=(-1)^{a_1+a_2+\cdots+a_{n-1}}\sum_{a_n=0}^9(-1)^{a_n}(X+a_n)^k$であるので、$\displaystyle\sum_{i=0}^9(-1)^i(X+i)^k$について考えればよいです。

これを二項定理で展開して計算すると、$\displaystyle\sum_{i=0}^9(-1)^i(X^k+kiX^{k-1}+\frac{k(k-1)}{2}i^2X^{k-2}+\cdots+i^k) \\\displaystyle=X^k\sum_{i=0}^9(-1)^i+kX^{k-1}\sum_{i=0}^9(-1)^ii+\frac{k(k-1)}{2}\sum_{i=0}^9(-1)^ii^2+\cdots+\sum_{i=0}^9(-1)^ii^k$
となり、ここで$\displaystyle S_m=\sum_{i=0}^9(-1)^ii^m$とおくと、$\displaystyle\sum_{i=0}^9(-1)^i(X+i)^k=S_0X^k+kS_1X^{k-1}+\frac{k(k-1)}{2}S_2X^{k-2}+\cdots+S_k$
となります。また、$S_0=0,S_1=-5,S_2=45,S_3=-425,...$となります。(後でわかりますが、実際に使うのは$S_0,S_1$だけです。)

$\displaystyle\sum_{a_1=0}^9\sum_{a_2=0}^9\cdots\sum_{a_{n-1}=0}^9(-1)^{a_1+a_2+\cdots+a_{n-1}}X^k \\\displaystyle=\sum_{a_1=0}^9\sum_{a_2=0}^9\cdots\sum_{a_{n-1}=0}^9(-1)^{a_1+a_2+\cdots+a_{n-1}}10^k(10^{n-1}a_1+10^{n-2}a_2+\cdots+a_{n-1})^k \\\displaystyle=10^kA_{n-1,k}$
であることと上の結果より、
$A_{n,k}=\displaystyle\sum_{a_1=0}^9\sum_{a_2=0}^9\cdots\sum_{a_{n-1}=0}^9(-1)^{a_1+a_2+\cdots+a_{n-1}}(kS_1X^{k-1}+\frac{k(k-1)}{2}S_2X^{k-2}+\cdots+S_k) \\\displaystyle=kS_110^{k-1}A_{n-1,k-1}+\frac{k(k-1)}{2}S_210^{k-2}A_{n-1,k-2}+\cdots+S_kA_{n-1,0}\ (k\geq0)$
という漸化式が立てられました。
これにより、$A_{n,k}$を$A_{n-1,k-1},A_{n-1,k-2},\cdots,A_{n-1,0}$で表すことができました。

ここで、式Aを思い出すと$k< n$のとき$0$となっているので$A_{n,k}$についても同じことが言えると予想ができます。

$A_{n,0} (n\geq1)$を計算すると$\displaystyle A_{n,0}=\sum_{a_1=0}^9\sum_{a_2=0}^9\cdots\sum_{a_n=0}^9(-1)^{a_1+a_2+\cdots+a_n} \\\displaystyle=\left(\sum_{i=0}^9(-1)^i\right)^n=0$
となり、これと上の漸化式を組み合わせると数学的帰納法によりこの予想が成り立つことが証明できます。

これによって、漸化式において$n=k$とすることで$\displaystyle A_{n,n}=nS_110^{n-1}A_{n-1,n-1}=-5n10^{n-1}A_{n-1,n-1}$が得られます。
$\displaystyle A_{1,1}=\sum_{a_1=0}^9(-1)^{a_1}a_1=-5$であるので、この漸化式から$\displaystyle A_{n,n}=(-5)^n10^{\frac{n(n-1)}{2}}n!$がわかり、特に$A_{100,100}=5^{100}10^{4950}100!$は$5$で$5074$回割りきれます。
(完)

(これは後から思いついたのですが、より短い解法も載せておきます。)
この記事の方法を応用します。

$\displaystyle S=\sum_{a_1=0}^9\sum_{a_2=0}^9\cdots\sum_{a_{100}=0}^9(-1)^{a_1+a_2+\cdots+a_{100}}(10^{99}a_1+10^{98}a_2+\cdots+a_{100})^{100}$
において、$(10^{99}a_1+10^{98}a_2+\cdots+a_{100})^{100}$の部分を$\displaystyle\left.\left(\frac{d}{dx}\right)^{100}e^{(10^{99}a_1+10^{98}a_2+\cdots+a_{100})x}\right|_{x=0}$と変形します。

そうすると次のように変形できます。
$S=\displaystyle\sum_{a_1=0}^9\sum_{a_2=0}^9\cdots\sum_{a_{100}=0}^9(-1)^{a_1+a_2+\cdots+a_{100}}\left.\left(\frac{d}{dx}\right)^{100}e^{(10^{99}a_1+10^{98}a_2+\cdots+a_{100})x}\right|_{x=0} \\\displaystyle=\left.\left(\frac{d}{dx}\right)^{100}\sum_{a_1=0}^9\sum_{a_2=0}^9\cdots\sum_{a_{100}=0}^9(-1)^{a_1+a_2+\cdots+a_{100}}e^{(10^{99}a_1+10^{98}a_2+\cdots+a_{100})x}\right|_{x=0} \\\displaystyle=\left.\left(\frac{d}{dx}\right)^{100}\left(\sum_{a_1=0}^9(-1)^{a_1}e^{10^{99}a_1x}\sum_{a_2=0}^9(-1)^{a_2}e^{10^{98}a_2x}\cdots\sum_{a_{100}=0}^9(-1)^{a_{100}}e^{a_{100}x}\right)\right|_{x=0}$

ここで、$\displaystyle f_i(x)=\sum_{a_i=0}^9(-1)^{a_i}e^{10^{100-i}a_ix},F(x)=\prod_{i=1}^{100}f_i(x)$とおきます。
$f_i(0)=\displaystyle\sum_{a_i=0}^9(-1)^{a_i}=0$であるので、ライプニッツ則を使って$F(x)$を微分したとき$f_i(x)\ (i=1,\cdots,100)$の中に1つでも微分されていないものがあればその項は$0$を代入したときに$0$となり、各$f_i$が1回ずつ微分された項のみが残り、
$\displaystyle\left.\left(\frac{d}{dx}\right)^{100}F(x)\right|_{x=0}=100!\prod_{i=1}^{100}\left(\left.\frac{d}{dx}f_i(x)\right|_{x=0}\right)$
となります。

ここで、$\displaystyle\left.\frac{d}{dx}f_i(x)\right|_{x=0} =\left.\frac{d}{dx}\sum_{a_i=0}^9(-1)^{a_i}e^{10^{100-i}a_ix}\right|_{x=0} \\\displaystyle=\sum_{a_i=0}^9(-1)^{a_i}10^{100-i}a_i =-5\cdot10^{100-i}$
であるので、

$\displaystyle S=100!\prod_{i=1}^{100}\left(-5\cdot10^{100-i}\right)=5^{100}\cdot10^{4950}\cdot100!$
となり、$5$で割りきれる回数は$5074$回です。