BdMO National Higher Secondary 2019/5

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm
BdMO National Higher Secondary 2019/5

Unread post by samiul_samin » Mon Mar 04, 2019 9:23 am

Prove that for all positive integers $n$ we can find a permutation of {$1,2,...,n$} such that the average of two numbers doesn't appear in-between them.For example {$1,3,2,4$}works,but {$1,4,2,3$} doesn't because $2$ is between $1$ and $3$.

User avatar
Abdullah Al Tanzim
Posts:24
Joined:Tue Apr 11, 2017 12:03 am
Location:Dhaka, Bangladesh.

Re: BdMO National Higher Secondary 2019/5

Unread post by Abdullah Al Tanzim » Tue Mar 19, 2019 4:57 pm

We will prove it by strong Induction.
Call a permutation $a_1,a_2,....,a_n$ "GOOD" if the average of any two numbers doesn't appear in between them and call it "VERY GOOD" if it is "GOOD" and for every integer $x\in {1,2,...,n} $, there exists a $i$ such that $a_i=x$

Lemma: If $a_1,a_2,....,a_n$ is a "GOOD" permutation then so is $2a_1-1,2a_2-1,...,2a_n-1$ and $2a_1,2a_2,...,2a_n$.
Proof: Let $b_i=2a_i-1$ and $c_i=2a_i$ for $i\in{1,2,..,n}$

We will prove that if for integers $k,l,m$; $a_k=(a_l+a_m)/2$ then also $b_k=(b_l+b_m)/2$ and $c_k=(c_l+c_m)/2$ holds.

$(b_l+b_m)/2= (2a_l-1+2a_m-1)/2$
$= a_l+a_m-1$
$ =2a_k-1$
$ =b_k$
Similiarly,$ c_k= (c_l+c_m)/2$
So, If $a_k$ is not between $a_l$ and $a_m$, then $b_k$ is also not between $b_l$ and $b_m$ and $c_k$ is not between $c_l$ and $c_m$.So, we have proved our lemma.


The base case for $n=1$ is true.Now, we will consider two cases.

Case 1: When $n=2k$ for any positive integer $k$.

By strong Induction hypothesis,there exists a permutation $a_1,a_2,..,a_k$ which is "VERY GOOD" and by our lemma, the permutations $2a_1-1,2a_2-1,...,2a_k-1$ and $2a_1,2a_2,..,2a_k$ are also "GOOD".
So, ${2a_1-1,2a_2-1,...,2a_k-1,2a_1,2a_2,....,2a_k}$ is a "VERY GOOD" permutation for $n=2k$.

Case 2: When $n=2k+1$

By strong Induction hypothesis,there exists permutations $a_1, a_2,...,a_k$ and $d_1,d_2,....,d_{k+1}$ which are "VERY GOOD" permutations for $n=k$ and $n=k+1$ respectively.
By our lemma, the permutations $2d_1-1,2d_2-1,...,2d_{k+1}$ and $2a_1,2a_2,...,2a_k$ are also "GOOD"
So, $ 2d_1-1,2d_2-1,.....,2d_{k+1},2a_1,2a_2,...,2a_k$ is a "VERY GOOD" permutation for $n=2k+1$
And we are done. :D :D
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein

Post Reply