Last week the UK held its annual training and selection camp in Cambridge. This week, four of the students have been attending the European Girls’ Mathematical Olympiad. 2018 is the seventh edition of this prestigious competition, and is being held in Florence.
You can find very many details about the competition, and observe the UK’s excellent performance (with particular congratulations to Emily, who obtained a perfect score) at the competition website. A short article about the team in the TES can be found here.
Part a) would have been more immediate if the set A had been defined as
as this is instantly suggestive of a telescoping product such as
I found part b) to be one of the most difficult sections of the paper. It builds on the idea that given an expression for x as a product of elements of A, and an expression for y as a product of elements of A, we can combine these (ie take the product of the products!) to get an expression for xy as a product of elements of A. This yields , and so the task is to show that sometimes this isn’t the most efficient way to proceed.
I tried a couple of things, like trying to bound f(p) below when p is a prime. This wasn’t ludicrous, as one would certainly need to use a term somewhere in the product so that it is divisible by p. However, this didn’t go anywhere, and nor did investigating f(n!). Perhaps others had more success down these avenues.
But as a general rule, if an abstractly-defined function is typically hard to calculate, then classes where you can calculate it are likely to be extra valuable. Here, powers of two make life particularly easy. We have , and so is a valid product. And we can’t possibly achieve as a product of fewer terms than this, because 2 is the largest element of A. So . Note that this is already way better than the bound we would have achieved from our argument in part a), which yields .
My next observation was that a similar argument and a natural construction gives . But this can be extended so that when , we have and in fact there is equality exactly for
In particular, note that all of these are even except . It may well be the case that we don’t need this extension, but before you’ve solved the problem you don’t know how much you’ll have to extend each idea!
I had a feeling that this meant was a strong candidate to satisfy the requirements, and that almost any factorisation would work. I suspect many students at this point did some refinement of choice of n, but I want to stay abstract, and use the extended observation (*). Since is certainly not always prime, let’s focus on the infinitely many values n where it has a factorisation as , and consider whether a or b can achieve equality at (*). We’d better introduce the notation
So , and so . But similarly, , so . We obtain
which is kind of what I’d been hoping for when I started this analysis. Now, we have
with equality precisely if both satisfy the equality conditions at (*). But are odd, and so we have equality at (**) precisely if . So we have a resolution to the problem whenever can be non-trivially factorised in any way other than , so we have a rich (and certainly infinite) class of suitable (x,y).
An obvious remark. The jury will never choose contestant i if she has fewer than i contestants in front of her unless they are forced to. They are only forced to if everyone has this property. So we ignore the second dashed bullet point, as it just tells us when the process ends. And with a little further thought, the process ends exactly when the contestants are in correct order.
I suspect part a) of this may end up featuring on future examples of our interactive write-up clinic, where students are challenged to produce technically-correct arguments for obvious but awkward mini-problems. The location of contestant is probably a good starting point.
For part b), you have to find an optimal construction, and prove that it’s optimal. At national and junior olympiad level, students often forget that they have to supply both of these components. At international level, the challenge is to work out which one gives the entry into the problem. I would say that about two-thirds of the time, either the optimal construction is very obvious, or is best attacked after you’ve had some insight into the bound. For this question (and again it’s just my opinion), I felt it was all about the construction. I made absolutely no progress by aiming for bounds. Whereas the construction offers plenty of insight into how to prove the bounds, and so once I had it, I found it quick.
The usual rules apply. An optimal construction is going to have to be neat to describe. It’s very unlikely to have millions of cases. Intuitively, it seems reasonable that starting the contestants in reverse order gives the jury the greatest possible ‘elbow room’ to squeeze moves into the procedure. Perhaps you tried to prove this directly, by coupling a procedure starting from arbitrary order with a corresponding procedure starting from reverse order? Well, I found that very hard, and perhaps you did too.
However, that doesn’t mean it’s the wrong construction! The key question is, what to do about contestant ? Well, essentially nothing. This contestant can never be moved. So when do we start allowing other contestants to pass her? It seemed natural to let the other contestants do as much as possible among themselves first. That is
where denotes lots of moves. At this point, what to do next stood out for me, namely that one could use at the start to put all the others back into reverse order, while moving to the back. That is
You might have tried other things first, but once you notice this, you just know it has to be right. It’s just too elegant a construction, and it looks like the sort of thing one prove will be optimal, because the overall process
incorporates the corresponding process for n-1 (twice, in fact) and so induction is very accessible both for calculating the total number of moves. We conjecture that this is indeed the optimal process, and under this assumption, with the number of moves, we would have , from the three stages of the process, from which, after looking at small values,
I started by saying that the construction was the hard part of this problem. Well, that doesn’t mean the bound is easy. But at least with a construction in hand, you can make observations that might inform a bounding argument:
- observation 1: contestant never jumps;
- observation 2: in the optimal construction, by induction doesn’t jump in the outer phases, so in fact jumps only once, ie during the middle phase;
- observation 3: contestant doesn’t jump very often, and in fact can only jump after at least one of and have ended up in front of her. Since we’ve established that don’t jump very often themselves, this gives a bound on the number of times .
There is still work to do here, and errors with could easily creep in. But I still hold fast to my original claim that the construction was the hard part here. Or at least, the rough form of the construction. I guess it’s possible that one would have started making observations like the three above without a construction in mind, but I think it’s unlikely. Anyway, I leave for you the final details of the bounding argument, which involves formally transcribing observation 3, proving it, then generalising it to jumps of and so on.
One of the exercises I have been setting to UK students recently is to produce short solution digests, which manifest any key ideas of the solution abstractly and briefly enough to resonate in the future. I’m a little tired of domino tiling problems, so I’ll do one of these here. This will be slightly longer than if I were not writing for a (small) audience.
Double-counting the total value by rows/columns and by dominos shows there are dominos in a balanced configuration. When n=3, we can achieve k=1, and by tiling copies of this down the main diagonal, can extend to . For , we must have ie , but in fact k=3 is achievable, by tiling the main diagonal with copies of small boards for which k=3 can be constructed with a bit of trial-and-error.
The double-counting idea at the start is the nice part of the problem. The construction is a bit annoying, but saving ourselves work by building up large examples from copies of small examples is a useful motif to have in mind.
This question has lots of clues in the statement. It would, for example, be pretty surprising if the answer were ‘no’ to part b) given the setup in part a).
My confession is that I wasted lots of time on part a) not using the option m=0, which was foolish given that it’s clued from part b) that one needs to use the option m=0. My thought had been to consider some integer y, and ask which integers x were banned (if we were aiming for contradiction in part a)). For part a), it gets harder if t is smaller, so I found it helpful to think of t as . Anyway, if you struggled on part a), maybe worth reviewing whether you were definitely trying to solve part a), and not accidentally using the setup that really addressed part b)!
Some people have shown me solutions to part a) that carry an air of magic, by placing all the key steps (such as (*) to follow) in the language of the original setup. Let’s try to be cleaner. The key is to consider m=0. Since m=0 is included, we know that whenever x<y, we must have
Maybe you just have a gut feeling that this can’t be possible if you have enough xs and ys? But either way, choosing to focus on (*) is the key step, because once you know you have to prove the result based on this, it’s not too hard. I prefer addition to multiplication, so one might as well take logs (since does it really look like we’re going to use heavily the integer property now?) to obtain
for all in some large finite collection, where . You should now have a strong gut feeling that this is impossible. You have an arbitrarily large collection of real numbers which have to be close to each other pairwise, but never too close pairwise. How to finish the argument is a matter of taste.
For part b), assuming we’re aiming for the answer ‘yes’, we probably want to construct it one step at a time, and you want to think of to make life as hard as possible.
Now, suppose you have so far. What next? Well if we could have
for all , that would be perfect. We can often solve sets of coupled residue equations like this using the Chinese Remainder Theorem. (Recall of course that the solutions themselves are rarely important – the fact that they exist is enough!) A couple of things go wrong with trying this crudely:
- If is odd, then is not an integer…
- If we correct this by asking for , then there’s a chance we might still be within the t-window around a multiple of .
- Unless we are going to make complicated demands on the residues, to use CRT it would be easier if all the s were coprime.
One option is to give up. But actually all these objections can be handled with fairly small alterations. Can you see how the second objection can be overcome by an appropriate choice of ? Remember that t is fixed right at the start, and cannot be equal to 1/2. Is the third objection actually an objection any more? If it is, can we fix it?
Anyway, I guess P6 was my favourite non-geometry question on the paper, though, that’s far from relevant. P5 was pretty neat too, but who knows whether a follow-up geometry post will materialise soon.