Vận dụng (M3)

Có 6 người ngồi quanh một bàn tròn trong một trò chơi mật mã. Mỗi người được phát một lá cờ màu Đỏ hoặc Xanh. Họ cần giơ cờ đồng thời để tạo thành một vòng tròn màu sắc. Để mật mã không bị giải dễ dàng, họ không được phép để có 3 người liên tiếp trở lên cầm cờ cùng màu. Hỏi có bao nhiêu cách phối màu cờ khác nhau?

1

Xác nhận

Giải thích đáp án:

Có 6 người trên một vòng tròn, cầm 2 màu cờ (Đỏ - Đ, Xanh - X). Ta phải đếm số cấu hình sao cho không có 3 cờ cùng màu đứng liên tiếp (chiều dài khối liên tiếp tối đa là 2).

Phân tách thành các dạng chuỗi độ dài khối:

1. Các khối có độ dài 1: Chứa các mẫu Đ-X-Đ-X-Đ-X và X-Đ-X-Đ-X-Đ. Có 2 cách.

2. Khối có dạng 2-1-2-1: Ví dụ ĐĐ-X-ĐĐ-X hoặc XX-Đ-XX-Đ. Số lượng hoán vị dịch chuyển vòng tròn của mỗi mẫu là 3 (do tính đối xứng). Đảo màu giữa Đ và X ta có thêm 3 cách. Tổng cộng: 6 cách.

3. Khối có dạng 2-2-1-1: Ví dụ ĐĐ-XX-Đ-X. Mẫu này tạo ra được 6 hoán vị dịch chuyển vòng tròn không trùng lặp. Đảo màu sinh ra thêm 6 cách nữa. Tổng cộng: 12 cách.

Cộng tất cả các trường hợp phân hoạch hợp lệ, ta được: cách phối màu.