INAMO 2019 P4 - Triangle equivalence

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

INAMO 2019 P4 - Triangle equivalence

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: INAMO 2019 P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ImbecileMathImbaTation

106 posts

ImbecileMathImbaTation

#1 h Jul 3, 2019, 8:19 AM • 1 Y

Y by Adventure10

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$

This post has been edited 5 times. Last edited by ImbecileMathImbaTation, Jul 3, 2019, 10:25 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10 posts

#2 h Jul 3, 2019, 12:01 PM • 3 Y

Y by valentinodante, ImbecileMathImbaTation, Adventure10

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

This post has been edited 3 times. Last edited by ayamgabut, Jul 3, 2019, 12:29 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

27 posts

#3 h Jul 3, 2019, 12:27 PM • 4 Y

Y by ayamgabut, ImbecileMathImbaTation, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RevolveWithMe101

482 posts

RevolveWithMe101

#4 h Jul 7, 2019, 3:27 PM • 3 Y

Y by ImbecileMathImbaTation, Adventure10, Mango247

This is actually ez

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

28 posts

#5 h Jul 15, 2023, 12:58 PM

Y by

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.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a