Câu hỏi 31
Một hoán vị của các số $1,2,\ldots,n$ được gọi là "xấu" nếu chứa một dãy con gồm 10 số theo thứ tự giảm dần; nếu không thì được gọi là "tốt". Ví dụ, với $n=15$,
$$
15,13,1,12,7,11,9,8,10,6,5,4,3,2,14
$$
là một hoán vị xấu vì chứa dãy con
$$
15,13,12,11,10,6,5,4,3,2.
$$
Chứng minh rằng với mỗi $n$, số hoán vị tốt không vượt quá $81^n$.
$$
15,13,1,12,7,11,9,8,10,6,5,4,3,2,14
$$
là một hoán vị xấu vì chứa dãy con
$$
15,13,12,11,10,6,5,4,3,2.
$$
Chứng minh rằng với mỗi $n$, số hoán vị tốt không vượt quá $81^n$.