Câu 4THPTChuyên đề: Đếm có điều kiện kề nhau hoặc loại trừ • Lớp 10Quy tắc cộng và nhân trong đếmSố hạng tổng quát và truy hồiVận dụng cao#secondary:M10.A08.COUNTING.L3.SUM_PRODUCT#secondary:M11.A05.SEQUENCE.L3.FORMULA
Câu 4 (1,5 điểm): Cho -giác đều . Mỗi một đỉnh của -giác đều được tô bởi một màu trong màu cho trước sao cho hai đỉnh kề nhau được tô bởi hai màu khác nhau. Tìm số cách tô màu có thể thực hiện được trong các trường hợp sau:
a) Khi , .
b) Khi , .
Câu 4 (1,5 điểm): Cho -giác đều . Mỗi một đỉnh của -giác đều được tô bởi một màu trong màu cho trước sao cho hai đỉnh kề nhau được tô bởi hai màu khác nhau. Tìm số cách tô màu có thể thực hiện được trong các trường hợp sau:
a) Khi , .
b) Khi , .
a) Khi , .
b) Khi , .
Đáp án chính thức: Tự luận
Hướng dẫn giải chi tiết
4a (0,5 điểm): Khi , .
Không mất tính tổng quát giả sử ta tô màu theo thứ tự các đỉnh . Đỉnh có 5 cách tô màu. Đỉnh có 4 cách tô màu.
TH1: đỉnh được tô màu cùng màu với đỉnh . Lúc đó, có 1 cách tô màu đỉnh và có 4 cách tô màu đỉnh . Trong trường hợp này, có tất cả cách tô màu.
TH2: đỉnh được tô màu khác màu với đỉnh . Lúc đó, có 3 cách tô màu đỉnh và có 3 cách tô màu đỉnh . Trong trường hợp này, có tất cả cách tô màu.
Vậy có 260 cách tô màu khi , .
4b (1,0 điểm): Khi , .
Gọi là số cách tô màu -giác đều thỏa mãn bài toán. Ta giải bài toán trong trường hợp tổng quát với bất kỳ thỏa mãn ; ; .
TH1: đỉnh và đỉnh được tô bởi hai màu khác nhau. Lúc đó, đỉnh được tô màu khác với màu của hai đỉnh trên nên đỉnh có tất cả cách tô màu. Trong trường hợp này, ta có số cách tô màu là .
TH2: đỉnh và đỉnh được tô bởi cùng một màu. Lúc đó, đỉnh được tô màu khác với màu trên nên đỉnh có tất cả cách tô màu. Trong trường hợp này, ta có số cách tô màu là .
Như vậy, ta có công thức truy hồi .
Khi : đỉnh có cách tô màu, đỉnh có cách tô màu, đỉnh có cách tô màu. Do đó .
Khi và theo câu a) ta có:
Do đó, ta có dãy số xác định bởi
Từ hệ thức truy hồi trên, ta có , với ; .
Thay , , ta được
Vậy khi , ta có cách tô màu.
Không mất tính tổng quát giả sử ta tô màu theo thứ tự các đỉnh . Đỉnh có 5 cách tô màu. Đỉnh có 4 cách tô màu.
TH1: đỉnh được tô màu cùng màu với đỉnh . Lúc đó, có 1 cách tô màu đỉnh và có 4 cách tô màu đỉnh . Trong trường hợp này, có tất cả cách tô màu.
TH2: đỉnh được tô màu khác màu với đỉnh . Lúc đó, có 3 cách tô màu đỉnh và có 3 cách tô màu đỉnh . Trong trường hợp này, có tất cả cách tô màu.
Vậy có 260 cách tô màu khi , .
4b (1,0 điểm): Khi , .
Gọi là số cách tô màu -giác đều thỏa mãn bài toán. Ta giải bài toán trong trường hợp tổng quát với bất kỳ thỏa mãn ; ; .
TH1: đỉnh và đỉnh được tô bởi hai màu khác nhau. Lúc đó, đỉnh được tô màu khác với màu của hai đỉnh trên nên đỉnh có tất cả cách tô màu. Trong trường hợp này, ta có số cách tô màu là .
TH2: đỉnh và đỉnh được tô bởi cùng một màu. Lúc đó, đỉnh được tô màu khác với màu trên nên đỉnh có tất cả cách tô màu. Trong trường hợp này, ta có số cách tô màu là .
Như vậy, ta có công thức truy hồi .
Khi : đỉnh có cách tô màu, đỉnh có cách tô màu, đỉnh có cách tô màu. Do đó .
Khi và theo câu a) ta có:
Do đó, ta có dãy số xác định bởi
Từ hệ thức truy hồi trên, ta có , với ; .
Thay , , ta được
Vậy khi , ta có cách tô màu.
