Разделы 
Дополнительно
Задача по математике - 3664
2019-06-15 
Все натуральные числа, в десятичной записи которых не больше $n$ цифр, разбиты на две группы. В первую группу входят все числа с нечетной суммой цифр, во вторую - с четной суммой цифр. Докажите, что если $1 \leq k < n$, то сумма $k$-x степеней всех чисел первой группы равна сумме $k$-x степеней всех чисел второй группы.
Решение:
Пусть $D_1$ - множество из 10 цифр $\{ 0, 1, 2, \cdots, 9 \}$; $A_1 = \{ 0, 2, \cdots, 8 \}$ - множество четных, $B_1 = \{ 1, 3, 9 \}$ - множество нечетных цифр. Вообще при любом $n$ обозначим через $D_n$ множество всех не более чем $n$-значных чисел, $A_n$ и $B_n$ - его подмножества из чисел с четной и нечетной суммой цифр $(D_n = A_n \cup B_n)$. Заметим, что $B_n$ и $A_n$ всего содержат, считая число из одних нулей, по $5 \cdot 10^{n-1}$ элементов. Сумму всех элементов $x$ множества $X$ будем коротко записывать: $\sum x$ по $x \in X$. Мы должны доказать, что $\sum a^k$ по $a \in A_n$ равна $\sum b^k$ по $b \in B_n$, эту сумму мы обозначим $S_n^{(k)}$.
При $n = 2, к = 1$ утверждение задачи сводится к очевидному равенству (где $а \in A_1, p \in A_1, b \in B_1, q \in B_1)$:
$\sum (10a + p) + \sum (10b + q) = \sum (10a + q) + \sum (10b + p)$;
обе части равны $5 (\sum 10d + \sum r)$) по всем $d_1 \in D_1, r \in D_1, S_2^(1) = 5 (10 + 1)(1 + 2 + \cdots + 9)$, так как каждая цифра $а, р, b, q$ входит в ту и другую сумму по 5 раз (а слева - в паре с пятью р и т, п.).
Дальнейшие выкладки проиллюстрируем сначала на примере $n = 3$. Найдем сумму по всем $a \in A_1$, $р \in A_2$, $b \in B_1$, $q \in B_2$ (ниже $d \in D_1$, $r \in D_2$):
$\sum (10a + p)^2 + \sum (10b + q)^2 = 50 \cdot 10^2 (\sum a^2 + \sum b^2) + 2 \cdot 10 (\sum {a \cdot p} + \sum {b \cdot q}) + 5 \sum p^2 + 5 \sum q^2 = 10^2 \sum d^2 + 2 \cdot p + \sum b \cdot q) + 5 \sum p^2 + 5 \sum q^2 = 10^2 \sum d^2 + 2 \cdot 10 (\sum a \cdot \sum p + \sum b \cdot \sum q) + 5 \sum r^2 = 5 \cdot 10^3 \sum d^2 + 20 \sum d S_2^(1) + 5 \sum r^2$.
Ясно, что точно так же преобразуется и сумма $\sum (10a + q)^2 + \sum (10b + p)^2$. Здесь мы использовали тождества
$(x + у)^2 = x^2 + 2xy + у^2$ и $\sum uv = \sum u \cdot \sum v$ (сумма по всем $u \in U, v \in V$).
Теперь докажем общее утверждение индукцией по $n$. При этом мы будем использовать формулы
$(x + y)^k = x^k + C_k^1 x^{k-1} y + C_k^2 x^{k-2} y + \cdots + C_k^{k-1} xy^{a-1} + y^k = x^k + \sum {C_k^j x^{k-j}} + y^k$.
(значения "биномиальных коэффициентов" $C_k^j, 1 \leq j \leq k - 1$, не играют роли в нашем рассуждении) и $\sum uv = \sum u \sum v$. Предположим, что для $n$-значных чисел и любого $1 \leq k < n$ нужное равенство доказано: $\sum p^j = \sum a^j = S_n^(j)$ (где $p \in A_n, q \in B_n$).
Преобразуем сумму $k$-x степеней чисел из $A_{n+1}, k < n + 1$ (ниже мы суммируем по $a \in A_1, p \in A_n, b \in B_1, q \in B_n, d \in D_1, r \in D_n, 1 \leq j \leq k - 1)$:
$\sum (10a + p)^k + \sum (10b + q)^k = 5 \cdot 10^{n-1} \cdot 10^k (\sum a^k + \sum b^k) + \sum {C_k^j \cdot 10^{k-j}} (\sum a^{k-j} p^j + \sum b^{k-j} q^j) + 5 (\sum p^k + \sum q^k) = 5 \cdot 10^{n+k-1} \sum d^k + \sum_j C_k^j \cdot 10^{k-j} S_k^(j) \sum d^{k-j} + 5 \sum r^k$.
Ясно, что сумма $k$-x степеней чисел из $B_{n+1}$ равна тому же выражению (нужно лишь поменять местами буквы $p$ и $q$).
Аналогичные тождества верны и в любой $d$-ичной системе счисления при четном $d$, например в двоичной, где для небольших $n$ его легко проверить непосредственно.
Все натуральные числа, в десятичной записи которых не больше $n$ цифр, разбиты на две группы. В первую группу входят все числа с нечетной суммой цифр, во вторую - с четной суммой цифр. Докажите, что если $1 \leq k < n$, то сумма $k$-x степеней всех чисел первой группы равна сумме $k$-x степеней всех чисел второй группы.
Решение:
Пусть $D_1$ - множество из 10 цифр $\{ 0, 1, 2, \cdots, 9 \}$; $A_1 = \{ 0, 2, \cdots, 8 \}$ - множество четных, $B_1 = \{ 1, 3, 9 \}$ - множество нечетных цифр. Вообще при любом $n$ обозначим через $D_n$ множество всех не более чем $n$-значных чисел, $A_n$ и $B_n$ - его подмножества из чисел с четной и нечетной суммой цифр $(D_n = A_n \cup B_n)$. Заметим, что $B_n$ и $A_n$ всего содержат, считая число из одних нулей, по $5 \cdot 10^{n-1}$ элементов. Сумму всех элементов $x$ множества $X$ будем коротко записывать: $\sum x$ по $x \in X$. Мы должны доказать, что $\sum a^k$ по $a \in A_n$ равна $\sum b^k$ по $b \in B_n$, эту сумму мы обозначим $S_n^{(k)}$.
При $n = 2, к = 1$ утверждение задачи сводится к очевидному равенству (где $а \in A_1, p \in A_1, b \in B_1, q \in B_1)$:
$\sum (10a + p) + \sum (10b + q) = \sum (10a + q) + \sum (10b + p)$;
обе части равны $5 (\sum 10d + \sum r)$) по всем $d_1 \in D_1, r \in D_1, S_2^(1) = 5 (10 + 1)(1 + 2 + \cdots + 9)$, так как каждая цифра $а, р, b, q$ входит в ту и другую сумму по 5 раз (а слева - в паре с пятью р и т, п.).
Дальнейшие выкладки проиллюстрируем сначала на примере $n = 3$. Найдем сумму по всем $a \in A_1$, $р \in A_2$, $b \in B_1$, $q \in B_2$ (ниже $d \in D_1$, $r \in D_2$):
$\sum (10a + p)^2 + \sum (10b + q)^2 = 50 \cdot 10^2 (\sum a^2 + \sum b^2) + 2 \cdot 10 (\sum {a \cdot p} + \sum {b \cdot q}) + 5 \sum p^2 + 5 \sum q^2 = 10^2 \sum d^2 + 2 \cdot p + \sum b \cdot q) + 5 \sum p^2 + 5 \sum q^2 = 10^2 \sum d^2 + 2 \cdot 10 (\sum a \cdot \sum p + \sum b \cdot \sum q) + 5 \sum r^2 = 5 \cdot 10^3 \sum d^2 + 20 \sum d S_2^(1) + 5 \sum r^2$.
Ясно, что точно так же преобразуется и сумма $\sum (10a + q)^2 + \sum (10b + p)^2$. Здесь мы использовали тождества
$(x + у)^2 = x^2 + 2xy + у^2$ и $\sum uv = \sum u \cdot \sum v$ (сумма по всем $u \in U, v \in V$).
Теперь докажем общее утверждение индукцией по $n$. При этом мы будем использовать формулы
$(x + y)^k = x^k + C_k^1 x^{k-1} y + C_k^2 x^{k-2} y + \cdots + C_k^{k-1} xy^{a-1} + y^k = x^k + \sum {C_k^j x^{k-j}} + y^k$.
(значения "биномиальных коэффициентов" $C_k^j, 1 \leq j \leq k - 1$, не играют роли в нашем рассуждении) и $\sum uv = \sum u \sum v$. Предположим, что для $n$-значных чисел и любого $1 \leq k < n$ нужное равенство доказано: $\sum p^j = \sum a^j = S_n^(j)$ (где $p \in A_n, q \in B_n$).
Преобразуем сумму $k$-x степеней чисел из $A_{n+1}, k < n + 1$ (ниже мы суммируем по $a \in A_1, p \in A_n, b \in B_1, q \in B_n, d \in D_1, r \in D_n, 1 \leq j \leq k - 1)$:
$\sum (10a + p)^k + \sum (10b + q)^k = 5 \cdot 10^{n-1} \cdot 10^k (\sum a^k + \sum b^k) + \sum {C_k^j \cdot 10^{k-j}} (\sum a^{k-j} p^j + \sum b^{k-j} q^j) + 5 (\sum p^k + \sum q^k) = 5 \cdot 10^{n+k-1} \sum d^k + \sum_j C_k^j \cdot 10^{k-j} S_k^(j) \sum d^{k-j} + 5 \sum r^k$.
Ясно, что сумма $k$-x степеней чисел из $B_{n+1}$ равна тому же выражению (нужно лишь поменять местами буквы $p$ и $q$).
Аналогичные тождества верны и в любой $d$-ичной системе счисления при четном $d$, например в двоичной, где для небольших $n$ его легко проверить непосредственно.
