Problems from Ukrainian Authors

Let $n=k{m}^{d+1}$. We will construct the desired splitting in the following way. To determine which of the subsets each number $x\in \{1;2;\dots n\}$ belongs to, let us write $x-1$ in the form: $$x-1=c{m}^{d+1}+x_0+x_{1}m+x_2{m}^2+\cdots +x_d{m}^d,$$ where $c\ge 0$ is an integer, $x_i\in \{0;1;\dots m-1\}$, $i=0,\dots ,d$, i.e. we write the remainder of $x-1$ divided by $m^{d+1}$ in base $m$ numeral system. We include the number $x$ to subset $A_j$, $j\in \{1;2;\dots m\}$ if $x_0+x_1+x_2+\cdots +x_d\equiv j(\mathrm{mod}m)$. Let us show that such splitting satisfies the condition. Clearly, it is enough to prove our statement for polynomials of the form $P(x)=x^t$, $t=0,\dots ,d$.

We have $$S(A_j)=\sum _{c=0}^{k-1}\sum _j(c{m}^{d+1}+x_0+x_{1}m+x_2{m}^2+\cdots +x_d{m}^d{)}^t,$$ where ${\sum }_j$ denotes the sum over all tuples $x_0,\dots ,x_d$ of numbers from the set $\{0;1;\dots m-1\}$ such that $x_0+x_1+x_2+\cdots +x_d\equiv j(\mathrm{mod}m)$. Let us show that the inner sum does not depend on $j$. Denoting $z=1+c{m}^{d+1}$, we can transform it by expanding the brackets: $$\sum _j(c{m}^{d+1}+x_0+x_{1}m+x_2{m}^2+\cdots +x_d{m}^d{)}^t=\sum _d\frac{t!}{u!t_0!t_1!\dots t_d!}{z}^u{m}^{t_1+2t_2+\cdots +d{t}_d}\sum _j{x}_0^{t_0}{x}_1^{t_1}\dots x_d^{t_d},$$ where ${\sum }_d$ denotes the sum over all tuples of non-negative integers $u,t_0,\dots ,t_d$ such that $u+t_0+\cdots +t_d=t$. Since $t_0+\cdots +t_d\le t<d+1$, there is at least one number among $t_0,\dots ,t_d$ which equals zero. Suppose that $t_0=0$, then $$\sum _j{x}_0^{t_0}{x}_1^{t_1}\dots x_d^{t_d}=\sum _j{x}_1^{t_1}\dots x_d^{t_d}=\sum _{x_1,\dots ,x_d=0}^{m-1}{x}_1^{t_1}\dots x_d^{t_d},$$ because for any tuple $x_1,\dots ,x_d$ of numbers from $\{0;1;\dots m-1\}$ there is a unique number $x_0\in \{0;1;\dots m-1\}$ for which $x_0+x_1+x_2+\cdots +x_d\equiv j(\mathrm{mod}m)$. The last sum is clearly independent of $j$, which is what we wanted to prove.