Given any integer $n\geq 3$. A finite series is called $n$-series if it satisfies the following two conditions $1)$ It has at least $3$ terms and each term of it belongs to $\{ 1,2,...,n\}$ $2)$ If series has $m$ terms $a_1,a_2,...,a_m$ then $(a_{k+1}-a_k)(a_{k+2}-a_k)<0$ for all $k=1,2,...,m-2$ How many $n$-series are there $?$
Problem
Source: China South East Mathematicall Olympiad Grade 10 Prob.3
Tags: combinatorics
03.08.2016 19:24
Any idea ?
06.08.2016 05:57
There are $2^{n+1}-n^2-n-2$. For every $n$-series, if $a_1<a_2$ then call this $n$-series as up $n$-series, if $a_1>a_2$ then call this $n$-series as down $n$-series. Let $T=\{A_i|A_i\subseteq \{1,2,\dots,n\},|A_i|\ge 3\}$, $S_1=\{\{a_n\}|\{a_n\}\text{ is up }n\text{-series}\}$, $S_2=\{\{a_n\}|\{a_n\}\text{ is down }n\text{-series}\}$. $(1)$ For every element $A_i\in T$, let $A_i=\{b_1,b_2,\dots,b_k\},b_1<b_2<\dots<b_k$. If $k$ is odd, let $k=2l+1$ then $b_l,b_{l+1},b_{l-1},b_{l+2},b_{l-2},\dots,b_{2l+1},b_1$ is up $n$-series, $b_l,b_{l-1},b_{l+1},b_{l-2},b_{l+2},\dots,b_1,b_{2l+1}$ is down $n$-series. If $k$ is even, let $k=2l$ then $b_l,b_{l+1},b_{l-1},b_{l+2},b_{l-2},\dots,b_1,b_{2l}$ is up $n$-series, $b_{l+1},b_l,b_{l+2},b_{l-1},\dots,b_{2l},b_1$ is down $n$-series. So $|T|\le |S_i|(i=1,2)$. $(2)$ It's easy to get that for $n$-series $b_1,b_2,\dots,b_k$, we have $b_i\neq b_j$ for $i\neq j$, so every $n$-series correspond a subset of $\{1,2,\dots,n\}$, so $|T|\ge |S_i|(i=1,2)$. Then we can get there are $2|T|=2^{n+1}-n^2-n-2$ many $n$-series.
30.10.2016 15:26
$(a_{k+1}-a_k)(a_{k+2}-a_k)<0$ means $a_{k+1} < a_k < a_{k+2}$ or $a_{k+1} > a_k > a_{k+2}$ suppose m>3 case 1 : $a_{k+1} < a_k < a_{k+2}$ so $a_{k+2} < a_{k+1} $ contradiction case 2 : $a_{k+1} > a_k > a_{k+2}$ so : $a_{k+2}> a_{k+1}$ contradicion so m= 3 since $n$-series have at least $3$ terms and each term of it belongs to $\{ 1,2,...,n\}$ and 3 terms so there is $\binom{3}{n}$