Đến nội dung

Hình ảnh

Có bao nhiêu cách sắp xếp các số sao cho mọi số hoặc lớn hơn tất cả các số đứng trước nó, hoặc nhỏ hơn tất cả số đứng trước nó?


  • Please log in to reply
Chủ đề này có 1 trả lời

#1
vinhthta

vinhthta

    Lính mới

  • Thành viên mới
  • 9 Bài viết

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


Bài viết đã được chỉnh sửa nội dung bởi vinhthta: 22-02-2019 - 22:38


#2
MachineGun

MachineGun

    Lính mới

  • Thành viên mới
  • 3 Bài viết

Bài này có 2 cách hiểu đề: cách đầu tiền là 2 số ở 2 biên thỏa điều kiện, cách thứ hai là 2 biên không cần thỏa điều kiện

Mình sẽ tổng quát hóa lên n số

Với cách hiểu đầu tiên đáp án là 1 dãy số duy nhất là 1, 2, 3, 4,..., n

Giải thích:

Đầu tiên ta sẽ chứng minh n luôn đứng cuối dãy, giả sử n không đứng cuối dãy, ta xét số cuối cùng của dãy là a thì ta thấy a không thể nhỏ hơn tất cả số đứng trước nó vì không có số nào đứng trước nó, nhưng a cũng không lớn hơn tất cả số đứng trước nó vì a<n => Vô lý.

Vậy n đứng ở cuối dãy, tương tự t chứng minh n-1 đứng vị trí thứ n-1 trong dãy và tiếp tục như vậy ta có đpcm

Cách hiểu thứ 2:

Đặt S(n) là số các số dãy thỏa đề có độ dài  n, A(n) là số các số dãy thỏa đề có độ dài n và n là số đứng cuối, B(n) là số các số dãy thỏa đề và n không đứng cuối dãy

Dễ thấy ta có $S(n)=A(n)+B(n)$

Đầu tiên ta tính A(n)

Dễ dàng thấy số n đứng cuối không ảnh hưởng đến dãy vì tất cả mọi số đều bé hơn nó nên $A(n)=S(n-1)$ 

Tiếp theo ta tính B(n)

Xét 2 trường hợp, nếu n-1 đứng cuối dãy và n-1 không đứng cuối dãy

Ở trường hợp 1, nếu ta bỏ số n-1 đi và thay n bằng n-1 thì dãy B(n) không khác gì dãy S(n-1)

Ở trường hợp 2, ta sẽ chứng minh n-1 đứng ngay trước n

Giả sử ngược lại nếu n-1 không đứng trước n thì dễ dàng thấy số ở giữa n-1 và n không thỏa đề, vậy n-1 đứng ngay trước n

Ta gộp n-1, n thành n-1 thì dãy B(n) sẽ thành dãy B(n-1)

Vậy $B(n)=S(n-1)+B(n-1)$

Kết hợp với A(n) ta có $S(n)=2S(n-1)+B(n-1)$

Liên tục thay thế $B(n)=S(n-1)+B(n-1)$  ta sẽ có $S(n)=2S(n-1)+S(n-2)+S(n-3)+...+S(1)$






2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh