Toán 9 Toán

Nguyễn Đăng Bình

Học sinh tiến bộ
Thành viên
12 Tháng hai 2019
2,153
1,936
296
Hà Nội
Trường THPT chuyên Hà Nội-Amsterdam
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Có bn cách xếp 10 người có chiều cao đôi một phân biệt thành một hàng ngang sao cho trong hàng mn luôn cao hơn hoặc luôn thấp hơn tất cả những người xếp trước?
(Mình hỏi đứa bạn thì nó bảo có 2^10 = 1024 cách?)
 

Mộc Nhãn

TMod Toán
Cu li diễn đàn
19 Tháng một 2019
6,327
10,650
1,116
16
Hà Tĩnh
THPT Chuyên Hà Tĩnh
Gọi [TEX]X_n[/TEX] là số cách sắp xếp n người thỏa mãn đề bài (coi như [TEX]X_0[/TEX]=1 vì khi không có người nào đứng thì chỉ có một cách sắp xếp duy nhất )
Giả sử chiều cao của n người trên lần lượt là [TEX]a_1;a_2;...;a_n[/TEX]sao cho với [TEX]i<j \Rightarrow a_i<a_j[/TEX]
Khi đó; giả sử người có chiều cao là [TEX]a_1[/TEX] đứng ở vị trí thứ k [tex](0\leq k\leq n)[/tex] thì mỗi người đứng ở vị trí từ 1→k luôn cao hơn tất cả những người đứng trước vì nếu ngược lại thì tồn tại một người có chiều cao nhỏ hơn a1 (vô lý) ⇒ người đứng ở vị trí thứ 1 là người cao nhất và có chiều cao [TEX]a_n[/TEX]
Tương tự; người đứng ở vị trí thứ 2 có chiều cao là [tex]a_{n-1}[/tex]
người đứng ở vị trí thứ 3 có chiều cao là [TEX]a_{n-2}[/TEX]
.............
người đứng ở vị trí thứ k - 1 có chiều cao là [tex]a_{n-k}[/tex]
Do đó với mọi [tex]0\leq k\leq n[/tex] thì chỉ có một cách sắp sếp những người đứng ở vị trí từ 1 đến k sao cho thỏa mãn đề bài. Từ đó suy ra số cách sắp xếp n người thỏa mãn đề bài khi người thấp nhất (có chiều cao [TEX]a_1[/TEX]) đứng ở vị trí thứ k chính bằng số cách sắp xếp [tex]n-k[/tex] người đứng từ vị trí thứ k+1 trở đi (=[tex]X_{n-k}[/tex] ).
Vì vậy; khi cho k lần lượt bằng [tex]n,n-1,...,1[/tex] thì ta nhận được số cách sắp xếp n người lần lượt là [tex]X_0,X_1,...,X_{n-1}[/tex]
Mà tổng số cách sắp xếp n người bằng tổng các số trên nên [tex]X_n=X_0+X_1+...+X_{n-1}[/tex]
Lại có [tex]X_0=1,X_1=1\Rightarrow X_n=2^{n-1}[/tex]
Thay n = 10 ta có [tex]X_n=2^9=512[/tex]
 
Top Bottom