MathLabs

Bài 6

Một hoán vị (x1,x2,…,x2n)(x_1,x_2,\ldots,x_{2n}) của {1,2,…,2n}\{1,2,\ldots,2n\} có tính chất PP nếu ∣xi−xi+1∣=n|x_i-x_{i+1}|=n với ít nhất một i∈{1,…,2n−1}i\in\{1,\ldots,2n-1\}. Chứng minh rằng với mọi số nguyên dương nn, số hoán vị có tính chất PP lớn hơn số hoán vị không có tính chất đó.
Bước 5 trên 5: Vượt quá một nửa mọi hoán vị
Bước trướcBước tiếp
Hiểu nôm na

Đa số nghiêm ngặt chính là điều cần so sánh với các hoán vị không có P.

2n2(2n−2)!>(2n)!2⟹∣A∣>(2n)!22n^2(2n-2)!>\frac{(2n)!}{2}\quad\Longrightarrow\quad |A|>\frac{(2n)!}{2}
Phân tích chi tiết

Vì (2n)!=2n(2n−1)(2n−2)!(2n)!=2n(2n-1)(2n-2)!, bất đẳng thức 2n2(2n−2)!>(2n)!/22n^2(2n-2)!>(2n)!/2 tương đương 2n>2n−12n>2n-1, luôn đúng. Do đó hơn một nửa của (2n)!(2n)! hoán vị thuộc AA và có tính chất PP; số còn lại ít hơn, chứng minh xong.