Problem: Let $A = \{a_1, \dots, a_{2024}\}$ be a set of $2024$ pairwise distinct real numbers.
Assume that there exist positive integers $b_1, b_2,\dotsc,b_{2024}$
such that \[ a_1b_1 + a_2b_2 + \dots + a_{2024}b_{2024} = 0. \]
Prove that one can choose $a_{2025}, a_{2026}, a_{2027}, \dots$ such that
$a_k \in A$ for all $k \ge 2025$ and, for every positive integer $d$,
there exist infinitely many positive integers $n$ satisfying
\[ \sum_{k=1}^n a_k k^d = 0. \]

Solution: It will be convenient to use $0$-based indexing here,
i.e.\ $A = \{a_0, \dotsc, a_{2023}\}$ and so on.
Let $m = \sum_{i=0}^{2023} b_i$.
By appending $b_i-1$ copies of $a_i$ for each $i$,
we may extend the sequence to $a_0, \dotsc, a_{m-1}$ such that $a_0+\dotsb+a_{m-1} = 0$.

\paragraph{Solution by direct construction.}
Let $s_m(n)$ be the sum of the base-$m$ digits of $n$, reduced modulo $m$.
We now claim that $a_k = a_{s_m(k)}$ works.
It is clear that this extends the original sequence in a valid way.
\begin{claim*}
  Fix $d$.
  Then the sum
  \[\sum_{k=0}^{n-1}a_k(k+1)^d\]
  is zero when $n = cm^{d+1}$ for any positive integer $c$.
\end{claim*}
If we prove this, then the problem is solved as there are infinitely many possible $c$.
We have two proofs of this.

\begin{proof}[Proof of claim by expansion (Andrew Gu)]
  We only need to show that each block of $m^{d+1}$ terms sums to zero. Each
  block takes the form
  \[ S = \sum_{k=cm^{d+1}}^{(c+1)m^{d+1}-1}a_{s_m(k)}(k+1)^d. \]
  We group terms based on the value of $s_m(k)$.
  The values of $k$ in this sum are given by
  \[\left\{ cm^{d+1}+\sum_{i=0}^{d}e_im^i
      \mid (e_0, \dotsc, e_d) \in \{0, \dotsc, m-1\}^{d+1}\right\}.\]
  In this form, the sum of the base-$m$ digits is $s_m(c)+e_0+\dotsb+e_d$.
  Therefore we can write
  \[ S = \sum_{i=0}^{m-1}a_i
    \underbrace{\Bigg(\sum_{
          \substack{(e_0, \dotsc, e_d) \in \{0, \dotsc, m-1\}^{d+1} \\
        e_0+\dots+e_d\equiv i-s_m(c)\pmod{m}}}
    \underbrace{\Big(cm^{d+1}+1+\sum_{j=0}^{d}e_jm^j\Big)^d}_{(2)}\Bigg)}_{(1)}. \]
  Since $\sum a_i=0$, it suffices to show that the value of the coefficient
  given by (1) is independent of $i$.

  Expand the term (2) with the multinomial theorem.
  Each monomial in the expansion is a product of terms $c$, $m$, $e_j$.
  Since the exponent is $d$, no monomial is divisible by the whole product $e_0e_1\dotsm e_d$.
  Since the tuples $(e_0, \dotsc, e_d)$ are uniformly distributed
  over all possible tuples when one or more coordinates are removed,
  that means that the sum of each monomial term is independent of $i$.
  We conclude that the sum (1) is independent of $i$ as well.
\end{proof}

\begin{proof}[Proof of claim by Fourier transform]
  Let $\omega \neq 1$ be an $m$\ts{th} root of unity.
  Then, define the operator
  \[\Delta^{(\omega)}_a f(x) = \sum_{i=0}^{m-1} \omega^i f(x + ia).\]
  By looking at the leading coefficients, one can see that $\Delta^{(\omega)}_a$
  lowers the degree of a polynomial by at least $1$.\footnote{In fact the degree
  decreases by exactly $1$, but this is not that important.}
  As a consequence, by letting $f(x) = (x+1)^d$ we conclude that
  \[ \sum_{k \in [0, m_e)} \omega^{s_m(k)} (k+1)^d
    = (\Delta^{(\omega)}_{m^{e-1}} \dotsb \Delta^{(\omega)}_{m} \Delta^{(\omega)}_{1} f)(0) = 0.\]
  Since $a_1 + \dotsb + a_m = 0$, by a discrete Fourier transform we may write
  $a_i = \sum_{j=1}^{m-1} c_j e^{2\pi ij/m}$ for some
  $c_1, \dots, c_{m-1} \in \CC$.
  Therefore
  \[ \sum_{k=0}^{m^e-1} a_k (k+1)^d
    = \sum_{j=1}^{m-1} c_j \sum_{k=0}^{m^e-1} (e^{2\pi ij/m})^{s_m(k)} (k+1)^d
    = 0. \qedhere \]
\end{proof}

\paragraph{Inductive solution.}
Define $m$ and extend the sequence to $a_{m-1}$ as before.
For $d \geq 0$, let $\Sigma_d(S)$ denote $\sum_{k \in S} k^d$.
Also, for $d \geq 0$ call a tuple of sets $(S_0,\dotsc,S_{m-1})$
to be \emph{$d$-uniform} if for all $0 \leq d' \leq d$
we have $\Sigma_{d'}(S_0) = \Sigma_{d'}(S_1) = \dots = \Sigma_{d'}(S_{m-1})$.

\begin{lemma}
  \label{lemma:fix}
  Suppose $(S_0,\dotsc,S_{m-1})$ is $d$-uniform.
  Then for all $0 \leq d' \leq d+1$, $x \in \RR$, and $0 \leq i, j < m$,
  the quantity $\Sigma_{d'}(S_i+x) - \Sigma_{d'}(S_j + x)$ is independent of $x$.
\end{lemma}
\begin{proof}
  We may expand
  \[\Sigma_{d'}(S_i + x) = \sum_{k=0}^{d'} \binom{d'}{k} x^{d'-k} \Sigma_k(S_i).\]
  By $d$-uniformity, the terms with $k\leq d$ are independent of $i$ and go away
  in the subtraction. The only term left is when $k = d' = d+1$. However, this
  term is independent of $x$, as desired.
\end{proof}

\begin{lemma}
  \label{lemma:induct}
  Suppose $(S_0,\dotsc,S_{m-1})$ is a $d$-uniform partition of $[0, n)$.
  Then there exists a $(d+1)$-uniform partition $(S'_0,\dotsc,S'_{m-1})$ of $[0, mn)$
  such that $S_i \subseteq S'_i$ for all $i$.
\end{lemma}
\begin{proof}
  We let $S'_i = \bigcup_{k=0}^{m-1} (S_{(i+k) \bmod m} + kn)$.
  Then, for every $0 \leq d' \leq d+1$ and $0 \leq i,j < m$, we have
  \begin{align*}
    \Sigma_{d'}(S'_i) - \Sigma_{d'}(S'_j)
    &= \sum_{k=0}^{m-1}\Sigma_{d'}(S_{(i+k) \bmod m}+ kn) - \Sigma_{d'}(S_{(j+k) \bmod m} + kn) \\
    &= \sum_{k=0}^{m-1}\Sigma_{d'}(S_{(i+k) \bmod m}) - \Sigma_{d'}(S_{(j+k) \bmod m}) \\
    &= 0. \qedhere
  \end{align*}
\end{proof}
Consider the $0$-uniform partition of $[0, m)$ given by $(\{0\}, \{1\}, \dotsc, \{m-1\})$.
By repeatedly applying \Cref{lemma:induct},
we get $d$-uniform partitions $(S^{(d)}_0, \dotsc, S^{(d)}_{m-1})$ of $[0, m^{d+1})$
such that $S^{(d)}_i \subseteq S^{(d+1)}_i$ for all $d$ and $i$.
For every $k$, let $i$ be the unique index such that $k \in S^{(d)}_i$ for some $d$,
and let $a_k = a_i$.
(This doesn't redefine $a_0$, \dots, $a_{m-1}$ as for $k < m$, we have $k \in S^{(0)}_k$.)
Then, for each $e \geq d$, we find that
\[ \sum_{k=0}^{m^{e+1}-1} a_k (k+1)^d = \sum_{i=0}^{m-1} a_i \sum_{k \in S^{(e)}_i} (k+1)^d
  = \sum_{i=0}^{m-1} a_i \sum_{j=1}^d \binom{d}{j} \Sigma_j(S^{(e)}_i) = 0. \]

\begin{remark*}
  The construction here is essentially the same as the sum-of-digits construction
  (in fact it would be exactly the same if we replace $(i+k) \bmod m$ in the proof
  of \Cref{lemma:induct} with $(i-k) \bmod m$).
  However, it hints at some flexibility in the construction which is less apparent with other approaches.
  For example, if $G$ is any transitive subgroup of permutations on $[0, m)$ and
  $\pi_0 = \id$, $\pi_1$, \dots, $\pi_{\abs{G}-1}$ is an enumeration of the elements of $G$,
  one can turn a $d$-uniform partition $(S_0,\dotsc,S_{m-1})$ of $[0, n)$
  into a $(d+1)$-uniform partition $(S'_0,\dotsc,S'_{m-1})$ of $[0, \abs{G}n)$ by
  letting $S'_i = \bigcup_{k=0}^{\abs{G}-1} (S_{\pi_k(i)} + kn)$.
  Here we used the special case $\pi_k(i) = (i+k) \bmod m$;
  it may also be natural to let $G$ be the set of all $m!$ permutations.
\end{remark*}

\begin{remark*}
  The construction in the solution has appeared a number of times in the literature; see
  \begin{itemize}
    \frenchspacing
    \ii D. H. Lehmer, The Tarry-Escott problem, \emph{Scripta Math.} \textbf{13}, 37--41, 1947;
    \ii E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres,
      \emph{C. R. Acad. Sci. Paris} \textbf{33}, 225, 1851;
    \ii E. M. Wright, \href{https://doi.org/10.1017/S0013091500002698}{Equal sums of like powers},
      \emph{Proc. Edinburgh Math. Soc.} 2nd series \textbf{8}, 138--142, 1949;
    \ii E. M. Wright, \href{https://doi.org/10.2307/2309513}{Prouhet's 1851 solution of the Tarry-Escott problem of 1910},
      \emph{Amer. Math. Monthly} \textbf{66}, 199--201, 1959.
    \nonfrenchspacing
  \end{itemize}
\end{remark*}