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
by Thanic Nur Samin
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
by Thanic Nur Samin
$\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
by tanmoy
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:}$ Answer:
We claim that the least number of edges is $n$.
The minimum value:
Let $E_{n}$ denote the number of edges left at the end of the applications.
We will prove by introduction that $E_n=n$.
The base case $n=4$ is easy to check. Now, let's assume that it is true for $n=m-1$. Now let $n=m$. Let's forget about a vertex. By inductive hypothesis, after deleting all the $4-cycles $, exactly $n-1$ edges left. Therefore, $E_{n} \geq n-1$.
If $E_n=n-1$, the forgotten vertex has degree $0$. But this can't be possible. Because in each step, the degree of a vertex decreases by $1$. So, if the degree of a vertex becomes $0$, it had degree $1$ at some moment, and became $0$ by subtracting an edge incident to this vertex from a $4-cycle$. But a vertex with degree $1$ can't be a part of a $4-cycle$, (Because, every vertex in a $4-cycle$ has degree at least $2$.) a contradiction.
So, $E_{n}=n$.
Construction:
We will show a construction for $E_{n}=n$. Let the vertices be $v_{1}, v_{2},.........., v_{n}$. Consider the algorithm: Take cycles of the form $v_{2}v_{i}v_{j}v_{n}$, where $i, \ j \in \{3,4,.....n-1\}$ and $i \neq j$ and delete edges $v_{i}v_{j}$ from these cycles.
Now take cycles of the form $v_{1}v_{2}v_{i}v_{n}$ for all $i \in \{3,......,n-1\}$ and delete edges $v_{2}v_{i}$ from them.
Next take cycles of the form $v_{1}v_{2}v_{n}v_{i}$ for all $i \in \{3,......,n-1\}$ and delete edges $v_{n}v_{i}$ from them.
Then we are left with a graph with $n$ edges, $v_{1}v_{i}$ for all $i \in \{2,......,n\}$ and $v_{2}v_{n}$.
Re: IMO Marathon
Posted: Fri Feb 24, 2017 5:09 pm
by tanmoy
$\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$.