IMO Marathon

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

Unread post by rah4927 » 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$.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: IMO Marathon

Unread post by Thanic Nur Samin » 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.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: IMO Marathon

Unread post by Thanic Nur Samin » 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).
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: IMO Marathon

Unread post by tanmoy » 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:}$
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}$.
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:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: IMO Marathon

Unread post by tanmoy » Fri Feb 24, 2017 5:09 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$.
"Questions we can't answer are far better than answers we can't question"

Post Reply