2

Erdös–Surányi問題の一般化をしていたら,2022JMO予選P11の一般化がでてきた!!

152
0
$$$$

はじめに

任意の$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*}

補題2

$$\sum_{i=0}^{2^n-1}\varepsilon(n,i)(x+i)^n=2^{\frac12n(n-1)}n!$$

補題2の証明の途中にもあったように,$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*}

補題3に$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より,
$$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$$
と書ける.

気になったこと

2022JMO予選

P11改

$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$が奇数のときは別のアプローチで進めないとダメなんですかね.
ありがとうございました.

投稿日:20221223
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

kk2
kk2
57
8335
2006年に生まれました

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中