Triangular equations

A triangular series of equations is a system of $k$ equations where the $k$-th row consists of $k+1$ terms on the LHS and $k$ terms on the RHS. For example: $$a + b = c$$ $$d + e + f = g + h$$ $$i + j + k + l + m = n + o + p$$ $$...$$ Given the numbers $1, 2, \dots, n^2$ and one number with the same parity as $n$ is removed, prove that the rest of the numbers can be arranged into a triangular series of equations.

For example, out of $1,2,\dots,9$, 3 is removed, so the rest can be written as:

$$1+4 = 5$$ $$2 + 6 + 8 = 7 + 9$$ Another example, out of $1,2,\dots, 16$, 10 is removed, so the rest can be written as: $$1+3 = 4$$ $$2 + 5 + 8 = 6 + 9$$ $$7 + 11 + 12 + 14 = 13 + 15 + 16$$

Solution (In Progress)

Suppose we color all the numbers with the same parity as $n$ with red, and color all the numbers with the opposite parity with black. Also, call the number that was removed, the missing number, $x$. A number is called "good" if, when missing, the rest of the numbers can be written as triangular system.

Note the triangular system below:

$$1+2 = 3$$ $$4+5+6 = 7+8$$ $$9+10+11+12 = 13+14+15$$ $$...$$ $$k^2 + \dots + (k^2+k) = (k^2+k+1) + \dots + (k^2+2k)$$ $$...$$ $$(n-1)^2 + \dots + ((n-1)^2+n-1) = ((n-1)^2+(n-1)+1) + \dots + (n^2-1)$$ We call this system A. This system is missing $n^2$, and the system is triangular and correct. (The correctness of said system can be verified by simple arithmetic series on the $k$-th row).

So we know that $n^2$ is good. Furthermore, note that each row has the same number of odd numbers (that is, $k$-th row has $k$ odd numbers if $k$ is odd and $k-1$ odd numbers if $k$ is even). So if we increase each odd number by two, we'll still get a correct triangular system:

$$3+2 = 5$$ $$4+7+6 = 9+8$$ $$11+10+13+12 = 15+14+17$$ $$...$$ So if $n$ is odd, 1 is good. Call this system B.

Similarly, the $k$-th row has $k$ even numbers in the LHS and $k-1$ even numbers in the RHS. We can increase the even numbers by two, but then the equation will be incorrect. Call the "weight" of an equation to be its RHS - LHS. Obviously, an equation is correct only if it has weight zero. If we increase all the even numbers by two, then the weight of the new equation is -2, for example:

$$6+5+8 > 7+10,w=-2$$ But note that now $(k^2+k+2)$ is in the LHS while $k^2+k+1$ is still in the RHS. In other words, the largest number in the LHS is exactly one more than the smallest number in the RHS, so if we switch those two, we restore the weight back to zero: $$6+5+7 = 8+10$$ So we can form a new system this way: $$1+3=4$$ $$6+5+7 = 8+10$$ $$9+12+11+13 = 14+16+15$$ $$...$$ Next, note that out of the $n$ rows in the equation, we can take the first $k$ rows from system A, and the $n-k$ last rows from system B or C. For example: $$1+2 = 3$$ $$4+5+6 = 7+8$$ $$11+10+13+12 = 15+14+17$$ $$...$$ Now we are ready to prove the main assertion by induction. We will show the base cases later. For now, suppose it holds for $n=2,3$. Then, if $x \leq (n-2)^2$, there is a way to arrange $\{1, 2, \dots, (n-2)^2\} \ \{x\}$ in triangular form by induction hypothesis, and the last two rows can be taken from the last two rows of system B (if $n$ is even) or system C (if $n$ is odd). So then we consider cases where the missing number is $x > (n-2)^2$. In system A above, it would be in the last two rows. We will divide into cases depending on the position of $x$ in system A. Note that the missing number is always red.

Suppose $x$ is red on the last row RHS (meaning the missing number is in the interval $x \ in [(n-1)^2+(n-1)+1, n^2-2]$). Take out that number and replace it with $n^2$. Then now the last row has weight a positive even number in the interval $[2, n-1]$. We can switch a number $k$ from LHS and $l$ from the RHS, and the weight would decrease by $2(l-k)$. But the difference of the numbers in RHS and LHS ranges from 1 to $2n-2 > n-2$, and each side has consecutive numbers. So we know there are numbers that we can pick to switch so that the weight is reduced back to zero.

Suppose the missing number is red on the last row LHS, meaning the missing number is in the interval $x \in [(n-1)^2+1, (n-1)^2+(n-1)]$. Take out that number and replace it with $n^2$. Then the last row has weight a negative even number in the interval $[-2n+2, -n]$. Now, there exists a number in RHS $y$ such that $y-n^2$ is exactly half the weight of the last row, because the numbers in RHS is in the range $[(n-1)^2+(n-1)+1,n^2-1]$ so those numbers subtracted by $n^2$ is in the range $[-n+1, -1]$ which encompasses $\frac{1}{2} [-2n+2, -n]$. If we switch this number $y$ and $n^2$, the weight of the last row is restored.

Suppose the missing number is red on the second-to-last (STL) row LHS, meaning the missing number is in the interval $x \in [(n-2)^2, (n-2)^2+(n-2)]$. Take out that number and replace it with $(n-1)^2+1$, and then in the last row, put $n^2$ to where $(n-1)^2+1$ used to be. The STL row now has weight negative even number in the interval $[-2n+2,-n]$, whereas last row has some other even number weight. The last row could be fixed with the procedure described above (as if $(n-1)^2+1$ was the missing number). However the STL row can be fixed by switching $(n-1)^2+1$ with an appropriate number in the STL RHS, because the numbers in STL RHS ranges from $[n^2-3n+3,n^2-2n]$ so the difference ranges from $[-n+1, -2]$ which encompasses $\frac{1}{2}[-2n+2,-n]$

Suppose the missing number is red on the STL row RHS. Same as before, take out that number, replace it with $(n-1)^2+1$, and then in the last row, put $n^2$ to where it used to be. Same as above, the last row can be fixed using the previous strategy, whereas the STL row can be fixed by switching two numbers in the STL (similar to if the missing number is from RHS last row).

Now all that remains is to prove the base cases. For $n=2$, we have either $1+3=4$ or $1+2=3$. For $n=3$, the missing numbers could be $x=1,3,5,7,9$, but $x=9$ is already covered by system A above, $x=1$ covered by system B, and $x=3$ is shown in the example. For $x=5$:

$$1+2=3$$ $$4+7+6 = 9+8$$ For $x=7$: $$1+3=4$$ $$2+5+8 = 6+9$$ (Really we're just applying the algorithm described above but we're including here for the sake of proof completeness).