Let us define a $\textit{triangle equivalence}$ a group of numbers that can be arranged as shown $a+b=c$ $d+e+f=g+h$ $i+j+k+l=m+n+o$ and so on... Where at the $j$-th row, the left hand side has $j+1$ terms and the right hand side has $j$ terms. Now, we are given the first $N^2$ positive integers, where $N$ is a positive integer. Suppose we eliminate any one number that has the same parity with $N$. Prove that the remaining $N^2-1$ numbers can be formed into a $\textit{triangle equivalence}$. For example, if $10$ is eliminated from the first $16$ numbers, the remaining numbers can be arranged into a $\textit{triangle equivalence}$ as shown. $1+3=4$ $2+5+8=6+9$ $7+11+12+14=13+15+16$
Problem
Source: INAMO 2019 P4
Tags: algebra
03.07.2019 15:01
Let's call a set gabut if it is of the form $\{x,x+1\}$ where $x \in \mathbb{Z}$, and call a number supergabut if it is the smaller member of a gabut set and gabutbanget if it is the larger member of the set. PART 1:$ N \leq X$ Notice that if we 'split' $\{N,N+1,N+2,...,N^{2}\}-\{X\}$ into $\frac{N^{2}-N-2}{2}$ gabut pairs(this can always be done since the parity of $N$ and $X$ is the same) then we can create a triangle equivalence by combining each member $M$ of the set $\{1,2,3,...,N-1\}$ with M supergabut numbers, where their sum will be equal to the sum of the gabutbanget correspondence of the supergabut numbers. PART 2: $ X \leq N$ Induction from N to N+2 by comrade @valentinodante
03.07.2019 15:27
Straight-up induction works; Divide the problem into 2 cases, even and odd. The base case for each part, $N=2$ and $N=3$ can be verified easily by hand. For the induction step from $N$ to $N+2$, note that the set $\{N^2+1,N^2+2,..., N^2+4N+4\}$ satisfies the equation: $(N^2+1) + (N^2+2) + ... + (N^2+N+1) = (N^2 +N+2) + ... + (N^2 + 2N) + (N^2+2N+2)$ $(N^2+2N+1) + (N^2+2N+3) + ... + (N^2+3N+3) = (N^2 +3N+4) + ... + (N^2 + 4N+3) + (N^2+4N+4)$ Now if the removed integer is less than $N^2$, we are done by the induction, with the above two equations occupying the last 2 lines in the triangle equivalence. For the rest, the idea is to make the last two equations "work" by changing the deleted term into $N^2$ and exchanging the positions of the terms inside.
07.07.2019 18:27
This is actually ez
15.07.2023 15:58
I'll provide a more detailed solution as well (may differ from the solutions above) First, consider eliminating $N^2$, then we can consider the following construction: \begin{align*} 1+2 &= 3\\ 4+5+6 &= 7+8 \\ &\vdots \\ n^2+(n^2+1)+...+(n^2+n) &= (n^2+n+1)+(n^2+n+2)+...+((n+1)^2-1) \end{align*}Proof: $n^2+(n^2+1)+...+(n^2+n)=\frac12(n^2+n)(n^2+n+1)-\frac12(n^2-1)(n^2)=\frac12(2n^3+3n^2+n)$ $(n^2+n+1)+(n^2+n+2)+...+(n^2+2n)=\frac12(n^2+2n)(n^2+2n+1)-\frac12(n^2+n)(n^2+n+1)=\frac12(2n^3+3n^2+n)$ Well, that may not always be the case. If the number eliminated is not $N^2$, but some number $N^2-2k (k\geq 1)$, then consider the following strategy: For the construction that $N^2$ is eliminated, for numbers $N^2-2k$, $N^2-2k+1$, ..., $N^2-1$, we increase by $1$. Then we notice that the row $N^2-2k$ is in, say row $C$ , the sum on the left is $D$ less than the sum on the right, where $D\leq C$. Notice that there are $N-1$ rows as well. Case 1: $(N-1)-C$ is odd. We have $(N-1)-C-1$ rows with all its numbers increased by $1$, and the $C$'th row has even number of numbers increased by $1$. For every pair of consecutive rows, pick the rightmost number from the upper row, and the leftmost number from the lower row, swap them. Call this operation (1). Then, for the $C$'th row, the left sum is $D+1$ less than the right sum. So, pick two numbers, such that their absolute difference is $\frac{D+1}{2}$ and they are on different sides of the equation. Case 2: $(N-1)-C$ is even. Perform (1) on the lower $(N-1)-C-1$ rows, then for the $C$'th row, pick two numbers, such that their absolute difference is $\frac{D}{2}$ and they are on different sides of the equation. Note, if the number eliminated is $3$, we should consider the following construction for the first two rows: \begin{align*} 1+4 &=5\\ 2+6+8 &= 7+9 \end{align*} Hence proved.