HMMT 二月 2003 · COMB 赛 · 第 5 题

HMMT February 2003 — COMB Round — Problem 5

We wish to color the integers 1 , 2 , 3 , . . . , 10 in red, green, and blue, so that no two numbers a and b , with a − b odd, have the same color. (We do not require that all three colors be used.) In how many ways can this be done?

解析

We wish to color the integers 1 , 2 , 3 , . . . , 10 in red, green, and blue, so that no two numbers a and b , with a − b odd, have the same color. (We do not require that all three colors be used.) In how many ways can this be done? Solution: 186 The condition is equivalent to never having an odd number and an even number in the same color. We can choose one of the three colors for the odd numbers and distribute the other two colors freely among the 5 even numbers; this can be done in 5 3 · 2 = 96 ways. We can also choose one color for the even numbers and distribute the other two colors among the 5 odd numbers, again in 96 ways. This gives a total of 192 possibilities. However, we have double-counted the 3 · 2 = 6 cases where all odd numbers are the same color and all even numbers are the same color, so there are actually 192 − 6 = 186 possible colorings.