Each of the five regions in the figure below is to be labelled with a unique integer taken from the set $\{1,2,3,4,5,6,8,9,10,12,14\}$. The labelling is to be done so that if two regions share a boundary and these regions are labelled with the integers $a$ and $b$, then

- $a$ and $b$ are not both multiples of 2 ,
- $a$ and $b$ are not both multiples of 3 , and
- $a$ and $b$ are not both multiples of 5 .

In how many ways can the regions be labelled?

![](https://cdn.mathpix.com/cropped/2024_04_30_3011c729c030a190170fg-4.jpg?height=523&width=780&top_left_y=1408&top_left_x=735)
We label the regions with unknown integers $u, v, w, x, y$, as shown:

![](https://cdn.mathpix.com/cropped/2024_04_30_75c1cf70fbe3735bfd92g-15.jpg?height=525&width=769&top_left_y=266&top_left_x=735)

The given list of integers includes 4 odd integers $(1,3,5,9)$ and 7 even integers $(2,4,6,8,10,12,14)$. We proceed by focusing on $w$ and considering a number of cases:

 (i) $\underline{w \text { is even }}$

In this case, none of $u, v, x, y$ can be even, by Rule 1 .

Therefore, all four odd integers have to be used for $u, v, x, y$.

Note that 3 and 9 cannot be adjacent, by Rule 2 .

Since 3, 5 and 9 are all used among $u, v, x, y$, then $w$ cannot be 6,10 or 12 , by Rules 2 and 3 .

Therefore, $w$ can only be $2,4,8,14$.

There are 4 choices for $w$.

For each of these, there are 4 choices of placement for 3 .

Once 3 is placed, the position of 9 is determined (it must be "opposite" 3).

Once 3 and 9 are placed, there are 2 choices of position for 5 and then 1 choice for 1 .

In this case, there are $4 \times 4 \times 2=32$ possible labellings.

 (ii) $\underline{w}=3$ or $w=9$

Here, there are 2 choices for $w$.

The other possible value for $w$ cannot be used among $u, v, x, y$, by Rule 2 .

We cannot use 3 or 4 even numbers among $u, v, x, y$, otherwise two even numbers would be adjacement.

Therefore, at most 2 even numbers can be used.

But there are only 2 odd numbers left ( 1 and 5 ), so exactly two even numbers must be used and these cannot be adjacent. The even numbers used cannot include $6,10,12$, by Rules 2 and 3 (each even number used will be adjacent to $w$ (which is 3 or 9 ) and to 5). Therefore, only 2, 4, 8, 14 can be used.

There are thus 2 choices for $w, 4$ choices of placement for 5,1 choice of placement for 1 (opposite 5), $\binom{4}{2}=6$ choices for the two even numbers, and 2 ways to place these even numbers.

In this case, there are $2 \times 4 \times 6 \times 2=96$ possible labellings.

 (iii) $\underline{w=5}$

Since 2 even numbers cannot be adjacent among $u, v, x, y$, then there must be 2 or 3 odd numbers among $u, v, x, y$.

Suppose that there are 3 odd numbers among $u, v, x, y$. (These must be 1,3,9.)

Note that 3 and 9 cannot be adjacent, so must be opposite.

There are 4 choices for placement of 3, which gives 1 placement for 9 (opposite 3), and

2 choices for 1 (in either open spot).

The remaining integer will be even and cannot be 6,10 or 12 , and so there are 4 choices for the remaining spot.

In this subcase, there are $4 \times 1 \times 2 \times 4=32$ possible labellings.

Suppose that there are now 2 odd numbers among $u, v, x, y$. These two cannot be adjacent (since the even numbers cannot be adjacent), so must be opposite. Therefore any of the $\binom{3}{2}=3$ pairs from $\{1,3,9\}$ can be used.

There are 4 choices of placement for the smaller of these numbers and then the larger one is placed opposite.

The even numbers are chosen from among $\{2,4,8,14\}$, as before. There are $\binom{4}{2}=6$ choices for the pair of numbers and 2 ways of placing them.

In this subcase, there are thus $3 \times 4 \times 6 \times 2=144$ possible labellings.

In this case, there are thus $32+144=176$ possible labellings.

 (iv) $\underline{w}=1$

Since 2 even numbers cannot be adjacent among $u, v, x, y$, then there must be 2 or 3 odd numbers among $u, v, x, y$.

Suppose that there are 3 odd numbers among $u, v, x, y$.

Note that 3 and 9 cannot be adjacent, so must be opposite.

There are 4 choices for placement of 3 , which gives 1 placement for 9 (opposite 3), and 2 choices for 5 (in either open spot).

The remaining integer will be even and cannot be 6 or 12, and so there are 5 choices for the remaining spot. (Note that the even number is now opposite 5 so could equal 10.) In this subcase, there are $4 \times 1 \times 2 \times 5=40$ possible labellings.

Suppose that there are now 2 odd numbers among $u, v, x, y$. These two cannot be adjacent (since the even numbers cannot be adjacent), so must be opposite. Therefore any of the 3 pairs from $\{3,5,9\}$ can be used.

If 3 and 9 are used, there are 4 choices of placement for 3 and then 1 choice of placement for 9 .

The even numbers are chosen from among $\{2,4,8,10,14\}$, as before. There are $\binom{5}{2}=10$ choices for the pair of numbers and 2 ways of placing them.

In this subcase, there are thus $4 \times 10 \times 2=80$ possible labellings.

If 3 and 5 are used, there are 4 choices of placement for 3 and then 1 choice of placement for 5 .

The even numbers are chosen from among $\{2,4,8,14\}$, as before. There are $\binom{4}{2}=6$ choices for the pair of numbers and 2 ways of placing them.

In this subcase, there are thus $4 \times 6 \times 2=48$ possible labellings.

If 9 and 5 are used, there are again 48 possible labellings.

In this case, there are thus $40+80+48+48=216$ possible labellings.

Therefore, in total there are $32+96+176+216=520$ possible labellings.

ANSWER: 520

## Relay Problems

(Note: Where possible, the solutions to parts (b) and (c) of each Relay are written as if the value of $t$ is not initially known, and then $t$ is substituted at the end.)