[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include(/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php) [function.include]: failed to open stream: No such file or directory
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 122: include() [function.include]: Failed opening '/home/shoeb/public_html/www.matholympiad.org.bd/forum/includes/phpbb-latex.php' for inclusion (include_path='.:/opt/php53/lib/php')
[phpBB Debug] PHP Warning: in file [ROOT]/includes/session.php on line 1042: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4786: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4788: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4789: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4790: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3887)
BdMO Online Forum • View topic - IMO Marathon

## IMO Marathon

Discussion on International Mathematical Olympiad (IMO)

### 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$.
rah4927

Posts: 104
Joined: Sat Feb 07, 2015 9:47 pm

### 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: 154
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.

Thanic Nur Samin

Posts: 154
Joined: Sun Dec 01, 2013 11:02 am

### 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:}$
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.
I like girls and mathematics; both are beautiful.
tanmoy

Posts: 276
Joined: Fri Oct 18, 2013 11:56 pm

### 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$.
I like girls and mathematics; both are beautiful.
tanmoy

Posts: 276
Joined: Fri Oct 18, 2013 11:56 pm

Previous