2003 Vietnamese Mathematical Olympiad

• Firstly, we construct an inductive relation for $s_n$. Consider an integer $n>4$. Denote by $P_n$ the set of permutations $(a_1,a_2,\dots ,a_n)$ satisfying the condition of the problem. Consider the partition: $$P_n=\bigcup _{k=1}^n{S}_k(1)$$ where $S_k$ is the set of permutations $(a_1,a_2,...,a_n)\in P_n$ such that $$\{a_1,a_2,...,a_k\}=\{1,2,...,k\},$$ $$\{a_1,a_2,...,a_i\}\ne \{1,2,...,i\}\forall i<k.$$ For every $k>1$, denote by $H_k$ the set of permutations $(a_1,a_2,...,a_k)$ of $k$ first positive integers such that each permutation satisfies simultaneously the following two conditions: $$i/1\le |a_i-i|\le 2\forall i=1,2,...,k;(2)$$ $$ii/\{a_1,a_2,...,a_i\}\ne \{1,2,...,i\}\forall i=1,2,...,k-1.(3)$$ Put $t_k=|H_k|$. Then it is easy to see that for every $k=1,2,...,n$, we have $|S_k|=t_k\cdot S_{n-k}$. (We put $S_0=1$). It follows from (1) that $$S_n=|P_n|=t_1\cdot S_{n-1}+t_2\cdot S_{n-2}+...+t_n\cdot S_0(4)$$ • Secondly, we calculate $t_k$, $k=1,2,...,n$. It is easy to see that: $$H_1=\varnothing \Rightarrow t_1=0.(5)$$ $$H_2=\{(2,1)\}\Rightarrow t_2=1.(6)$$ $$H_3=\{(2,3,1);(3,1,2)\}\Rightarrow t_3=2.(7)$$ $$H_4=\{(2,4,1,3);(3,1,4,2);(3,4,1,2)\}\Rightarrow t_4=3.(8)$$ Consider $H_k$ with $4<k\le n$. Let $(a_1,a_2,...,a_k)\in H_k$. Can occur: - 1st case: $a_1=2$. We shall prove that in this case, $a_{2i}=2i+2$ and $a_{2i+1}=2i-1$ () for every $i=1,2,...,[k/2]-1$. Indeed, it follows from (2) and (3) that $a_3=1$; and so, from (3), $a_2\ne 3$. It follows that $a_2=4$ (since $a_2\in \{1,3,4\}$ from (2)). So () holds for $i=1$. Suppose that () holds for every $i\le m$, with $1\le m\le [k/2]-2$, i.e. we have: $$a_2=4,a_3=1,...,a_{2m-2}=2m,a_{2m-1}=2m-3,a_{2m}=2m+2,a_{2m+1}=2m(9)$$ From (9) and (2) it follows that $2m+1\in \{a_{2m+2},a_{2m+3}\}$. If $a_{2m+2}=2m+1$ then with remarking that $j\in \{a_1,a_2,...,a_{2m+1}\}$ for every $j<2m$, we get $$\{a_1,a_2,...,a_{2m+2}\}=\{1,2,...,2m+2\},$$ which contradicts (3) (since $2m+2<k$). So $a_{2m+3}$ must be equal to $2m+1$. (). From (), (2) and (9) it follows that $a_{2m+2}\in \{2m+3,2m+4\}$. But if $a_{2m+2}=2m+3$, by an analogous reasoning, we get $$\{a_1,a_2,...,a_{2m+3}\}=\{1,2,...,2m+3\},$$ which contradicts (3). So $a_{2m+2}$ must be equal to $2m+4$. These results show that () holds for $i=m+1$. So, by induction, (*) holds for all $i=1,2,...,[k/2]-1$. By an analogous reasoning, we have: $$+a_k=k-1\text{ if k is even, and}$$ + $a_{k-1}=k$, $a_k=k-2$ if k is odd. Thus, there is a unique permutation $(a_1,a_2,...,a_k)\in H_k$ such that $a_1=2$. - 2nd case: $a_1=3$. In this case, we shall prove analogously that $(3,a_2,...,a_k)\in H_k\iff a_2=1$ and + if k is even then: $a_{2i-1}=2i+1$, $a_{2i}=2i-2$ $\forall i=2,...,\lfloor k/2\rfloor -1$; $a_{k-1}=k$, $a_k=k-2$. + if k is odd then: $a_{2i-1}=2i+1$, $a_{2i}=2i-2$ $\forall i=2,...,\lfloor k/2\rfloor$; $a_k=k-1$. Shortly, we have: $t_k=2$ $\forall k=4,5,...,n$. (10) • From (4) – (8) and (10) it follows that: $$S_n=S_{n-2}+2\cdot S_{n-3}+3\cdot S_{n-4}+2(S_{n-5}+\cdots +S_1+S_0)(11)$$ Therefore $$S_{n+1}=S_{n-1}+2\cdot S_{n-2}+3\cdot S_{n-3}+2(S_{n-4}+\cdots +S_1+S_0)(12)$$ By subtracting (11) from (12), we get $$S_{n+1}-S_n=S_{n-1}+S_{n-2}+S_{n-3}-S_{n-4}(13)$$ hence $$S_{n+2}-S_{n+1}=S_n+S_{n-1}+S_{n-2}-S_{n-3}(14)$$ By subtracting (13) from (14), we get $$S_{n+2}-2\cdot S_{n+1}=S_{n-4}-2\cdot S_{n-3}.$$ $$\text{So, with }n>6,\text{ we have: }{S}_n-2\cdot S_{n-1}=S_{n-6}-2\cdot S_{n-5}.(15)$$ It is easy to prove that $S_{n-5}>S_{n-6}\forall n>6$. Therefore, from (15), we get: $$S_n<2\cdot S_{n-1}\forall n>6.(16)$$ $$\text{Moreover, from (13) we have }{S}_n>S_{n-1}+S_{n-2}+S_{n-3}\forall n>5(17)$$ From (16), (17) it follows that for every $n>8$, we have: $$S_n>S_{n-1}+(S_{n-1/2}+S_{n-2/2})>S_{n-1}+(S_{n-1/2}+S_{n-1/4})=1.75\cdot S_{n-1}$$ By counting directly, we have $S_1=0$, $S_2=1$, $S_3=2$, $S_4=4$. Then, from (14) we can calculate: $S_5=6$, $S_6=13$, $S_7=24$, $S_8=45$. These results show that $S_7>1.75\cdot S_6$ and $S_8>1.75\cdot S_7$. Therefore $S_n>1.75\cdot S_{n-1}\forall n>6$. $$\text{So: }1.75\cdot S_{n-1}<S_n<2\cdot S_{n-1}\forall n>6.$$