Page 19 of 19

### Re: IMO Marathon

Posted: Sun Feb 19, 2017 11:12 am
$\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$.

### Re: IMO Marathon

Posted: Sun Feb 19, 2017 11:25 pm
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.

### Re: IMO Marathon

Posted: Sun Feb 19, 2017 11:43 pm
$\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).

### Re: IMO Marathon

Posted: Fri Feb 24, 2017 1:25 pm
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:}$
$\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$.