Câu 6. (7.0 điểm)
Cho đa giác lồi 2026 đỉnh . Tô màu tất cả các đỉnh của đa giác bởi một trong hai màu đỏ hoặc xanh, mỗi đỉnh chỉ được tô bởi một màu.
a) Tính số cách tô màu sao cho không có 2 đỉnh nào kề nhau đều được tô màu xanh.
b) Tính số cách tô màu sao cho với mọi , trong đỉnh , số đỉnh được tô màu đỏ không ít hơn số đỉnh được tô màu xanh.
Câu 6. (7.0 điểm)
Cho đa giác lồi 2026 đỉnh . Tô màu tất cả các đỉnh của đa giác bởi một trong hai màu đỏ hoặc xanh, mỗi đỉnh chỉ được tô bởi một màu.
a) Tính số cách tô màu sao cho không có 2 đỉnh nào kề nhau đều được tô màu xanh.
b) Tính số cách tô màu sao cho với mọi , trong đỉnh , số đỉnh được tô màu đỏ không ít hơn số đỉnh được tô màu xanh.
Cho đa giác lồi 2026 đỉnh . Tô màu tất cả các đỉnh của đa giác bởi một trong hai màu đỏ hoặc xanh, mỗi đỉnh chỉ được tô bởi một màu.
a) Tính số cách tô màu sao cho không có 2 đỉnh nào kề nhau đều được tô màu xanh.
b) Tính số cách tô màu sao cho với mọi , trong đỉnh , số đỉnh được tô màu đỏ không ít hơn số đỉnh được tô màu xanh.
Đáp án chính thức: Tự luận
Hướng dẫn giải chi tiết
Lời giải.
a) Trước hết xét một dãy gồm đỉnh thẳng hàng. Gọi là số cách tô đỏ, xanh các đỉnh sao cho không có hai đỉnh xanh liên tiếp.
Ta có , . Với , xét màu của đỉnh cuối cùng. Nếu đỉnh cuối màu đỏ thì đỉnh trước có cách tô. Nếu đỉnh cuối màu xanh thì đỉnh ngay trước nó bắt buộc màu đỏ, còn đỉnh đầu có cách tô. Do đó .
Trở lại với đa giác 2026 đỉnh. Xét màu của .
- Nếu màu đỏ thì là một dãy 2025 đỉnh, nên có cách tô.
- Nếu màu xanh thì do và đều kề , hai đỉnh này bắt buộc màu đỏ. Khi đó chỉ còn dãy gồm 2023 đỉnh cần tô, nên có cách.
Vì vậy số cách tô là .
b) Ta biểu diễn mỗi cách tô bằng một quỹ đạo trên lưới ô vuông, xuất phát từ như sau:
- Nếu được tô đỏ thì đi một bước sang phải.
- Nếu được tô xanh thì đi một bước lên trên.
Sau bước, hoành độ của điểm đang đứng bằng số đỉnh đỏ trong , còn tung độ bằng số đỉnh xanh. Vì vậy điều kiện của bài toán tương đương với việc quỹ đạo luôn nằm trên hoặc phía dưới đường thẳng .
Giả sử có đúng đỉnh xanh, với . Khi đó có đỉnh đỏ, nên quỹ đạo đi từ đến bằng bước sang phải và bước lên.
Nếu bỏ qua điều kiện , số quỹ đạo là , và ta cần tính số quỹ đạo không thoả mãn.
Một quỹ đạo như vậy phải có lúc đi lên phía trên đường . Xét điểm đầu tiên quỹ đạo chạm đường , giả sử đó là . Lúc lấy đối xứng quỹ đạo từ đến qua đường , tức là đổi mỗi bước sang phải thành bước lên và mỗi bước lên thành bước sang phải. Khi đó điểm biến thành , nên toàn bộ quỹ đạo biến thành một quỹ đạo từ đến .
Ngược lại, với một quỹ đạo bất kỳ từ đến , vì hoành độ cuối lớn hơn tung độ cuối nên quỹ đạo có một điểm đầu tiên nằm trên đường . Đối xứng đoạn đầu đến điểm đó qua ta thu lại duy nhất một quỹ đạo từ đến đã đi lên phía trên . Do đó đây là một song ánh.
Vì quỹ đạo từ đến có đúng bước lên trong tổng số 2026 bước, số quỹ đạo không thỏa mãn là . Vậy với đúng đỉnh xanh, số cách tô thỏa mãn là , với quy ước . Cộng từ 0 tới 1013, ta được số cách tô thoả mãn là
Nhận xét. Bài toán trên sử dụng ý tưởng quỹ đạo tương tự với Hùng Yên TST 2026. Bài toán: Cho số nguyên dương . Hai bạn và cùng tham gia một trò chơi gồm lượt. Mỗi lượt, họ độc lập giải cùng một câu đố và kết quả là mỗi người chơi hoặc giải được hoặc không giải được. Đặt lần lượt là tổng số câu đố mà giải được trong lượt đầu tiên. Hỏi có bao nhiêu kịch bản có thể xảy để đạt giải đặc biệt, nghĩa là sau khi kết thúc toàn bộ lượt chơi, không chỉ giải được nhiều câu đố hơn (), mà còn chưa bao giờ để bỏ xa quá một câu trong suốt quá trình ()?
a) Trước hết xét một dãy gồm đỉnh thẳng hàng. Gọi là số cách tô đỏ, xanh các đỉnh sao cho không có hai đỉnh xanh liên tiếp.
Ta có , . Với , xét màu của đỉnh cuối cùng. Nếu đỉnh cuối màu đỏ thì đỉnh trước có cách tô. Nếu đỉnh cuối màu xanh thì đỉnh ngay trước nó bắt buộc màu đỏ, còn đỉnh đầu có cách tô. Do đó .
Trở lại với đa giác 2026 đỉnh. Xét màu của .
- Nếu màu đỏ thì là một dãy 2025 đỉnh, nên có cách tô.
- Nếu màu xanh thì do và đều kề , hai đỉnh này bắt buộc màu đỏ. Khi đó chỉ còn dãy gồm 2023 đỉnh cần tô, nên có cách.
Vì vậy số cách tô là .
b) Ta biểu diễn mỗi cách tô bằng một quỹ đạo trên lưới ô vuông, xuất phát từ như sau:
- Nếu được tô đỏ thì đi một bước sang phải.
- Nếu được tô xanh thì đi một bước lên trên.
Sau bước, hoành độ của điểm đang đứng bằng số đỉnh đỏ trong , còn tung độ bằng số đỉnh xanh. Vì vậy điều kiện của bài toán tương đương với việc quỹ đạo luôn nằm trên hoặc phía dưới đường thẳng .
Giả sử có đúng đỉnh xanh, với . Khi đó có đỉnh đỏ, nên quỹ đạo đi từ đến bằng bước sang phải và bước lên.
Nếu bỏ qua điều kiện , số quỹ đạo là , và ta cần tính số quỹ đạo không thoả mãn.
Một quỹ đạo như vậy phải có lúc đi lên phía trên đường . Xét điểm đầu tiên quỹ đạo chạm đường , giả sử đó là . Lúc lấy đối xứng quỹ đạo từ đến qua đường , tức là đổi mỗi bước sang phải thành bước lên và mỗi bước lên thành bước sang phải. Khi đó điểm biến thành , nên toàn bộ quỹ đạo biến thành một quỹ đạo từ đến .
Ngược lại, với một quỹ đạo bất kỳ từ đến , vì hoành độ cuối lớn hơn tung độ cuối nên quỹ đạo có một điểm đầu tiên nằm trên đường . Đối xứng đoạn đầu đến điểm đó qua ta thu lại duy nhất một quỹ đạo từ đến đã đi lên phía trên . Do đó đây là một song ánh.
Vì quỹ đạo từ đến có đúng bước lên trong tổng số 2026 bước, số quỹ đạo không thỏa mãn là . Vậy với đúng đỉnh xanh, số cách tô thỏa mãn là , với quy ước . Cộng từ 0 tới 1013, ta được số cách tô thoả mãn là
Nhận xét. Bài toán trên sử dụng ý tưởng quỹ đạo tương tự với Hùng Yên TST 2026. Bài toán: Cho số nguyên dương . Hai bạn và cùng tham gia một trò chơi gồm lượt. Mỗi lượt, họ độc lập giải cùng một câu đố và kết quả là mỗi người chơi hoặc giải được hoặc không giải được. Đặt lần lượt là tổng số câu đố mà giải được trong lượt đầu tiên. Hỏi có bao nhiêu kịch bản có thể xảy để đạt giải đặc biệt, nghĩa là sau khi kết thúc toàn bộ lượt chơi, không chỉ giải được nhiều câu đố hơn (), mà còn chưa bao giờ để bỏ xa quá một câu trong suốt quá trình ()?