Let $m$ be a positive integer satisfying $\dfrac{m(m+1)}{4}\in \mathbb{Z}$. Show that there exists a positive integer $t$ and $t$ positive integers $m_1,m_2,\cdots,m_t$ such that $$\begin{cases} \sum\limits_{k=1}^{t}m_k=m\\ \sum\limits_{k=1}^{t}\dfrac{m_k(m_k+1)}{2}=\dfrac{m(m+1)}{4} \end{cases}.$$ P.S. This question comes from Problem F in The 2022 ICPC Asia Shenyang Regional Contest (https://codeforces.com/gym/104160/problem/F). One of the key steps in this problem is to find a set of solutions to the above indeterminate equations. And I noticed that $\dfrac{m(m+1)}{4}$ cannot be arbitrarily replaced by other positive integers, which may make the proposition no longer true.

$\begingroup$ What do you mean by saying "cannot be replaced bu other positive integers"? It can surely be replaced, say, with $m$ yielding a solution $t=m$ and $m_k=1$ for all $k$. $\endgroup$– Max AlekseyevCommented Apr 14, 2023 at 13:50

$\begingroup$ @MaxAlekseyev Sorry, what I originally meant to express is that it cannot be arbitrarily replaced by other positive integers. $\endgroup$– John_zyjCommented Apr 14, 2023 at 15:24

1$\begingroup$ I found that this Sage code seems to always find a set of solutions for small $m$. The general idea of this algorithm is to select $m_k$ as large as possible in each iteration. Can anyone prove the correctness of this algorithm? Thanks! $\endgroup$– John_zyjCommented Apr 14, 2023 at 16:55

1$\begingroup$ @GHfromMO: Yes, see my answer where I prove that the greedy algorithm always produces a solution. $\endgroup$– Max AlekseyevCommented Apr 15, 2023 at 19:22

1$\begingroup$ @GHfromMO: Good point! I've updated the answer to make clear its contribution. $\endgroup$– Max AlekseyevCommented Apr 15, 2023 at 19:29
2 Answers
In the comments OP proposed a greedy algorithm to represent a given positive integer $A$ as the sum of triangular numbers whose indices sum to $m$, and applied it to $A = \frac{m(m+1)}4$. I will prove that it indeed always produces a solution, and thus the given system is soluble for any positive integer $m$ with $\frac{m(m+1)}4\in\mathbb Z$.
Essentially, the algorithm goes from a pair $(m,A)$ with $m\leq A$ to the pair $(mt,A\tfrac{t(t+1)}2)$ for the largest integer $t$ such that $mt \leq A\tfrac{t(t+1)}2$, or equivalently $$(\star)\qquad \frac{t(t1)}2\leq Am < \frac{t(t+1)}2.$$ The value for $t$ can be given explicitly as $t = \left\lfloor\tfrac{1 + \sqrt{8(Am)+1}}2\right\rfloor.$ Notice that $t\geq 1$, and furthermore $t\geq 2$ as soon as $m<A$.
The algorithm converges and produces a solution when/if it reaches the pair $(0,0)$. Let's start with the following claim.
Claim. The greedy algorithm converges for any given pair of integers $(m,A)$ satisfying $0\leq m\leq A \leq \frac{(m1)^2}4$.
Proof. Proof is done by induction on $m$. In the base cases $m< 43$ the claim is verified computationally. Let's prove the claim for $m\geq 43$, assuming that it's proved for all smaller values of $m$.
The algorithm from the given pair $(m,A)$ goes to the pair $(m',A')$ where $m':=mt$ and $A':=A\frac{t(t+1)}2$ with $t\geq 1$ defined by the formula above. Clearly, $m'<m$. Hence, for the induction assumption to work it remains to verify that $0\leq m'\leq A'\leq \frac{(m'1)^2}4$.
It can be seen that inequality $0\leq m'$ (ie. $t\leq m$) follows from the inequality $A \leq \frac{(m1)^2}4$ coupled with $(\star)$. The inequality $m'\leq A'$ follows from the definition of $t$.
Finally, the inequality $A' \leq \frac{(m'1)^2}4$, given that $(\star)$ implies $A'<m$, would follow from $m \leq \frac{(mt1)^2}4$, for which we need $t \leq m12\sqrt{m}$. Since $A\leq \frac{(m1)^2}4$, from the explicit formula for $t$, we have $$t\leq \frac{1 + \sqrt{2(m^26m+1)+1}}2<\frac{1+\sqrt{2}(m3)}2\leq m12\sqrt{m},$$ where the last inequality holds since $m\geq 43$. QED
While Claim is not directly applicable to $A = \frac{m(m+1)}4$, we show that for $m\geq 50$ after one iteration the pair $(m',A'):=(mt,A\frac{t(t+1)}2)$ does satisfy the condition of Claim. Similarly to the above, it's enough to show that $t \leq m12\sqrt{m}$. Here the explicit formula for $t$ implies $$t\leq \frac{1 + \sqrt{2(m^23m)+1}}2<\frac{1+\sqrt{2}(m1.5)}2\leq m12\sqrt{m},$$ where the last inequality holds for $m\geq 50$. Hence, our Claim implies that the algorithm converges on the input $(m,\frac{m(m+1)}4)$ for all $m\geq 50$. For $m<50$, the algorithm convergence on the input $(m,\frac{m(m+1)}4)$ is verified computationally.
I expect that in many cases the following construction will do the job. By Fermat polygonal number theorem, we have representation of $\frac{m(m3)}4$ as the sum of 3 triangular numbers: $$ \frac{m(m3)}4 = \frac{m_1(m_11)}2 + \frac{m_2(m_21)}2 + \frac{m_3(m_31)}2$$ and if additionally we can have $m_1+m_2+m_3\leq m$, we set $t:=m(m_1+m_2+m_3)+3$ and $m_k:=1$ for $k\in\{4,5,\dots,t\}$ to get a solution.
Here is an online Sage code that implements this approach. Relying on just one (somewhat arbitrary) representation produced by sum_of_k_squares(3,x)
it solves the problem for all 50 suitable values of $m$ below $100$, except $m=60$. Moreover, I was not able to find any other exceptional integers in the range $m\leq 10^5$, and so it may be the only exception to the above approach overall. Still, the problem for $m=60$ can be solved similarly via considering representations as the sum of 4 triangular numbers.

$\begingroup$ Thank you very much for your answer! I found that this Sage code seems to always find a set of solutions for small $m$. The general idea of this algorithm is to select $m_k$ as large as possible in each iteration. Can anyone prove the correctness of this algorithm? Thanks! $\endgroup$– John_zyjCommented Apr 14, 2023 at 16:52

$\begingroup$ Your comment is irrelevant to my answer. You describe a greedy algorithm. $\endgroup$ Commented Apr 14, 2023 at 17:35

$\begingroup$ Yes, I understand. I just said that I found another possible way to construct the solution. $\endgroup$– John_zyjCommented Apr 14, 2023 at 17:53