MOG 2018 Q4
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.
Explain why no more than 67 houses can be painted yellow.(4 marks)
In how many different ways may the houses be painted if exactly 67 are painted yellow?
(6 marks)
Mathematical Olympiad for Girls 2018, Question 4. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: (b) 34
Commentary
It is important to first set up some notation for a solution, it would be sensible to denote a house that is to be painted white by \(W\) and a house that is to be painted yellow by \(Y\).
For the first part of the problem if you try to come up with an example with as many houses painted yellow as possible you may end up with something like \(WYYWYY\dots WYYWYYW\), which contains exactly 66 yellow houses. When you try to improve on this you might come up with something like \(YWYYWY\dots YWYYWYY\) or perhaps \(YYWYYW\dots YYWYYWY\), both of which contain exactly 67 yellow houses. The subtlety comes in when you try to explain precisely why a 68th house cannot be painted yellow, no matter what colouring you choose. As no three neighbouring houses may be the same colour it makes sense to consider groupings of three houses at a time. To construct a proof it will be helpful to consider groupings which do not overlap. The simple groupings consisting of houses \((2, 3, 4), (5, 6, 7), \dots, (95, 96, 97), (98, 99, 100)\), which leave the first house on its own in a group of one, turn out to work well.
For the second part of the question the same groupings can be used to great effect. It is important that all allowable combinations of colourings for three houses are considered and writing these down is a good start. For a group of three houses, with one painted white and two painted yellow we have the colourings \(YYW\), \(YWY\) and \(WYY\). To work towards a solution we must consider how these colourings interact with one another. For example, can one colouring precede or follow another?
We shall denote a house that is to be painted white by \(W\) and a house that is to be painted yellow by \(Y\).
Let us number the houses 1 to 100 from left to right and consider the 34 blocks \((1), (2, 3, 4), (5, 6, 7), \dots, (95, 96, 97), (98, 99, 100)\). As no three neighbouring houses can all be the same colour there must be a maximum of two yellow houses in each of the 33 blocks of three houses. From this we can deduce that at most \(1 + 2 \times 33 = 67\) houses could 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\).
Each block of three houses could be painted \(YYW\), \(YWY\) or \(WYY\). Note that the second colouring cannot be followed by the first and the third colouring cannot be followed by either the first or the second. This means that as soon as we choose the third colouring for one of our blocks of three houses then all successive blocks must have the same colouring. The first house must be painted \(Y\), as demonstrated in part (a), and the next block of three could be painted \(YWY\) or \(WYY\). The only choice we have is when we first paint a block \(WYY\), this could be in any of the 33 blocks of three houses or not at all. This means there are 34 different ways to paint the 100 houses, which adhere to the strict requests of the residents.
Solution © UK Mathematics Trust, from the MOG 2018 solutions.