2019/20 AHSMC Part 1 Problem 13

Problem 13 of 16

Each of the integers $1,2,3,\ldots,9$ is coloured either blue, yellow or red such that any two numbers whose difference is odd do not have the same colour. It is not required that all three colours be used. The number of acceptable possibilities is

Show solution

Solution

The condition of the problem holds if there is no pair of an even number and odd number in the same color. This can be obtained if all the odd numbers are coloured first in blue (and then all in red and again all in yellow) and all four even numbers in the other two colours, or, all the even numbers are coloured first in blue (and then all in red and again all in yellow) and all five odd numbers in the other two colours. There is a total of $3 \cdot 2^4 + 3 \cdot 2^5 = 144$ possibilities but $3 \cdot 2 = 6$ colourings where only two colours are used are double counted. Thus there are $144 - 6 = 138$ possibilities. The answer is (B).

University of Alberta

Answer choices

Solution