Erdös–Surányi問題の一般化をしていたら,2022JMO予選P11の一般化がでてきた!!
はじめに
任意の$m,n\in\mathbb Z_{\geqslant0}$に対して,$N\in\mathbb Z_{\geqslant0},\varepsilon:\{0,\cdots,N\}\longrightarrow\{1,-1\}$が存在して,以下をみたす.
$$m=\sum_{i=0}^N\varepsilon(i)i^n$$
本当は,$N,\varepsilon$がいっぱいあるという主張ですが,あんまり変わらないので,存在性だけにフォーカスします.証明の途中で興味深い事実があり,少し深掘りします.
証明パート
$i,j\in\mathbb Z_{\geqslant0},j<2^i$として,$\varepsilon(i,j)\in\{1,-1\}$を以下のように定義する.
\begin{equation*} \varepsilon (i,j)= \left\{ \begin{array}{ll} 1 & (i=j=0) \\ -\varepsilon(i-1,j) & (0\leqslant j<2^{i-1}) \\ \varepsilon(i-1,j-2^{i-1}) & (2^{i-1}\leqslant j<2^i) \end{array} \right. \end{equation*}
$n,k\in\mathbb Z_{\geqslant0},n< k$
$$\sum_{i=0}^{2^k-1}\varepsilon(k,i)(x+i)^n=0$$
(左辺は$x$に関する多項式)
(追記)$\displaystyle {\sum_i\varepsilon(n>0,i)=0}$なので明らかでした
$k=n+1$のときだけ見れば十分.なぜなら,
$$\sum_{i=0}^{2^k-1}\varepsilon(k,i)(x+i)^n=0 \Longrightarrow \sum_{i=0}^{2^{k+1}-1}\varepsilon(k+1,i)(x+i)^n=0$$
が成り立つからである.
$n=0$のときは明らかである.任意の$l\in\mathbb Z_{\geqslant0}$に対して,$n$が$l$以下なら主張が成り立つという仮定の下で$n=l+1$のとき成り立つことを示せばいい.
\begin{equation*}
\begin{split}
\sum_{i=0}^{2^l-1}\varepsilon(l,i)(x+i)^l &=\sum_{i=0}^{2^l-1}\sum_{j=0}^l \varepsilon(l,i)\binom ljx^{l-j}i^j\\
&=\sum_{j=0}^l\binom ljx^{l-j}\sum_{i=0}^{2^l-1}\varepsilon(l,i)i^j\\
&=\sum_{i=0}^{2^l-1}\varepsilon(l,i)i^l
\end{split}
\end{equation*}
つまり,
\begin{equation*}
\begin{split}
0&=\sum_{i=0}^{2^l-1}-\varepsilon(l,i)(x+i)^l+\sum_{i=0}^{2^{l}-1}\varepsilon(l,i)(x+2^l+i)^l\\
&=\sum_{i=0}^{2^l-1}\varepsilon(l+1,i)(x+i)^l+\sum_{i=2^l}^{2^{l+1}-1}\varepsilon(l+1,i)(x+i)^l\\
&=\sum_{i=0}^{2^{l+1}-1}\varepsilon(l+1,i)(x+i)^l
\end{split}
\end{equation*}
$$\sum_{i=0}^{2^n-1}\varepsilon(n,i)(x+i)^n=2^{\frac12n(n-1)}n!$$
補題２の証明の途中にもあったように,$x=0$のときだけ考えればいい.
$$a_n=\sum_{i=0}^{2^n-1}\varepsilon(n,i)i^n=\sum_{i=0}^{2^n-1}\varepsilon(n,i)(x+i)^n$$
とおく.$a_0=1$で,
\begin{equation*}
\begin{split}
a_{n+1}&=\sum_{i=0}^{2^{n+1}-1}\varepsilon(n+1,i)i^{n+1}\\
&=\sum_{i=0}^{2^n-1}\varepsilon(n,i)((i+2^n)^{n+1}-i^{n+1})\\
&=\sum_{i=0}^{2^n-1}\sum_{j=0}^{n}\varepsilon(n,i)\binom{n+1}{j}i^j2^{n(n+1-j)}\\
&=\sum_{j=0}^{n}\binom{n+1}{j}2^{n(n+1-j)}\sum_{i=0}^{2^n-1}\varepsilon(n,i)i^j\\
&=(n+1)2^n\sum_{i=0}^{2^n-1}\varepsilon(n,i)i^n\\
&=(n+1)2^na_n\ \ \ (n\geqslant0)
\end{split}
\end{equation*}
が成り立つので,$a_n=2^{\frac12n(n-1)}n!a_0=2^{\frac12n(n-1)}n!$.
$n,L\in\mathbb Z_{\geqslant0}$,$L>1$.任意の$l\in\mathbb Z$に対して,$N\in\mathbb Z_{\geqslant0},\varepsilon':\{0,\cdots,N\}\longrightarrow\{1,-1\}$が存在して,以下をみたす.
$$l\equiv\sum_{i=0}^N\varepsilon'(i)i^n \pmod L$$
$k\in\mathbb Z_{>0}$に対して,以下が明らか.
\begin{equation*}
\begin{array}{cl}
2k&\displaystyle{\equiv\sum_{j=0}^{2k-1}\left((jL+1)^n+(-1)^j\sum_{i=2}^{L}(jL+i)^n\right)}\\
2k+1&\displaystyle{\equiv\sum_{j=0}^{2k-1}\left((jL+1)^n+(-1)^j\sum_{i=2}^{L}(jL+i)^n\right)}+(2kL+1)^n
\end{array}
\pmod L
\end{equation*}
もう明らかだが,せっかくなので具体的に書き表してみる.
$\mathrm{sgn}:\mathbb R\longrightarrow\mathbb R$
\begin{equation*}
\mathrm{sgn}(x)=\left\{
\begin{array}{ll}
0 & (x=0)\\
1 & (x>0)\\
-1 & (x<0)
\end{array}
\right.
\end{equation*}
補題３に$L=2^{\frac12n(n-1)}n!$($n=0$は考えない)を適用すれば,任意の$m\in\mathbb Z_{\geqslant0}$に対して,$A\in\mathbb Z,N\in\mathbb Z_{\geqslant0},\varepsilon':\{0,\cdots,N\}\longrightarrow\{1,-1\}$が存在して,以下をみたす.
$$m+2^{\frac12n(n-1)}n!A=\sum_{i=0}^N\varepsilon'(i)i^n$$
$A=0$なら目的は達成されるので,$A\ne0$のときだけ考える.補題２より,
$$2^{\frac12n(n-1)}n!A=\sum_{i=0}^{\mid A\mid-1}\sum_{j=0}^{2^n-1}\mathrm{sgn}(A)\varepsilon(n,j)(x+i2^{\frac12n(n-1)}n!+j)^n$$
が成り立つので,
$$m=\sum_{i=0}^N\varepsilon'(i)i^n+\sum_{i=0}^{\mid A\mid-1}\sum_{j=0}^{2^n-1}-\mathrm{sgn}(A)\varepsilon(n,j)(N+1+i2^{\frac12n(n-1)}n!+j)^n$$
と書ける.
気になったこと
$k$を正の整数とする.正の整数$n$に対して,$f(n)$を
\begin{equation}
f(n)=\left\{
\begin{array}{ll}
n^{d} & (nの各桁の和が偶数のとき),\\
-n^{d} & (nの各桁の和が奇数のとき)
\end{array}
\right.
\end{equation}
と定める.$S=f(1)+f(2)+\cdots+f(10^{d}-1)$を$5^m$が割り切るような最大の非負整数$m$を求めよ.(十進法で表すものとする)
$S=10^{\frac12d(d-1)}(-5)^dd!$と書ける.これ系とすごく似ています.$\varepsilon$も,符号の調整で分かりにくくなっていますが,値は二進法で表した時の各桁の和の偶奇に依存しています.逆に,二進法のときでうまくいくなら,$n$進法でも同じようにできそうです.
少し頑張ると以下のようなことが分かりました.
$n\in\mathbb Z_{\geqslant0},k\in\mathbb Z_{>0}$,$k$は偶数.
$i,j\in\mathbb Z_{\geqslant0},j< k^i$に対して,$\varepsilon(i,j)\in\{1,-1\}$を次のように定める.
\begin{equation}
\varepsilon(i,j)=\left\{
\begin{array}{ll}
1 & (i=j=0)\\
-\varepsilon\left(i-1,j-k^{i-1}\left\lfloor\dfrac{j}{k^{i-1}}\right\rfloor\right) & \left(j\in\displaystyle\bigcup_{l=0}^{\frac k2-1}\left[\right.\left.2lk^{i-1},(2l+1)k^{i-1}\right)\right)\\
\varepsilon\left(i-1,j-k^{i-1}\left\lfloor\dfrac{j}{k^{i-1}}\right\rfloor\right) & \left(j\in\displaystyle\bigcup_{l=1}^{\frac k2}\left[\right.\left.(2l-1)k^{i-1},2lk^{i-1}\right)\right)
\end{array}
\right.
\end{equation}
このとき,以下が成り立つ.
$$a_n=\sum_{i=0}^{k^n-1}\varepsilon(n,i)(x+i)^n=k^{\frac12n(n+1)}2^{-n}n!$$
同じような流れで,
$$\sum_{i=0}^{k^n-1}\varepsilon(n,i)(x+i)^n=\sum_{i=0}^{k^n-1}\varepsilon(n,i)i^n$$
が分かり,$n< l$に対して,
\begin{equation}
\begin{split}
\sum_{i=0}^{k^{l}-1}\varepsilon(l,i)(x+i)^n=0
\end{split}
\end{equation}
が分かる.これを合わせると,
\begin{equation}
\begin{split}
a_n&=\sum_{i=0}^{k^n-1}\varepsilon(n,i)(x+i)^n\\
&=\sum_{i=0}^{k^n-1}\varepsilon(n,i)i^n\\
&=\sum_{i=0}^{k^{n-1}-1}\sum_{j=0}^{k-1}(-1)^{j+1}\varepsilon(n-1,i)(jk^{n-1}+i)^n\\
&=\sum_{i=0}^{k^{n-1}-1}\sum_{j=0}^{k-1}\sum_{l=0}^n(-1)^{j+1}\varepsilon(n-1,i)\binom nli^lj^{n-l}k^{(n-1)(n-l)}\\
&=\sum_{l=0}^n\binom nlk^{(n-1)(n-l)}\sum_{j=0}^{k-1}(-1)^{j+1}j^{n-l}\sum_{i=0}^{k^{n-1}-1}\varepsilon(n-1,i)i^l\\
&=\sum_{j=0}^{k-1}(-1)^{j+1}\sum_{i=0}^{k^{n-1}-1}\varepsilon(n-1,i)i^n+nk^{n-1}a_{n-1}\sum_{j=0}^{k-1}(-1)^{j+1}j\\
&=nk^n2^{-1}a_{n-1} \ \ \ (n>0)
\end{split}
\end{equation}
が分かるので,$a_0=1$に注意すると,$a_n=k^{\frac12n(n+1)}2^{-n}n!\ (n\geqslant0)$を得る.
おしまい
$k$が奇数のときは別のアプローチで進めないとダメなんですかね.
ありがとうございました.
この記事を高評価した人
この記事に送られたバッジ
投稿者
