[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)
Facebook Twitter

Re: IMO Marathon

Post Number:#181  Unread postby 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$.
rah4927
 
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

Re: IMO Marathon

Post Number:#182  Unread postby 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: 174
Joined: Sun Dec 01, 2013 11:02 am

Re: IMO Marathon

Post Number:#183  Unread postby 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.
User avatar
Thanic Nur Samin
 
Posts: 174
Joined: Sun Dec 01, 2013 11:02 am

Re: IMO Marathon

Post Number:#184  Unread postby 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.
I like girls and mathematics; both are beautiful.
tanmoy
 
Posts: 277
Joined: Fri Oct 18, 2013 11:56 pm
Location: Rangpur,Bangladesh

Re: IMO Marathon

Post Number:#185  Unread postby 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$.
I like girls and mathematics; both are beautiful.
tanmoy
 
Posts: 277
Joined: Fri Oct 18, 2013 11:56 pm
Location: Rangpur,Bangladesh

Previous

Share with your friends: Facebook Twitter

  • Similar topics
    Replies
    Views
    Author

Return to International Mathematical Olympiad (IMO)

Who is online

Users browsing this forum: No registered users and 3 guests