Chủ đề này có 1 trả lời

[LinhToan]

có bao nhiêu cách sắp xếp các số 1,2,3,4,5,6,7 thành 1 hàng ngang sao cho mọi số lớn hơn hoặc nhỏ hơn tất cả các số đứng trước nó.(đề thi thử khtn)

mọi người gt rõ giúp ạ

[Dark Magician 2k2]

có bao nhiêu cách sắp xếp các số 1,2,3,4,5,6,7 thành 1 hàng ngang sao cho mọi số lớn hơn hoặc nhỏ hơn tất cả các số đứng trước nó.(đề thi thử khtn)

mọi người gt rõ giúp ạ

Gọi $x_n$ là số cách xếp thoả mãn đề bài của các số $1,2,...,n$.

Xét $S_{n+1}=\left\{1,2,...,n+1\right\}$.

Xét một cách xếp mà trong đó $a_i=n+1$ cố định.

Khi đó $a_i>a_j,\forall i<j$.

Xét $a_k$ với $k<i$.

Nếu $a_k<a_j$ thì số $a_j$ không thoả mãn đề bài.

Do đó $a_k>a_j, \forall k<i<j$ 

Mà số hoán vị của $i-1$ số đó là $x_{i-1}$

Do $a_i>a_j$ nên $a_{i+1},a_{i+2},...,a_{n-1}$ phải sắp xếp theo thứ tự giảm dần.

Suy ra $x_{n+1}=\sum_{i=1}^{n+1}x_{i-1}=\sum_{i=0}^{n}x_{i}$

Dễ thấy $x_0=0$

Do đó ta có $\left\{\begin{matrix} x_0=0\\ x_{n+1}=\sum_{i=0}^{n}x_{i} \end{matrix}\right.$

Suy ra $x_{n+1}=2^n$

Vậy có $2^6=64$ cách thoả mãn đề bài.