I’m teaching a lecture course at Technion this coming semester, which is going to limit opportunities for travel somewhat for the next three months or so. It was therefore nice to take advantage of the new ultra-cheap Luton-Tel Aviv connection on Wizzair to make a whistlestop weekend trip to Cambridge. It was lovely to catch up with friends, colleagues and former students, including some people who fit into all those categories.
Among my various mathematical diversions over the weekend, about thirty of us spent most of Sunday marking the 2018 edition of the UK’s Mathematical Olympiad for Girls (MOG). You can find the paper without solutions here, and the paper with official solutions and commentary here.
I have had several blog posts on probabilistic, competitive and educational topics queued up over this summer which has alternated between extreme busyness and lethargy, but this felt like a good opportunity to break the drought and both start and finish a post on the same day!
I’m going to write some thoughts about Question 4, mostly about part a), which I hope might be useful to future students who perhaps find this post while preparing for next year’s edition of the competition. Here’s the statement:
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 ways may the houses be painted if exactly 67 are painted yellow?
Of all the questions on the paper, based on the fraction of the scripts which I saw, I suspect Q4a) is the one for which the most candidates will have scored significantly fewer points than they’d been hoping for.
I think this illustrates some useful guidance for maths competitions, and also illuminates some differences between maths and other subjects which candidates might not have thought about.
Many students wrote that because three houses in a row cannot be yellow, the way to get as many yellow houses as possible is to use a YYWYYW… pattern. Since 100 is not a multiple of three, you have to work out what to do with the final house, after you’ve coloured 99 using the pattern, and sometimes you can colour it yellow, and sometimes you can’t.
Finding and proving results about maxima
Before focusing on the qualities of this argument, it’s worth returning to the question statement. It’s in two parts, and (assuming the answer to the second part isn’t “none“) then the overall goal is to find the maximum number of yellow houses, and to count the number of ways to achieve this maximum number, presumably by characterising them somehow. If the question had just asked us to find the maximum, and had not told us what it is, we would have to:
- Decide on a value M, and show that there is a configuration with exactly M yellows.
- Show that no value >M of yellows is possible.
Note that, apart from deciding on the value of M, which really has to come at the start of the argument, you can do these steps in either order. And if you want to find the number of configurations achieving the maximum, you have to:
- Decide on a value M, and count the number of configurations with exactly M yellows, and check that this is positive!
- Show that no value >M of yellows is possible.
Again, you can perform these steps in either order. If the question is posed like this (with M unknown), you have no idea as you are attempting the paper whether finding the value of M is supposed to be easy or supposed to be a really significant part of the attack on the problem, so starting your solution with a sentence like “I’m going to show that M is the maximum” and continuing by giving your proof an exoskeleton like “First, I’ll show that M+1 (or >M) is impossible. [Do this. Then leave a gap.] Now, I’ll count the number of configurations with M yellows.” This leaves no ambiguity that you are doing the problem in the right way, and for someone reading it, it might be the case that the validity of your argument is almost instantly clear once the rough outline is established.
In any case, on MOG Q4, the question has been split into two parts deliberately, and you have been told what the value of the maximum is. In fact, the order is the opposite to what I’ve proposed in the bullet points above. But this just serves to emphasise that, even when or especially when the maximum is already given, the order of attack is not important. The two bullet points might be completely unrelated mathematical arguments, but they are certainly structurally unrelated.
Structuring your approach to MOG Q4
But, to return to MOG Q4, the first part is asking you to show that 68 or more yellow houses is not possible under the rules. The second part is where you are supposed to establish what all the 67 yellow configurations are, and on this occasion it may turn out that you re-use ideas established in part a) during the enumeration of part b).
Anyway, I’m going to repeat an earlier paragraph. Many students wrote that because three houses in a row cannot be yellow, the way to get as many yellow houses as possible is to use a YYWYYW… pattern. Since 100 is not a multiple of three, you have to work out what to do with the final house, after you’ve coloured 99 using the pattern, and sometimes you can colour it yellow, and sometimes you can’t.
Now that we’ve established some general principles, we can see why some students may have got themselves into knots that weren’t directly relevant to the question.
- The blue comment “sometimes you can colour it yellow, and sometimes you can’t” is just not relevant because at this stage we are trying to show that 68 (or more) is not possible. If at any point it becomes a discussion of whether one class of configurations leads to 66 or 67, this can’t be relevant to showing that 68 is not possible.
- The green sentence “because three houses in a row cannot be yellow, the way to get as many yellow houses as possible is to use a YYWYYW… pattern” is, as written, true, but dangerous. Because it’s not precise. As becomes clear in part b), there are actually lots of ways to get as many yellow houses as possible, and while all of them have this pattern most of the time, it is certainly not the case that you use this pattern for the first 99, and then make a decision about the final house. (Since this only gives one configuration.)
- The fact that 100 is not a multiple of 3 is crucial to the problem. If it had asked about 99 houses, you would have had more room just to work with a breakdown into 33 groups of three houses, and some of the argument would have been simpler. So an argument saying that 100/3 = 66.66…, which we can round up to 67 is not really explaining what’s going on. Of course we have to have a whole number of houses, but why you round up rather than down is all about the rules of colouring.
- Finally, the notion of an ‘iterated maximum’ is a generally erroneous argument. In such an argument, you argue that the maximum way to attack a subproblem is X, and once you have X, clearly the maximal way to finish is Y, so the maximum total is X+Y. This is wrong, because of course it’s possible there might be a non-maximum way X*>X to attack the subproblem, from which you can finish in Y*<<Y, so the total ends up being lower overall.
- In this example, the problem is not that the green statement is an erroneous iterated maximum. It’s just sounds like one. It can easily be made into a non-erroneous argument. But as soon as you start with a pattern, but then consider how to add something onto the end of it, you have essentially fallen into this trap unless you very carefully explain why taking the maximum for the first 99 houses plus the maximum for the final house must give a maximum overall.
Because the condition is a local one (meaning it tells you about rules governing two or three adjacent houses, not a global one affecting all houses in the street), it’s good to use a local argument. In the example:
notice that it is not true that in every group of three consecutive houses, two are Yellow. (Look between the *asterisks*.) However, it is true that in every group of three consecutive houses, at most two are Yellow, and so in particular if we split as shown above, there are at most two yellows in all the three-brackets, and at most one at the end, giving at most 67 in total. The fact that the pattern changes from YYW to YWY does not affect this argument.
If you set it up this way, then this gives you a good headstart on part b). You might notice that the pattern can change from YYW to YWY (as in the previous example), but not the other way round. And what about WYY? Can this ever come up? You need to justify both aspects of this, and then clarify how to count the number of places where the pattern could change, having now established that all configurations have this form.
The question setters produced a beautiful paper, and it was clear that one of their goals was to use multiple parts sensibly so as to suggest entrance routes into the problem. Many many students successfully used the factorisations discussed in the first parts of Q1, and even those who didn’t succeed seemed mostly to be trying to find differences of squares, rather than prime factors out of nowhere.
This principle applied elsewhere though, and in particular on Q3. I think some students thought Q3a) was supposed to involve three calculations, but in fact it required just giving a combinatorial justification for why the set of objects counted by b can be split into two, where one subset is counted by c and one by d. This argument, which might have been familiar to some through knowledge of Pascal’s triangle, applies equally well at other squares in the box, and also in three dimensions. If you don’t have the gap in the middle of the house, you can immediately apply this argument to Ghastly in part b). But in fact, even with the gap, you can make this work, because you are only really counting across *places you could have been just before in your path*, and the gap means that sometimes this is smaller than it would be without the gap.
There were other ways to do the question, such as counting all paths, and all paths through the gap, but all attempts using a b=c+d+e argument seemed quick and successful.
A couple of other tips to bear in mind on these sorts of questions.
- When you’re deep in a calculation, it’s easy to forget that you started with a problem of some kind, and you should always go back to check that your answer makes sense in the context of the problem! Even if fits the algebra, you should not have any of the following (among many other examples that can emerge after a small conceptual or calculation error):
- A negative radius for a circle
- A non-integer number of configurations
- A probability >1
- You should also check for potential symmetries. While it’s dangerous to use symmetry excessively until you’re sure the situation genuinely is symmetric, it can be your friend in reducing errors. For example, maybe you found the final count in the far corner for Ghastly the ghost to be eg 18+16+12? But the three adjacent-to-far-corner cells are clearly equivalent from the starting point. Any difference between them can only be a feature of the argument you are trying. So they should have the same path count, and probably you made a small error in one of them.
- It’s also worth checking your answers feel roughly right for magnitude. In particular, again on Q3 , if you get a very large answer for part b), you should try to check against other options. How many total paths are there? (Ie, ignoring the gap.) If your answer is much bigger than this, you must have made a small mistake, probably multiplying where you should have been adding. It might well, for example, not feel right if you end up showing that the number of paths is greater than the number of atoms in the universe. This applies equally well for Q4. Note that 67! is an extremely large number, and is larger than 2^100, which is the total number of colourings without observing any of the consecutive rules, let alone the maximum condition.
- As a final point, it was good to see that many candidates were making a bona fide effort to get as many marks as possible. I would say, however, that just writing down a speculative answer is often less helpful than a single sentence explaining what you are trying to do. Pretty much any comment on patterns and a division into cases for Q4 would be useful, even if it wasn’t completely correct, whereas a guess at eg or similar for the final answer is probably less valuable, and draws attention to what you haven’t done, rather than any progress that you really have made.
Anyway, I hope that was interesting at some level to some girls potentially interested in taking MOG or any other challenging mathematics in the future.