BdMO National Higher Secondary 2019/5

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
samiul_samin
Posts: 1004
Joined: Sat Dec 09, 2017 1:32 pm

BdMO National Higher Secondary 2019/5

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

Abdullah Al Tanzim
Posts: 20
Joined: Tue Apr 11, 2017 12:03 am

Re: BdMO National Higher Secondary 2019/5

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.
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