# The existence of solutions of a system of indeterminate equations

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.

• 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$. Commented Apr 14, 2023 at 13:50
• @MaxAlekseyev Sorry, what I originally meant to express is that it cannot be arbitrarily replaced by other positive integers. Commented Apr 14, 2023 at 15:24
• 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! Commented Apr 14, 2023 at 16:55
• @GHfromMO: Yes, see my answer where I prove that the greedy algorithm always produces a solution. Commented Apr 15, 2023 at 19:22
• @GHfromMO: Good point! I've updated the answer to make clear its contribution. Commented Apr 15, 2023 at 19:29

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.

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'. 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', 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.

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.

• 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! Commented Apr 14, 2023 at 16:52
• Your comment is irrelevant to my answer. You describe a greedy algorithm. Commented Apr 14, 2023 at 17:35
• Yes, I understand. I just said that I found another possible way to construct the solution. Commented Apr 14, 2023 at 17:53