Lời giải Hoang72, 10-01-2024 - 10:24
Nhận thấy nếu đổi chỗ quả bóng đen $a$ và quả bóng đen $b$, đồng thời đổi chỗ quả bóng trắng $a$ và quả bóng trắng $b$ thì điều kiện bài toán vẫn được đảm bảo.
Do đó ta không mất tính tổng quát, coi các quả bóng đen được sắp xếp theo thứ tự tăng dần (quả bóng đen $i$ đứng trước quả bóng đen $i+1$)
Khi đó, các quả bóng trắng được sắp xếp theo thứ tự giảm dần.
Gọi $u_n$ là số cách sắp xếp thoả mãn các điều kiện trên.
+) Nếu quả bóng đen $n$ đứng trước quả bóng trắng $n$ thì ta có duy nhất cách xếp thoả mãn là đen $1$, đen $2$,..., đen $n$, trắng $n$,..., trắng $2$, trắng $1$.
+) Nếu quả bóng đen $n - 1$ đứng trước quả bóng trắng $n$ thì sử dụng điều kiện b), ta có quả bóng đen $n$ đứng trước các quả bóng trắng $n-1,...,1$. Như vậy ta cũng có duy nhất cách xếp thoả mãn là đen $1$, đen $2$,..., đen $n-1$, trắng $n$, đen $n$, trắng $n-1$,..., trắng $1$.
+) Nếu quả bóng trắng $n$ đứng trước quả bóng đen $i$ mà đứng sau quả bóng đen $i-1$ (coi quả bóng đen $0$ đứng trước mọi quả bóng) thì quả bóng đen $n$ đứng trước các quả bóng trắng $1,...,i-1$, và đứng sau các quả bóng trắng $i,...,n$. Rõ ràng các quả bóng $1,...,i-1$ và $n$ đã chọn được vị trí. Chú ý các quả bóng trắng $i,...,n - 1$ cũng đứng sau quả bóng đen $i-1$. Như vậy ta cần xếp các quả bóng trắng $i,...,n-1$ vào các vị trí cố định của các quả bóng đen $i,...,n-1$, số cách xếp là $u_{n - i}$.
Dẫn đến $u_n = 2 + u_1 + u_2 + ... + u_{n-1}$. Bằng quy nạp, ta chứng minh được $u_n = 2^{n},\forall n\in\mathbb N^*$.
Kết hợp với $n!$ hoán vị của các quả bóng đen, ta có tất cả $2^{n} . n!$ cách xếp.
Đi đến bài viết »
Trung sĩ
Có $2n$ quả bóng được đánh số $1,2,...,n$ và tô $2$ màu đen trắng, không có $2$ quả nào vừa cùng màu vừa cùng số. Có bao nhiêu cách sắp xếp chúng trên một đường thẳng thỏa mãn cả hai điều kiện:
a) Quả bóng đen $a$ đứng trước quả bóng đen $b$ khi và chỉ khi quả bóng trắng $b$ đứng trước quả bóng trắng $a$.
b) Quả bóng đen $a$ đứng trước quả bóng trắng $b$ khi và chỉ khi quả bóng đen $b$ đứng trước quả bóng trắng $a$.
Bài viết đã được chỉnh sửa nội dung bởi poset: 07-01-2024 - 18:14
Thiếu úy
Nhận thấy nếu đổi chỗ quả bóng đen $a$ và quả bóng đen $b$, đồng thời đổi chỗ quả bóng trắng $a$ và quả bóng trắng $b$ thì điều kiện bài toán vẫn được đảm bảo.
Do đó ta không mất tính tổng quát, coi các quả bóng đen được sắp xếp theo thứ tự tăng dần (quả bóng đen $i$ đứng trước quả bóng đen $i+1$)
Khi đó, các quả bóng trắng được sắp xếp theo thứ tự giảm dần.
Gọi $u_n$ là số cách sắp xếp thoả mãn các điều kiện trên.
+) Nếu quả bóng đen $n$ đứng trước quả bóng trắng $n$ thì ta có duy nhất cách xếp thoả mãn là đen $1$, đen $2$,..., đen $n$, trắng $n$,..., trắng $2$, trắng $1$.
+) Nếu quả bóng đen $n - 1$ đứng trước quả bóng trắng $n$ thì sử dụng điều kiện b), ta có quả bóng đen $n$ đứng trước các quả bóng trắng $n-1,...,1$. Như vậy ta cũng có duy nhất cách xếp thoả mãn là đen $1$, đen $2$,..., đen $n-1$, trắng $n$, đen $n$, trắng $n-1$,..., trắng $1$.
+) Nếu quả bóng trắng $n$ đứng trước quả bóng đen $i$ mà đứng sau quả bóng đen $i-1$ (coi quả bóng đen $0$ đứng trước mọi quả bóng) thì quả bóng đen $n$ đứng trước các quả bóng trắng $1,...,i-1$, và đứng sau các quả bóng trắng $i,...,n$. Rõ ràng các quả bóng $1,...,i-1$ và $n$ đã chọn được vị trí. Chú ý các quả bóng trắng $i,...,n - 1$ cũng đứng sau quả bóng đen $i-1$. Như vậy ta cần xếp các quả bóng trắng $i,...,n-1$ vào các vị trí cố định của các quả bóng đen $i,...,n-1$, số cách xếp là $u_{n - i}$.
Dẫn đến $u_n = 2 + u_1 + u_2 + ... + u_{n-1}$. Bằng quy nạp, ta chứng minh được $u_n = 2^{n},\forall n\in\mathbb N^*$.
Kết hợp với $n!$ hoán vị của các quả bóng đen, ta có tất cả $2^{n} . n!$ cách xếp.
Bài viết đã được chỉnh sửa nội dung bởi Hoang72: 10-01-2024 - 10:24
0 thành viên, 1 khách, 0 thành viên ẩn danh
Community Forum Software by IP.Board
Licensed to: Diễn đàn Toán học
