education

# Did you solve it? Are you smarter than Britain’s teenage brainiacs?

Earlier today I set you the following two puzzles. The first is from the UK’s Mathematical Olympiad for Girls:

Painting the houses

Each of 100 houses in a row are to be painted white or yellow. The residents are quite particular and request that no three neighbouring houses are all the same colour.

(a) Explain why no more than 67 houses can be painted yellow.

(b) In how many different ways may the houses be painted if exactly 67 are painted yellow?

Solution

(a) Let us number the houses 1 to 100 from left to right. Divide the street up into a single house (number 1) and 33 blocks of three neighbouring houses: (2, 3, 4), (5, 6, 7), . . ., (95, 96, 97), (98, 99, 100).

Since no three neighbouring houses can all be the same colour, for each block of three neighbouring houses, there must be a maximum of two yellow houses. Thus the maximum number of yellow houses is 2 for each of the 33 groups of 3, and one extra for the first house. i.e at most (2 × 33) + 1 = 67 houses can be painted yellow.

Note: It is possible to paint exactly 67 houses yellow. One colouring that achieves this is Y followed by 33 blocks of WYY.

(b) If 67 houses are painted yellow, then for all of the 33 groups of three neighbouring houses, two houses must be yellow. In other words, they must be be painted in one of these three ways:

Note that the second colouring cannot precede the first, and the third colouring cannot precede either the first or the second. (Since otherwise you get more than two yellow houses in a row). This means that as soon as we choose the third colouring (WYY) for one of our blocks of three houses then all successive blocks must have the WYY colouring.

Now let’s get painting! The first house must be painted Y, as demonstrated in part (a), and thus the first block of three could be painted YWY or WYY.

If this block is WYY, then we know it’s WYYs all the way to the end of the street. But if this block is YWY, then the choice for the next block is either YWY or WYY. Again, if this block is WYY, then we know it’s WYYs all the way to the end, but if it’s YWY we get a choice for the following block.

So, the only choice we have is when to first paint a group of three neighbouring houses WYY. This could be in any of the 33 blocks of three houses, or in none of them. It follows that there are 34 different ways to paint the 100 houses if 67 are to be painted yellow.

The second (much harder) problem was frome last week’s European Girls’ Mathematical Olympiad.

Fantabulous numbers

The number 2021 is fantabulous. For any positive integer m, if any element of the set {m, 2m + 1, 3m} is fantabulous, then all the elements are fantabulous. Does it follow that the number 20212021 is fantabulous?