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

159

はじめに

任意の $m, n \in Z_{⩾ 0}$ に対して, $N \in Z_{⩾ 0}, ε : {0, \dots, N} ⟶ {1, - 1}$ が存在して,以下をみたす.
$m = \sum_{i = 0}^{N} ε (i) i^{n}$

本当は, $N, ε$ がいっぱいあるという主張ですが,あんまり変わらないので,存在性だけにフォーカスします.証明の途中で興味深い事実があり,少し深掘りします.

証明パート

$i, j \in Z_{⩾ 0}, j < 2^{i}$ として, $ε (i, j) \in {1, - 1}$ を以下のように定義する.

$ε (i, j) = {\begin{cases} 1 & (i = j = 0) \\ - ε (i - 1, j) & (0 ⩽ j < 2^{i - 1}) \\ ε (i - 1, j - 2^{i - 1}) & (2^{i - 1} ⩽ j < 2^{i}) \end{cases}$

参考にしました

$n, k \in Z_{⩾ 0}, n < k$
$\sum_{i = 0}^{2^{k} - 1} ε (k, i) (x + i)^{n} = 0$

(左辺は $x$ に関する多項式)
(追記) $\sum_{i} ε (n > 0, i) = 0$ なので明らかでした

$k = n + 1$ のときだけ見れば十分.なぜなら,
$\sum_{i = 0}^{2^{k} - 1} ε (k, i) (x + i)^{n} = 0 ⟹ \sum_{i = 0}^{2^{k + 1} - 1} ε (k + 1, i) (x + i)^{n} = 0$
が成り立つからである.

$n = 0$ のときは明らかである.任意の $l \in Z_{⩾ 0}$ に対して, $n$ が $l$ 以下なら主張が成り立つという仮定の下で $n = l + 1$ のとき成り立つことを示せばいい.
$\begin{aligned} \sum_{i = 0}^{2^{l} - 1} ε (l, i) (x + i)^{l} & = \sum_{i = 0}^{2^{l} - 1} \sum_{j = 0}^{l} ε (l, i) (\binom{l}{j}) x^{l - j} i^{j} \\ = \sum_{j = 0}^{l} (\binom{l}{j}) x^{l - j} \sum_{i = 0}^{2^{l} - 1} ε (l, i) i^{j} \\ = \sum_{i = 0}^{2^{l} - 1} ε (l, i) i^{l} \end{aligned}$
つまり,
$\begin{aligned} 0 & = \sum_{i = 0}^{2^{l} - 1} - ε (l, i) (x + i)^{l} + \sum_{i = 0}^{2^{l} - 1} ε (l, i) (x + 2^{l} + i)^{l} \\ = \sum_{i = 0}^{2^{l} - 1} ε (l + 1, i) (x + i)^{l} + \sum_{i = 2^{l}}^{2^{l + 1} - 1} ε (l + 1, i) (x + i)^{l} \\ = \sum_{i = 0}^{2^{l + 1} - 1} ε (l + 1, i) (x + i)^{l} \end{aligned}$

補題２

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

補題２の証明の途中にもあったように, $x = 0$ のときだけ考えればいい.
$a_{n} = \sum_{i = 0}^{2^{n} - 1} ε (n, i) i^{n} = \sum_{i = 0}^{2^{n} - 1} ε (n, i) (x + i)^{n}$
とおく. $a_{0} = 1$ で,
$\begin{aligned} a_{n + 1} & = \sum_{i = 0}^{2^{n + 1} - 1} ε (n + 1, i) i^{n + 1} \\ = \sum_{i = 0}^{2^{n} - 1} ε (n, i) ((i + 2^{n})^{n + 1} - i^{n + 1}) \\ = \sum_{i = 0}^{2^{n} - 1} \sum_{j = 0}^{n} ε (n, i) (\binom{n + 1}{j}) i^{j} 2^{n (n + 1 - j)} \\ = \sum_{j = 0}^{n} (\binom{n + 1}{j}) 2^{n (n + 1 - j)} \sum_{i = 0}^{2^{n} - 1} ε (n, i) i^{j} \\ = (n + 1) 2^{n} \sum_{i = 0}^{2^{n} - 1} ε (n, i) i^{n} \\ = (n + 1) 2^{n} a_{n} (n ⩾ 0) \end{aligned}$
が成り立つので, $a_{n} = 2^{\frac{1}{2} n (n - 1)} n! a_{0} = 2^{\frac{1}{2} n (n - 1)} n!$ .

弱い主張

$n, L \in Z_{⩾ 0}$ , $L > 1$ .任意の $l \in Z$ に対して, $N \in Z_{⩾ 0}, ε^{'} : {0, \dots, N} ⟶ {1, - 1}$ が存在して,以下をみたす.
$l \equiv \sum_{i = 0}^{N} ε^{'} (i) i^{n} (\mod L)$

$k \in Z_{> 0}$ に対して,以下が明らか.
$\begin{array}{cl} 2 k & \equiv \sum_{j = 0}^{2 k - 1} ((j L + 1)^{n} + (- 1)^{j} \sum_{i = 2}^{L} (j L + i)^{n}) \\ 2 k + 1 & \equiv \sum_{j = 0}^{2 k - 1} ((j L + 1)^{n} + (- 1)^{j} \sum_{i = 2}^{L} (j L + i)^{n}) + (2 k L + 1)^{n} \end{array} (\mod L)$

もう明らかだが,せっかくなので具体的に書き表してみる.

$sgn : R ⟶ R$
$sgn (x) = {\begin{cases} 0 & (x = 0) \\ 1 & (x > 0) \\ - 1 & (x < 0) \end{cases}$

補題３に $L = 2^{\frac{1}{2} n (n - 1)} n!$ ( $n = 0$ は考えない)を適用すれば,任意の $m \in Z_{⩾ 0}$ に対して, $A \in Z, N \in Z_{⩾ 0}, ε^{'} : {0, \dots, N} ⟶ {1, - 1}$ が存在して,以下をみたす.
$m + 2^{\frac{1}{2} n (n - 1)} n! A = \sum_{i = 0}^{N} ε^{'} (i) i^{n}$
$A = 0$ なら目的は達成されるので, $A \neq 0$ のときだけ考える.補題２より,
$2^{\frac{1}{2} n (n - 1)} n! A = \sum_{i = 0}^{∣ A ∣ - 1} \sum_{j = 0}^{2^{n} - 1} sgn (A) ε (n, j) (x + i 2^{\frac{1}{2} n (n - 1)} n! + j)^{n}$
が成り立つので,
$m = \sum_{i = 0}^{N} ε^{'} (i) i^{n} + \sum_{i = 0}^{∣ A ∣ - 1} \sum_{j = 0}^{2^{n} - 1} - sgn (A) ε (n, j) (N + 1 + i 2^{\frac{1}{2} n (n - 1)} n! + j)^{n}$
と書ける.

気になったこと

2022JMO予選

P11改

$k$ を正の整数とする.正の整数 $n$ に対して, $f (n)$ を
$f (n) = {\begin{cases} n^{d} & (n の各桁の和が偶数のとき), \\ - n^{d} & (n の各桁の和が奇数のとき) \end{cases}$
と定める. $S = f (1) + f (2) + \dots + f (10^{d} - 1)$ を $5^{m}$ が割り切るような最大の非負整数 $m$ を求めよ.(十進法で表すものとする)

$S = 10^{\frac{1}{2} d (d - 1)} (- 5)^{d} d!$ と書ける.これ系とすごく似ています. $ε$ も,符号の調整で分かりにくくなっていますが,値は二進法で表した時の各桁の和の偶奇に依存しています.逆に,二進法のときでうまくいくなら, $n$ 進法でも同じようにできそうです.
少し頑張ると以下のようなことが分かりました.

$n \in Z_{⩾ 0}, k \in Z_{> 0}$ , $k$ は偶数.
$i, j \in Z_{⩾ 0}, j < k^{i}$ に対して, $ε (i, j) \in {1, - 1}$ を次のように定める.
$ε (i, j) = {\begin{cases} 1 & (i = j = 0) \\ - ε (i - 1, j - k^{i - 1} ⌊ \frac{j}{k^{i - 1}} ⌋) & (j \in ⋃_{l = 0}^{\frac{k}{2} - 1} [2 l k^{i - 1}, (2 l + 1) k^{i - 1})) \\ ε (i - 1, j - k^{i - 1} ⌊ \frac{j}{k^{i - 1}} ⌋) & (j \in ⋃_{l = 1}^{\frac{k}{2}} [(2 l - 1) k^{i - 1}, 2 l k^{i - 1})) \end{cases}$
このとき,以下が成り立つ.
$a_{n} = \sum_{i = 0}^{k^{n} - 1} ε (n, i) (x + i)^{n} = k^{\frac{1}{2} n (n + 1)} 2^{- n} n!$

同じような流れで,
$\sum_{i = 0}^{k^{n} - 1} ε (n, i) (x + i)^{n} = \sum_{i = 0}^{k^{n} - 1} ε (n, i) i^{n}$
が分かり, $n < l$ に対して,
$\begin{array}{r} \sum_{i = 0}^{k^{l} - 1} ε (l, i) (x + i)^{n} = 0 \end{array}$
が分かる.これを合わせると,
$\begin{aligned} a_{n} & = \sum_{i = 0}^{k^{n} - 1} ε (n, i) (x + i)^{n} \\ = \sum_{i = 0}^{k^{n} - 1} ε (n, i) i^{n} \\ = \sum_{i = 0}^{k^{n - 1} - 1} \sum_{j = 0}^{k - 1} (- 1)^{j + 1} ε (n - 1, i) (j k^{n - 1} + i)^{n} \\ = \sum_{i = 0}^{k^{n - 1} - 1} \sum_{j = 0}^{k - 1} \sum_{l = 0}^{n} (- 1)^{j + 1} ε (n - 1, i) (\binom{n}{l}) i^{l} j^{n - l} k^{(n - 1) (n - l)} \\ = \sum_{l = 0}^{n} (\binom{n}{l}) k^{(n - 1) (n - l)} \sum_{j = 0}^{k - 1} (- 1)^{j + 1} j^{n - l} \sum_{i = 0}^{k^{n - 1} - 1} ε (n - 1, i) i^{l} \\ = \sum_{j = 0}^{k - 1} (- 1)^{j + 1} \sum_{i = 0}^{k^{n - 1} - 1} ε (n - 1, i) i^{n} + n k^{n - 1} a_{n - 1} \sum_{j = 0}^{k - 1} (- 1)^{j + 1} j \\ = n k^{n} 2^{- 1} a_{n - 1} (n > 0) \end{aligned}$
が分かるので, $a_{0} = 1$ に注意すると, $a_{n} = k^{\frac{1}{2} n (n + 1)} 2^{- n} n! (n ⩾ 0)$ を得る.