Maths Olympiad Prep

Library / /240 of 241

, 2025

Combinatorics Difficulty 4.9 AIME Find the answer Canada

Rita is colouring a picture of a flower. She has already coloured
the centre and the stem of the flower, as shown. Next, she will colour
each of the six petals with exactly one of the colours: red, orange,
yellow, and blue. No two neighbouring petals can be the same colour and
not all four colours need to be used. There are NN different-looking ways in which Rita
can colour the petals. What are the rightmost two digits of NN?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Throughout the solution, we will use diagrams like
the one below to represent a way to colour the flower. Each circle
corresponds to a petal, and the capital letters RR, OO, YY, and BB represent the colours red, orange,
yellow, and blue, respectively. For example, the diagram representing
the petals coloured red, blue, yellow, blue, red, orange starting at the
top petal in clockwise order is

[[IMAGE0]]

For now, we will count the number of ways to colour the petals
according to the rules with the additional assumption that the top petal
is red. Using this assumption, we will consider cases based on how many
times the colour red is used.

Before reading on, you should convince yourself that it is not possible
to colour four or more petals red without causing two neighbouring
petals to be coloured red.

Case 1: Red is used three times.

Because two neighbouring petals must have different colours, there is
only one choice of which three petals are coloured red

[[IMAGE1]]

The rest of the petals can be coloured in any way using the other
three colours, so there are 3×3×3=273\times3\times3=27 ways to colour the
petals in this case.
Case 2: Red is used two times.

There are three possibilities of which two petals are coloured
red.

[[IMAGE2]] [[IMAGE3]]
[[IMAGE4]]

Consider the second of these configurations.

The two petals that neighbour the top red petal can each be coloured any
of the three remaining colours.

Once these two (independent) choices are made, the remaining two petals
can be independently coloured using one of exactly two possible
colours.

Therefore, the colouring of the middle configuration can be completed in
3×3×2×2=363\times3\times2\times2=36 different
ways.

In the first configuration, the petal between the two red petals can be
coloured in any of 33 ways, and this
choice is independent of the way the other three petals are
coloured.

The other three petals can either be coloured three different colours
(xx, yy, and zz), or they can be coloured using two
different colours (u(u and vv), as shown below:

[[IMAGE5]] [[IMAGE6]]

If three colours are used, then there are 66 ways to choose them since we can choose
xx in any of 33 ways, then choose yy in any of two ways, and then zz is forced.

If two colours are used, then there are 33 ways to choose uu and then 22 ways to choose vv, for a total of 66 ways.

Thus, there are 6+6=126+6=12 ways to
colour the three petals (other than the one between the two red
petals).

Since there are 33 ways to colour
the petal between the red petals, there are 3×12=363\times12=36 ways to complete the
colouring for this configuration.

The third configuration can be coloured in 3636 ways as well, so there are 36+36+36=10836+36+36=108 ways to colour the petals in
this case.
Case 3: Red is used one time.

We can imagine colouring the petals one at a time in the clockwise
direction starting from the red petal.

There will be 33 choices for the
first petal since the only restriction is that we cannot use red.

The next petal has 22 options since
it cannot be the same colour as the previous petal, but it also cannot
be red.

Continuing in this way, there are 22
options for the 44th
petal, and 22 options for the 55th petal.

The final petal also has two options since its two neighbours have two
different colours. This is because we have not used red other than to
colour the top petal.

Therefore, there are 3×2×2×2×2=483\times2\times2\times2\times2=48 ways to
colour the petals in this case.

From the three cases, we get a total of 27+108+48=18327+108+48=183 ways to colour the petals
so that the top petal is red.

There are 44 choices for the colour
of the top petal and each will lead to a count of 183183.

Therefore, the number of ways to colour the petals according the the
given rules is 4×183=7324\times183=732.

The last two digits of 732732 make the
integer 3232, which is the answer to
the question.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.