RMM 2017 – Problems 2, 3 and 6

In the previous post, I discussed Problems 1, 4 and 5 from this year’s Romanian Master of Mathematics competition. In this post, I discuss the harder problems (modulo my subjective appreciation of difficulty).

Problem 2

Determine all positive integers n satisfying the following condition: for every monic polynomial P of degree at most n with integer coefficients, there exists a positive integer k \leq n, and (k+1) distinct integers x_1,\ldots,x_{k+1} such that

P(x_1) + P(x_2) + \cdots + P(x_k) = P(x_{k+1}).

Parsing this question deserve at least a moment. Straight after a first reading, I find it worth writing down any key quantifiers which I might forget later. Here, it’s the words at most. If you want to show the statement holds for n=2, you need to investigate monic polynomials with degree zero, one and two. You should also make sure that any instances of x_i really are always distinct.

This matters in competitions! Two of our contestants failed to get the mark for showing n=2 works, precisely because of not checking the linear case, and a third could have lost it for using examples which are sometimes not distinct. On hard papers, one mark actually is the difference between triumph and frustration. And of course it matters outside competitions too, since small cases are exactly what your reader might examine first, to check they understand the problem posed, so it’s not a good place for awkward errors.

I started by trying to show that it couldn’t possibly happen that every polynomial with degree at most n had this property, for some combinatorial reason. For example, that if every set of distinct integers could only be a solution set for a small number of polynomials, then we would end up with not enough polynomials. But I couldn’t make this work at all; every bound ended up heavily in the wrong direction.

The next natural question is, does a typical polynomial of degree at most n have this property? But choosing a typical polynomial is hard, so in fact I asked, do the simplest polynomials of degree at most n have this property? I think the simplest polynomials of degree at most n are \{1,x,x^2,\ldots,x^n\}. Under what circumstances does

x_1^m + \ldots x_k^m = x_{k+1}^m, (1)

have solutions in distinct integers? Famously, when k=2 and m\ge 3 this is a very very hard problem indeed. So the first point is that it though it might be useful to use Fermat’s Last Theorem, it would be foolish to pursue a strategy which, if successful, would have a proof of FLT as a sub-problem. At least, it would be foolish if the aim was to finish this strategy within a few hours.

So my main comment on this question is meta-mathematical. If lots of attempts at general arguments don’t work, there must be some special example that does it. And what properties do I want this special example to have? Maybe one might have thought of this from scratch, but my motivation came from (1) in the case m=p-1. Then, by Fermat’s Little Theorem, all the summands are equal to 1 or 0 modulo p. If k>p, then after discounting any uniform factors of p, we obtain a congruence equation which is, in informal terms,

\left(0\text{ or }1\right)+\ldots+\left(0\text{ or }1\right) \equiv \left(0\text{ or }1\right).

This looks really promising because it’s quite restrictive, but it’s still just a bit annoying: there are quite a few solutions. But it does give us the right idea, which is to find a polynomial P for which P(x)\equiv 1 modulo n. The equation 1+\ldots+1\equiv 1 modulo n has solutions only if the number of summands on the LHS is 1 modulo n. So in this context, this reduces to showing that P is, additionally, injective on the integers, ie that P(x)=P(y) only when x=y.

It’s a nice exercise to show the existence of polynomials which are constant modulo n, and a good problem to work out how to force injectivity. If a polynomial is increasing everywhere, then it is certainly injective, and so the problem ends up being slightly easier in the case where the degree is odd than when the degree is even, but this is a nice conclusion to a nice problem, so I’ll save it for any interested readers to finish themselves.

Problem 3

Let n be an integer greater than 1 and let X be an n-element set. A non-empty collection of subsets A_1,\ldots, A_k of X is tight if the union A_1 \cup \dots \cup A_k is a proper subset of X and no element of X lies in exactly one of the A_is. Find the largest cardinality of a collection of proper non-empty subsets of X, no non-empty subcollection of which is tight.

Note. A subset A of X is proper if A\neq X. The sets in a collection are assumed to be distinct. The whole collection is assumed to be a subcollection.

By Neel Nanda:

If |X|=n, there are 2^n possible subsets, so at first glance the answer could be a variety of things, from a linear to an exponential function of n, each of which would suggest a different approach. So the first step is to conjecture an answer, and by examining small cases it seems impossible to do better than 2n-2. There are several natural constructions for this bound, such as n subsets of size (n-1) and (n-2) subsets of size 1, so we guess this to be our answer (which later turn out to be right!).

From here, a solution is deceptively simple, though empirically the five full solutions in the contest show that it was by no means easy to find. We proceed by induction on the size of X, and want to show that any collection of subsets S has size at least (2n-2). By assumption all subcollections are not tight, so if the union of a subcollection is not the whole set X, then there is an element which appears in exactly one subset. This is a useful result, so we’d like to force a subcollection whose union is not the whole set X.

One way to guarantee that the union of a subcollection is not X is by taking the subcollection of all subsets not containing some element b. So there is some element c which appears in only one subset not containing b. If we choose b so that it’s the element contained in the fewest subsets of S, c is in at least as many subsets of S, but in only one subset not containing b. This means that at most one subset containing b doesn’t contain c. This is useful, because after removing at most 2 subsets (the coefficient of n in 2n-2, importantly!), we now have that every subset in S either contains both b and c or neither. This means that we can replace the pair (b,c) with a new element d, to get a new collection of subsets S’ of a set X’, of size n-1, so by induction |S| \le |S'|+2\le 2n-2.

There is also the case where all subsets contain b, but we can create an equivalent collection of subsets of X \ {b} by removing b from all subsets. So again by induction we are done.

Problem 6

Let ABCD be any convex quadrilateral and let P, Q, R, S be points on the segments AB, BC, CD, and DA, respectively. It is given that the segments PR and QS dissect ABCD into four quadrilaterals, each of which has perpendicular diagonals. Show that the points P, Q, R, S are concyclic.

I thought this problem was extremely hard. The official solution starts with a ‘magic lemma’, that isn’t quite so magic if you then read how it’s used. The overall claim is that PQ, RS and AC are concurrent (or parallel), and this is proved using the fact that the radical axis of the two circles with diameters PQ and RS also passes through this point of concurrency. Hunting for key properties of subsets of points in the diagram is an important skill in hard olympiad geometry, since it exactly reflects how problem-setters produce the problems. All the more so when there is lots of symmetry in the construction. But this is a hard example – there are a lot of potentially relevant subsets of the configuration.

When you’re really stuck with how to get involved in a synthetic configuration, you might consider using coordinates. Some of the UK students have been reading some chapters of a book (Euclidean Geometry in Mathematical Olympiads by Evan Chen. I’ve only had my own copy for a couple of days, but my initial impression is very positive – it fills a gap in the literature in a style that’s both comprehensive and readable.) focusing on various analytic approaches, so James and I felt it was safer to make sure we knew what the best settings were, and how far we could take them.

You almost certainly want the intersection of PR and QS to be your origin. I wanted to set up the configuration using the language of vectors, referenced by (P,Q,R,S). This was because PQ\perp BO and so on, hence \mathbf{b}\cdot (\mathbf{q}-\mathbf{p})=0 and so on. An alternative is to use complex numbers, which makes this condition a bit more awkward, but is more promising for the conclusion. Concyclity is not a natural property in vectors unless you can characterise the centre of the circle, but can be treated via cross-ratios in \mathbb{C}. You also have to decide whether to describe the collinearity of A, B and P by expressing \mathbf{p}=\lambda_{\mathbf{p}} \mathbf{a}+(1-\lambda_{\mathbf{p}})\mathbf{b}, or via something more implicit. There definitely are not four degrees of freedom here, since specifying A certainly defines at most one valid set of (B,C,D), so one is mindful we’ll have to eliminate many variables later. We also have to account for fact that \mathbf{r} is a negative scalar multiple of \mathbf{p}, and it’s not clear whether it’s better to break symmetry immediately, or use this towards the end of a calculation.

The point of writing this was that if your initial thought was ‘this looks promising via coordinate methods’, then I guess I agree. But there’s a difference between looking promising, and actually working, and there are lots of parameterisation options. It’s certainly worth thinking very carefully about which to choose, and in this case, challenging though they were, the synthetic or synthetic-trigonometric methods probably were better.

BMO1 2016 Q5 – from areas to angles

For the second year in a row Question 5 has been a geometry problem; and for the second year in a row I presented the video solution; and the for the second year in a row I received the question(s) while I was abroad. You can see the video solutions for all the questions here (for now). I had a think about Q5 and Q6 on the train back from a day out at Lake Balaton in Western Hungary, so in keeping with last year’s corresponding post, here are some photos from those sunnier days.

bmo1-2016-q5aI didn’t enjoy this year’s geometry quite as much as last year’s, but I still want to say some things about it. At the time of writing, I don’t know who proposed Q5, but in contrast to most geometry problems, where you can see how the question might have emerged by tweaking a standard configuration, I don’t have a good intuition for what’s really going on here. I can, however, at least offer some insight into why the ‘official’ solution I give on the video has the form that it does.

bmo1-2016-q5bThe configuration given is very classical, with only five points, and lots of equal angles. The target statement is also about angles, indeed we have to show that a particular angle is a right-angle. So we might suspect that the model approach might well involve showing some other tangency relation, where one of the lines AC and BC is a radius and the other a tangent to a relevant circle. I think it’s worth emphasising that throughout mathematics, the method of solving a problem is likely to involve similar objects to the statement of the problem itself. And especially so in competition problems – it seemed entirely reasonable that the setter might have found a configuration with two corresponding tangency relations and constructed a problem by essentially only telling us the details of one of the relations.

There’s the temptation to draw lots of extra points or lots of extra lines to try and fit the given configuration into a larger configuration with more symmetry, or more suggestive similarity [1]. But, at least for my taste, you can often make a lot of progress just by thinking about what properties you want the extra lines and points to have, rather than actually drawing them. Be that as it may, for this question, I couldn’t initially find anything suitable along these lines [2]. So we have to think about the condition.

But then the condition we’ve been given involves areas, which feels at least two steps away from giving us lots of information about angles. It doesn’t feel likely that we are going to be able to read off some tangency conditions immediately from the area equality we’ve been given. So before thinking about the condition too carefully, it makes sense to return to the configuration and think in very loose terms about how we might prove the result.

How do we actually prove that an angle is a right-angle? (*) I was trying to find some tangency condition, but it’s also obviously the angle subtending by the diameter of a circle. You could aim for the Pythagoras relation on a triangle which includes the proposed right-angle, or possibly it might be easier to know one angle and two side-lengths in such a triangle, and conclude with some light trigonometry? We’ve been given a condition in terms of areas, so perhaps we can use the fact that the area of a right-angled triangle is half the product of the shorter side-lengths? Getting more exotic, if the configuration is suited to description via vectors, then a dot product might be useful, but probably this configuration isn’t.

The conclusion should be that it’s not obvious what sort of geometry we’re going to need to do to solve the problem. Maybe everything will come out from similar triangles with enough imagination, but maybe it won’t. So that’s why in the video, I split the analysis into an analysis of the configuration itself, and then an analysis of the area condition. What really happens is that we play with the area condition until we get literally anything that looks at all like one of the approaches discussed in paragraph (*). To increase our chances, we need to know as much about the configuration as possible, so any deductions from the areas are strong.

The configuration doesn’t have many points, so there’s not much ambiguity about what we could do. There are two tangents to the circle. We treat APC with equal tangents and the alternate segment theorem to show the triangle is isosceles and that the base angles are equal to the angle at B in ABC. Then point Q is ideally defined in terms of ABC to use power of a point, and add some further equal angles into the diagram. (Though it turns out we don’t need the extra equal angle except through power of a point.)

So we have some equal angles, and also some length relations. One of the length relations is straightforward (AP=CP) and the other less so (power of a point CQ^2 = AQ\cdot BQ). The really key observation is that the angle-chasing has identified

\angle PAQ = 180 - \angle \hat C,

which gives us an alternative goal: maybe it will be easier to show that PAQ is a right-angle.

Anyway, that pretty much drinks the configuration dry, and we have to use the area condition. I want to emphasise how crucial this phase in for this type of geometry problem. Thinking about how to prove the goal, and getting a flavour for the type of relation that comes out of the configuration is great, but now we need to watch like a hawk when we play with the area condition for relations which look similar to what we have, and where we might be going, as that’s very likely to be the key to the problem.

We remarked earlier that we’re aiming for angles, and are given areas. A natural middle ground is lengths. All the more so since the configuration doesn’t have many points, and so several of the triangles listed as having the same area also have the same or similar bases. You might have noticed that ABC and BCQ share height above line AQ, from which we deduce AB=BQ. It’s crucial then to identify that this is useful because it supports the power of a point result from the configuration itself. It’s also crucial to identify that we are doing a good job of relating lots of lengths in the diagram. We have two pairs of equal lengths, and (through Power of a Point) a third length which differs from one of them by a factor of \sqrt{2}.

If we make that meta-mathematical step, we are almost home. We have a relation between a triple of lengths, and between a pair of lengths. These segments make up the perimeter of triangle APQ. So if we can relate one set of lengths and the other set of lengths, then we’ll know the ratios of the side lengths of APQ. And this is excellent, since much earlier we proposed Pythagoras as a possible method for establish an angle is a right-angle, and this is exactly the information we’d need for that approach.

Can we relate the two sets of lengths? We might guess yes, that with a different comparison of triangles areas (since we haven’t yet used the area of APC) we can find a further relation. Indeed, comparing APC and APQ gives CQ = 2PC by an identical argument about heights above lines.

bmo1-2016-q5cNow we know all the ratios, it really is just a quick calculation…

[1] – I discussed the notion of adding extra points when the scripts for the recording were being shared around. It was mentioned that for some people, the requirement to add extra points (or whatever) marks a hard division between ‘problems they can do’ and ‘problem they can’t do’. While I didn’t necessarily follow this practice while I was a contestant myself, these days the first thing I do when I see any angles or an angle condition in a problem is to think about whether there’s a simple way to alter the configuration so the condition is more natural. Obviously this doesn’t always work (see [2]), but it’s on my list of ‘things to try during initial thinking’, and certainly comes a long way before approaches like ‘place in a Cartesian coordinate system’.

[2] – Well, I could actually find something suitable, but I couldn’t initially turn it into a solution. The most natural thing is to reflect P in AC to get P’, and Q in BC to get Q’. The area conditions [AP’C]=[ABC]=[BCQ’] continue to hold, but now P’ and B are on the same side of AC, hence P’B || AC. Similarly AQ’ || BC. I see no reason not to carry across the equal length deductions from the original diagram, and we need to note that angles P’AC, ACP’, CBA are equal and angles Q’AB and BAC are equal. In the new diagram, there are many things it would suffice to prove, including that CP’Q’ are collinear. Note that unless you draw the diagram deliberately badly, it’s especially easy accidentally to assume that CP’Q’ are collinear while playing around, so I wasted quite a bit of time. Later, while writing up this post, I could finish it [3].

[3] – In the double-reflected diagram, BCQ’ is similar to P’BA, and since Q’C=2P’C = P’A, and Q’B=AB, you can even deduce that the scale factor is \sqrt{2}. There now seemed two options:

  • focus on AP’BC, where we now three of the lengths, and three of the angles are equal, so we can solve for the measure of this angle. I had to use a level of trigonometry rather more exotic than the Pythagoras of the original solution, so this doesn’t really serve purpose.
  • Since BCQ’ is similar to P’BA and ABQ’ similar to CP’A, we actually have Q’BCA similar to AP’BC. In particular, \angle CBP' = \angle ACB, and thus both are 90. Note that for this, we only needed the angle deductions in the original configuration, and the pair of equal lengths.
  • There are other ways to hack this final stage, including showing that BP’ meets AQ’ at the latter’s midpoint, to give CP’Q’ collinear.

Pencils, Simson’s Line and BMO1 2015 Q5

When on olympiad duty, I normally allow myself to be drawn away from Euclidean geometry in favour of the other areas, which I feel are closer to home in terms of the type of structures and arguments I am required to deal with in research. For various reasons, I nonetheless ended up choosing to present the solution to the harder geometry on the first round of this year’s British Mathematical Olympiad a couple of weeks ago. The paper was taken a week ago, so I’m now allowed to write about it, and Oxford term finished yesterday so I now have time to write up the notes I made about it during a quick trip to Spain. Here’s three gratuitous photos to remind us all what a blue sky looks like:

And here’s the statement of the problem:

BMO1 Q5 a

and you can find the video of the solution I presented here (at least for now). Thanks to the AV unit at the University of Bath, not just as a formality, but because they are excellent – I had no right to end up looking even remotely polished.

As so often with geometry problems, the key here is to find an entry point into the problem. There are a lot of points and a lot of information (and we could add extra points if we wanted to), but we don’t expect that we’ll need to use absolutely all the information simultaneously. The main reason I’m going to the trouble to write this blog post is that I found an unusually large number of such entry points for this problem. I think finding the entry points is what students usually find hardest, and while I don’t have a definitive way to teach people how to find these, perhaps seeing a few, with a bit of reverse reconstruction of my thought process might be helpful or interesting?

If you haven’t looked at the problem before, you will lose this chance if you read what follows. Nonetheless, some of you might want to anyway, and some of you might have looked at the problem but forgotten it, or not have a diagram to hand, so here’s my whiteboard diagram:

BMO1 Q5 b

Splitting into stages

A natural first question is: “how am supposed to show that four points are collinear?” Typically it’s interesting enough to show that three points are collinear. So maybe our strategy will be to pick three of the points, show they are collinear, then show some other three points are collinear then patch together. In my ‘official solution’ I made the visual observation that it looks like the four points P,Q,R,S are not just collinear, but lie on a line parallel to FE. This is good, because it suggests an alternative, namely split the points P,Q,R,S into three segments, and show each of them is parallel to FE. We can reduce our argument by 1/3 since PQ and RS are symmetric in terms of the statement.

BMO1 Q5 c

So in our reduced diagram for RS, we need an entry point. It doesn’t look like A is important at all. What can we say about the remaining seven points. Well it looks like we’ve got a pencil of three lines through C, and two triangles each constructed by taking one point on each of these lines. Furthermore, two pairs of sides of the triangles are parallel. Is this enough to prove that the third side is parallel?

Well, yes it is. I claim that this is the natural way to think about this section of the diagram. The reason I avoided it in the solution is that it requires a few more lines of written deduction than we might have expected. The key point is that saying BF parallel to DR is the same as saying BFC and DRC are similar. And the same applies to BE parallel to DS being the same as saying BEC similar to DSC.

We now have control of a lot of angles in the diagram, and by being careful we could do an angle chase to show that <FEB = <RSD or similar, but this is annoying to write down on a whiteboard. We also know that similarity gives rise to constant ratios of lengths. And this is (at least in terms of total equation length) probably the easiest way to proceed. FC/RC = BC/DC by the first similarity relation, and EC/SC=BC/DC by the second similarity relation, so FC/RC = EC/SC and we can reverse the argument to conclude FE || RS.

So, while I’m happy with the cyclic quadrilaterals argument in the video (and it works in an almost identical fashion for the middle section QR too), spotting this pencil of lines configuration was key. Why did I spot it? I mean, once A is eliminated, there were only the seven points in the pencil left, but we had to (actively) make the observation that it was a pencil. Well, this is where it becomes hard to say. Perhaps it was the fact that I was working out of a tiny notebook so felt inclined to think about it abstractly before writing down any angle relations (obviously there are lots)? Perhaps it was because I just knew that pencils of lines and sets of parallel lines go together nicely?

While I have said I am not a geometry expert, I am aware of Desargues’ Theorem, of which this analysis is a special case, or at least of the ingredients. This is not an exercise in showing off that I know heavy projective machinery to throw at non-technical problems, but rather that knowing the ingredients of a theorem is enough to remind you that there are relations to be found, which is certainly a meta-analytic property that exists much more widely in mathematics and beyond.

Direct enlargment

If I’d drawn my board diagram even more carefully, it might have looked like FE was in fact the enlargement of the line P,Q,R,S from D by a factor of 2. This is the sort of thing that might have been just an accidental consequence of the diagram, but it’s still worth a try. In particular, we only really need four points in our reduced diagram here, eg D,E,F,R, though we keep in mind that we may need to recall some property of the line FR, which is really the line FC.

Let’s define R’ to be the enlargement of R from D by a factor 2. That is, we look along the ray DR, and place the point R’ twice as far from D as R. We want to show that R’ lies on FE. This would mean that FR is the perpendicular bisector of DR’ in the triangle FDR’, and would further require that FR is the angle bisector of <DFR’, which we note is <DFE. At this stage our diagram is small enough that I can literally draw it convincingly on a post-it note, even including P and P’ for good measure:

BMO1 Q5 d

So all we have to do is check that FC (which is the same as FR) is actually the angle bisector of DFE, and for this we should go back to a more classical diagram (maybe without P,Q,R,S) and argue by angle-chasing. Then, we can reverse the argument described in the previous paragraph. Q also fits this analysis, but P and S are a little different, since these lie on the external angle bisectors. This isn’t qualitatively harder to deal with, but it’s worth emphasising that this might be harder to see!

I’ve described coming at this approach from the observation of the enlargement with a factor of 2. But it’s plausible that one might have seen the original diagram and said “R is the foot of the perpendicular from D onto the angle bisector of DFE”, and then come up with everything useful from there. I’m not claiming that this observation is either especially natural nor especially difficult, but it’s the right way to think about point R for this argument.

Simson Lines

The result about the Simson Line says that whenever P is a point on the circumcircle of a triangle ABC, the feet of the perpendiculars from P to the sides of the triangle (some of which will need to be extended) are collinear. This line is called the Simson line. The converse is also true, and it is little extra effort to show that the reflections of P in the sides are collinear (ie the Simson line enlarged from P by factor 2) and pass through the orthocentre H of ABC.

It turns out that this can be used to solve the problem quite easily. I don’t want to emphasise how to do this. I want to emphasise again that the similarity of the statement of the theorem to the statement of this particular problem is the important bit. Both involve dropping perpendiculars from a single point onto other lines. So even if it hadn’t worked easily in this case, it would still have been a sensible thing to try if one knew (and, crucially, remembered) the Simson line result.

I was working on this script during an evening in Barcelona, and tapas culture lends itself very well to brief solutions. Whether it was exactly between the arrival of cerveza and the arrival of morcilla or otherwise, this was the extent of my notes on this approach to the problem:

BMO1 Q5 e

And this makes sense. No computation or technical wizardry is required. Once you’ve identified the relevant reference triangle (here HEC), and have an argument to check that the point playing the role of P (here D) is indeed on the circumcircle (it’s very clear here), you are done. But it’s worth ending by reinforcing the point I was trying to make, that considering the Simson line is an excellent entry point to this problem because of the qualitative similarities in the statements. Dealing with the details is sometimes hard and sometimes not, and in this case it wasn’t, but that isn’t normally the main challenge.