## IMO Marathon

Discussion on International Mathematical Olympiad (IMO)
rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

### Re: IMO Marathon

$\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$.

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.
Hammer with tact.

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).
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

tanmoy
Posts: 289
Joined: Fri Oct 18, 2013 11:56 pm

### Re: IMO Marathon

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).
$\text{Solution:}$

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"

tanmoy
Posts: 289
Joined: Fri Oct 18, 2013 11:56 pm
$\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$.