The existence of solutions of a system of indeterminate equations

Question

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.

Answer 1

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 $(m-t,A-\tfrac{t(t+1)}2)$ for the largest integer $t$ such that $m-t \leq A-\tfrac{t(t+1)}2$, or equivalently $$(\star)\qquad \frac{t(t-1)}2\leq A-m < \frac{t(t+1)}2.$$ The value for $t$ can be given explicitly as $t = \left\lfloor\tfrac{1 + \sqrt{8(A-m)+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{(m-1)^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':=m-t$ 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{(m-1)^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{(m-t-1)^2}4$, for which we need $t \leq m-1-2\sqrt{m}$. Since $A\leq \frac{(m-1)^2}4$, from the explicit formula for $t$, we have $$t\leq \frac{1 + \sqrt{2(m^2-6m+1)+1}}2<\frac{1+\sqrt{2}(m-3)}2\leq m-1-2\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'):=(m-t,A-\frac{t(t+1)}2)$ does satisfy the condition of Claim. Similarly to the above, it's enough to show that $t \leq m-1-2\sqrt{m}$. Here the explicit formula for $t$ implies $$t\leq \frac{1 + \sqrt{2(m^2-3m)+1}}2<\frac{1+\sqrt{2}(m-1.5)}2\leq m-1-2\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.

Answer 2

I expect that in many cases the following construction will do the job. By Fermat polygonal number theorem, we have representation of $\frac{m(m-3)}4$ as the sum of 3 triangular numbers: $$ \frac{m(m-3)}4 = \frac{m_1(m_1-1)}2 + \frac{m_2(m_2-1)}2 + \frac{m_3(m_3-1)}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.