$\text{Problem } 53$

Let $n$ be a positive integer and let $a_1 \le a_2 \le \dots \le a_n$ and $b_1 \le b_2 \le \dots \le b_n$ be two nondecreasing sequences of real numbers such that

$$ a_1 + \dots + a_i \le b_1 + \dots + b_i \text{ for every } i = 1, \dots, n$$

and

$$ a_1 + \dots + a_n = b_1 + \dots + b_n. $$

Suppose that for every real number $m$, the number of pairs $(i,j)$ with $a_i-a_j=m$ equals the numbers of pairs $(k,\ell)$ with $b_k-b_\ell = m$. Prove that $a_i = b_i$ for $i=1,\dots,n$.

## IMO Marathon

- Thanic Nur Samin
**Posts:**176**Joined:**Sun Dec 01, 2013 11:02 am

### Re: IMO Marathon

Solution to problem $53$:

Take the sum of all differences for both sequences, since each difference in one sequence must have a corresponding equal difference in the other, the quantity would be same. Multiply both sides with $(-1)$. Add $(n-1)(a_1 + \dots + a_n) = (n-1)(b_1 + \dots + b_n)$ to both sides and divide by 2. We then get :

\[(n-1)a_1+(n-2)a_2+\dots 2a_{n-2}+a_{n-1}=(n-1)b_1+(n-2)b_2+\dots 2b_{n-2}+b_{n-1}\]

However, the summing the following inequality while $i$ runs from $1$ to $n-1$:

\[a_1 + \dots + a_i \le b_1 + \dots + b_i\]

We get:

\[(n-1)a_1+(n-2)a_2+\dots 2a_{n-2}+a_{n-1}\le (n-1)b_1+(n-2)b_2+\dots 2b_{n-2}+b_{n-1}\]

Since the equality case occurs, the equality case must occur in all the inequalities. From this, the desired result follows.

Take the sum of all differences for both sequences, since each difference in one sequence must have a corresponding equal difference in the other, the quantity would be same. Multiply both sides with $(-1)$. Add $(n-1)(a_1 + \dots + a_n) = (n-1)(b_1 + \dots + b_n)$ to both sides and divide by 2. We then get :

\[(n-1)a_1+(n-2)a_2+\dots 2a_{n-2}+a_{n-1}=(n-1)b_1+(n-2)b_2+\dots 2b_{n-2}+b_{n-1}\]

However, the summing the following inequality while $i$ runs from $1$ to $n-1$:

\[a_1 + \dots + a_i \le b_1 + \dots + b_i\]

We get:

\[(n-1)a_1+(n-2)a_2+\dots 2a_{n-2}+a_{n-1}\le (n-1)b_1+(n-2)b_2+\dots 2b_{n-2}+b_{n-1}\]

Since the equality case occurs, the equality case must occur in all the inequalities. From this, the desired result follows.

Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Because destroying everything mindlessly isn't cool enough.

- Thanic Nur Samin
**Posts:**176**Joined:**Sun Dec 01, 2013 11:02 am

### Re: IMO Marathon

$\text{Problem 54}$

The following operation is allowed on a finite graph: choose any cycle of length $4$ (if one exists), choose an arbitrary edge in that cycle, and delete this edge from the graph. For a fixed integer $n \ge 4$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices is joined by an edge).

The following operation is allowed on a finite graph: choose any cycle of length $4$ (if one exists), choose an arbitrary edge in that cycle, and delete this edge from the graph. For a fixed integer $n \ge 4$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices is joined by an edge).

Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Because destroying everything mindlessly isn't cool enough.

### Re: IMO Marathon

$\text{Solution:}$Thanic Nur Samin wrote:$\text{Problem 54}$

The following operation is allowed on a finite graph: choose any cycle of length $4$ (if one exists), choose an arbitrary edge in that cycle, and delete this edge from the graph. For a fixed integer $n \ge 4$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices is joined by an edge).

**Answer:**

**The minimum value:**

**Construction:**

Last edited by tanmoy on Fri Feb 24, 2017 10:48 pm, edited 2 times in total.

"Questions we can't answer are far better than answers we can't question"

### Re: IMO Marathon

$\text{Problem 55}$

Let $n$ be a positive integer and let $(a_1,a_2,\ldots ,a_{2n})$ be a permutation of $1,2,\ldots ,2n$ such that the numbers $|a_{i+1}-a_i|$ are pairwise distinct for $i=1,\ldots ,2n-1$.

Prove that $\{a_2,a_4,\ldots ,a_{2n}\}=\{1,2,\ldots ,n\}$ if and only if $a_1-a_{2n}=n$.

Let $n$ be a positive integer and let $(a_1,a_2,\ldots ,a_{2n})$ be a permutation of $1,2,\ldots ,2n$ such that the numbers $|a_{i+1}-a_i|$ are pairwise distinct for $i=1,\ldots ,2n-1$.

Prove that $\{a_2,a_4,\ldots ,a_{2n}\}=\{1,2,\ldots ,n\}$ if and only if $a_1-a_{2n}=n$.

"Questions we can't answer are far better than answers we can't question"