Balkan MO 2017 – Qs 1, 3 and 4

The UK is normally invited to participate as a guest team at the Balkan Mathematical Olympiad, an annual competition between eleven countries from South-Eastern Europe. I got to take part in Rhodes almost exactly ten years ago, and this year the competition was held in Ohrid, in Macedonia. There’s one paper, comprising four questions, normally one from each of the agreed olympiad topic areas, with 4.5 hours for students to address them. The contest was sat this morning, and I’m going to say quite a bit about the geometric Q2, and a little bit about Qs 1 and 3 also. In all cases, this discussion will include most of a solution, with some commentary, so don’t read these if you are planning to try the problems yourself.

I’m not saying anything about Q4, because I haven’t solved it. (Edit: I have solved it now, so will postpone Q2 until later today.)

Question One

Find all ordered pairs of positive integers (x,y) such that

x^3+y^3=x^2+42xy+y^2.

The first thought is that if either of x or y is ‘large’, then the LHS is bigger than the RHS, and so equality can’t hold. That is, there are only finitely many solutions. The smallest possible value of y is, naturally, 1, and substituting y=1 is convenient as then y^2=y^3, and it’s straightforward to derive x=7 as a solution.

Regarding the non-existence of large solutions, you can make this precise by factorising the LHS as

(x+y)(x^2-xy+y^2) = x^2+42xy+y^2.

There are 44 terms of degree two on the RHS, and one term of degree in the second bracket on the LHS. With a bit of AM-GM, you can see then that if x+y>44, you get a contradiction, as the LHS will be greater than the RHS. But that’s still a lot of possibilities to check.

It struck me that I could find ways to reduce the burden by reducing modulo various primes. 2, 3 and 7 all divide 42, and furthermore cubes are nice modulo 7 and squares are nice modulo 3, so maybe that would bring the number of possibilities down. But my instinct was that this wasn’t the right way to use the fact that we were solving over positive integers.

The second bracket in the factorisation looks enough like the RHS, that it’s worth exploring. If we move x^2-xy+y^2 from the right to the left, we get

(x+y-1)(x^2-xy+y^2) = 43xy. (1.1)

Now it suddenly does look useful that we are solving over positive integers, because 43 is a prime, so has to appear as a factor somewhere on the LHS. But it’s generally quite restrictive that x^2-xy+y^2 | 43xy. This definitely looks like something that won’t hold often. If x and y are coprime, then certainly x^2-xy+y^2 and y are coprime also. But actually if x and y have a non-trivial common factor d, we can divide both sides by d^2, and it still holds. Let’s write

x=dm,\quad y=dn,\quad\text{where }d=\mathrm{gcd}(x,y).

Then m^2 -mn+n^2 really does divide 43, since it is coprime to both m and n. This is now very restrictive indeed, since it requires that m^2-mn+n^2 be equal to 1 or 43. A square-sandwiching argument gives m^2-mn+n^2=1 iff m=n=1. 43 requires a little bit more work, with (at least as I did it) a few cases to check by hand, but again only has one solution, namely m=7, n=1 and vice versa.

We now need to add the common divisor d back into the mix. In the first case, (1.1) reduces to (2d-1)=43, which gives (x,y)=(22,22). In the second case, after cancelling a couple of factors, (1.1) reduces to (8d-1)=7, from which (x,y)=(7,1),(1,7) emerges, and these must be all the solutions.

The moral here seemed to be that divisibility was a stronger tool than case-reduction. But that was just this question. There are other examples where case-reduction is probably more useful than chasing divisibility.

Question Three

Find all functions f:\mathbb{N}\rightarrow\mathbb{N} such that

n+f(m) \,\big|\, f(n)+nf(m)

for all m,n\in\mathbb{N}.

What would be useful here? There are two variables, and a function. It would be useful if we could reduce the number of variables, or the number of occurences of f. We can reduce the number of variables by taking m=n, to get

n+f(n) \,\big|\, f(n) [1+n]. (3.1)

From this, we might observe that f(n)\equiv 1 is a solution. Of course we could analyse this much more, but this doesn’t look like a 10/10 insight, so I tried other things first.

In general, the statement that a\,|\,b also tells us that a\,|\, b-ka. That is, we can subtract arbitrary multiples of the divisor, and the result is still true. A recurring trope is that the original b is elegant, but an adjusted b-ka is useful. I don’t think we can do the latter, but by subtracting n^2 +nf(m) from the problem statement, we get

n+f(m) \,\big|\, n^2-f(n). (3.2)

There’s now no m on the RHS, but this relation has to hold for all m. One option is that f(n)=n^2 everywhere, then what we’ve deduced always holds since the RHS is zero. But if there’s a value of n for which f(n)\ne n^2, then (3.2) is a very useful statement. From now on, we assume this. Because then as we fix n and vary m, we need n+f(m) to remain a divisor of the RHS, which is fixed, and so has finitely many divisors. So f(m) takes only finitely many values, and in particular is bounded.

This ties to the observation that f\equiv 1 is a solution, which we made around (3.1), so let’s revisit that: (Note, there might be more elegant ways to finish from here, but this is what I did. Also note, n is no longer fixed as in previous paragraph.)

n+f(n) \,\big|\, f(n) [1+n]. (3.1)

Just to avoid confusion between the function itself, and one of the finite collection of values it might take, let’s say b is a value taken by f. So there are values of n for which

n+b \,\big|\, b(1+n).

By thinking about linear equations, you might be able to convince yourself that there are only finitely many solutions (in n) to this relation. There are certainly only finitely many solutions where LHS=RHS (well, at most one solution), and only finitely many where 2xLHS=RHS etc etc. But why do something complicated, when we can actually repeat the trick from the beginning, and subtract b(n+b), to obtain

n+b \,\big|\, b^2-b.

For similar reasons to before, this is a great deduction, because it means if b\ne 1, then the RHS is positive, which means only finitely many n can satisfy this relation. Remember we’re trying to show that no n can satisfy this relation if b\ne 1, so this is definitely massive progress!

If any of what’s already happened looked like magic, I hope we can buy into the idea that subtracting multiples of the divisor from the RHS is the only tool we used, and that making the RHS fixed gives a lot of information about the LHS as the free variable varies. The final step is not magic either. We know that f is eventually 1. If you prefer “for large enough n, f(n)=1,” since all other values appear only finitely often. I could write this with quantifiers, but I don’t want to, because that makes it seem more complicated than it is. We genuinely don’t care when the last non-1 value appears.

Anyway, since we’ve deduced this, we absolutely have to substitute this into something we already have. Why not the original problem statement? Fix m, then for all large enough n

n+f(m) \,\big|\, 1+nf(m). (3.3)

To emphasise, (3.3) has to hold for all large enough n. Is it possible that f(m)=2? Again, it’s easy to convince yourself not. But, yet again, why not use the approach we’ve used so profitably before to clear the RHS? In fact, we already did this, and called it (3.2), and we can make that work [3.4], but in this setting, because f(m) is fixed and we’re working with variable large n, it’s better to eliminate n, to get

n+f(m)\,\big|\, f(m)^2-1,

again for all large enough n. By the same size argument as before, this is totally impossible unless f(m)=1. Which means that in fact f(m)=1 for all m. Remember ages ago we assumed that f(n) was not n^2 everywhere, so this gives our two solutions: f(n)=1,\, f(n)=n^2.

Moral: choosing carefully which expression to work with can make life much more interesting later. Eliminating as many variables or difficult things from one side is a good choice. Playing with small values can help you understand the problem, but here you need to think about soft properties of the expression, in particular what happens when you take one variable large while holding another fixed.

[3.4] – if you do use the original approach, you get n^2-1 on the RHS. There’s then the temptation to kill the divisibility by taking n to be the integer in the middle of a large twin prime pair. Unfortunately, the existence of such an n is still just a conjecture

Question Four

(Statement copied from Art of Problem Solving. I’m unsure whether this is the exact wording given to the students in the contest.)

On a circular table sit n>2 students. First, each student has just one candy. At each step, each student chooses one of the following actions:

(A) Gives a candy to the student sitting on his left or to the student sitting on his right.

(B) Separates all its candies in two, possibly empty, sets and gives one set to the student sitting on his left and the other to the student sitting on his right.

At each step, students perform the actions they have chosen at the same time. A distribution of candy is called legitimate if it can occur after a finite number of steps.
Find the number of legitimate distributions.

My moral for this question is this: I’m glad I thought about this on the bus first. What I found hardest here was getting the right answer. My initial thoughts:

  • Do I know how to calculate the total number of possibilities, irrespective of the algorithm? Fortunately yes I do. Marbles-in-urns = barriers between marbles on a line (maybe add one extra marble per urn first). [4.1]
  • What happens if you just use technique a)? Well first you can get into trouble because what happens if you have zero sweets? But fine, let’s temporarily say you can have a negative number of sweets. If n is even, then there’s a clear parity situation developing, as if you colour the children red and blue alternately, at every stage you have n/2 sweets moving from red children to blue and vice versa, so actually the total number of sweets among the red children is constant through the process.
  • What happens if you just use technique b)? This felt much more promising.
  • Can you get all the sweets to one child? I considered looking at the child directly opposite (or almost-directly opposite) and ‘sweeping’ all the sweets away from them. It felt like this would work, except if for some parity reason we couldn’t prevent the final child having one (or more, but probably exactly one) sweets at the crucial moment when all the other sweets got passed to him.

Then I got home, and with some paper, I felt I could do all possibilities with n=5, and all but a few when n=6. My conjecture was that all are possible with n odd, and all are possible with n even, except those when none of the red kids or none of the kids get a sweet. I tried n=8, and there were a few more that I couldn’t construct, but this felt like my failure to be a computer rather than a big problem. Again there’s a trade-off between confirming your answer, and trying to prove it.

Claim: If n is even, you can’t achieve the configurations where either the red children or the blue children have no sweets.

Proof: Suppose you can. That means there’s a first time that all the sweets were on one colour. Call this time T. Without loss of generality, all the sweets are on red at T. Where could the sweets have been at time T-1? I claim they must all have been on blue, which contradicts minimality. Why? Because if at least one red child had at least one sweet, they must have passed at least one sweet to a blue neighbour.

Now it remains to give a construction for all other cases. In the end, my proof has two stages:

Step One: Given a configuration, in two steps, you can move a candy two places to the right, leaving everything else unchanged.

This is enough to settle the n odd case. For the even case, we need an extra step, which really corresponds to an initial phase of the construction.

Step Two: We can make some version of the ‘sweeping’ move precise, to end up in some configuration where the red number of children have any number of sweets except 0 or n.

Step one is not so hard. Realising that step one would be a useful tool to have was probably the one moment where I shifted from feeling like I hadn’t got into the problem to feeling that I’d mostly finished it. As ever in constructions, working out how to do a small local adjustment, which you plan to do lots of times to get a global effect, is great. (Think of how you solve a Rubik’s cube for example.)

Step two is notationally fiddly, and I would think very carefully before writing it up. In the end I didn’t use the sweeping move. Instead, with the observation that you can take an adjacent pair and continually swap their sweets it’s possible to set up an induction.

Actual morals: Observing the possibility to make a small change in a couple of moves (Step one above) was crucial. My original moral does still hold slightly. Writing lots of things down didn’t make life easier, and in the end the ideas on the bus were pretty much everything I needed.

[4.1] – one session to a group of 15 year olds is enough to teach you that the canon is always ‘marbles in urns’ never ‘balls’ nor ‘bags’, let alone both.

Advertisements

RMM 2017 – UK Team Blog

This is the customary and slightly frivolous account of a trip to Bucharest for the ninth edition of the Romanian Master of Mathematics, an annual competition for school students, widely recognised as the hardest of its kind.

I discuss the problems in two previous posts (here and here), and there is also a pdf with fewer pictures, which includes both the discussion and this diary, as well as some more formal comments about the competition itself, the results, and thanks.

Wednesday 22 February

Did you know that trains in Moldova use different width tracks to trains in Romania? Well, I didn’t know either, but I found out at 1am today, as my wagon lit from Chisinau was painstakingly jacked up to allow the transfer from ex-Soviet gauge to Western gauge. Outside, a man in a smart uniform and epaulettes shouted loudly and continuously at a group of men in smart uniforms without epaulattes. When their task was done, four sets of border and custom checks remained before the opportunity for another visit to the samovar, and finally a chance to sleep.

All of which is to say that I have arrived at maths competitions in better mental shape than 6am today at Gara de Nord. The UK students have a more conventional itinerary, but their flight from Luton doesn’t arrive until mid-afternoon. After my first Haifa ‘winter’, I’m craving pork and snow, and find both in the mountain town of Sinaia, an hour away by train in Transylvania. I also find a bear. The bear seems very scared.

I return in time to meet the UK students as well as James and MT. Some of our contestants are now into their fourth year of attending international competitions, and the labour of finding them fresh material resembles Hercules against the hydra, but some problems on combinatorial geometry with convexity seem to have kept everyone entertained on the flight. Dinner is at the Moxa campus of the University of Economics, and features chicken with one of two possible carbohydrates, as in fact do the next six meals. However, today is Thomas’s 18th birthday, and so his parents have arranged a delicious cake, which elicits considerably more enthusiasm. On the short walk back to our meeting, we notice it is possible both to buy fireworks and get a tattoo among other options, so Thomas is spoiled for choice about how to take advantage of his majority.

The team’s activities remain a mystery to James and me though, as we have to join the other leaders for the first meeting, to receive the proposed problems. We spend some time thinking about them separately then together, and our initial impression is that it’s a very suitable paper, that hopefully our team will enjoy.

Thursday 23 February

The leaders meet to finalise the choice and statement of the problems. With a bit more time this morning, I’ve solved Q1, Q2, Q5, and proved Q3 once I’d looked up the correct bound. James eats conics for breakfast and shows me a glorious range of interpretations of Q4. We feel happy that our students will have a chance at all of these, while Q6 may prove more restricting. Either way, it’s clearly an appropriate set for this competition, and is approved quickly. So it’s time to finalise the English version of the paper, or finalize the American version. Many alternatives to the word sieve are proposed. Andrea from Italy is clearly already craving home comforts, but his suggestion of cheese grater is not taken up. This time I’m sorting the LaTeX, so get to settle the commas, but also take the blame for inconsistently spacing the rubric between the two papers. I’m sure everyone noticed.

While all this has been happening, the students have been at a lecture by Sergiu Moroianu at the Institute of Mathematics. Joe Benton gives an account of what they learned in the longer pdf version of this report.

For all the charms of Chipping Norton, I sense MT is enjoying the grittier nature of Bucharest Sector 1, and has been shepherding the students round various sites in between attempts at practice problems. I join them for a brief visit to a geology museum. I am very cynical, but it slightly exceeds my expectations, and is infinitely better than the nearby Museum of the Romanian Peasant, which currently ties with the Hanoi Ethnology Museum as my least favourite olympiad excursion of all time.

The opening ceremony is held in the grand hall of the university, and includes several welcoming and thoughtful speeches from the Mayor of Bucharest and the headteacher of Tudor Vianu, the school which hosts this competition every year. Each team briefly presents themselves on stage. Joe and Neel have accumulated a large collection of UK flags from previous competitions, and should hereby consider themselves publicly shamed for forgetting their promise to bring them. It is over soon, and while the students enjoy a quiet evening and an early night, the leaders have to finalise markschemes for all the problems. The walk back takes us through Victory Square, and past the protesters whose fires and slogans have been on front pages around the world in the past months. It’s an interesting time, and the atmosphere of this city feels very different from my first visit, for the inaugural edition of this competition in 2008.

Friday 24 February

The first day of the contest starts at 9am. The British students seem fairly relaxed, and hopefully are aiming high. Contestants may ask questions of clarification during the first 30 minutes. Rosie does this, and I send my reply to her two queries back via the courier. Five minutes later it is returned to me with the explanation that the student does not understand the answer. Even under competition pressure this seems unlikely, given that my answers are, respectively ‘yes’, and putting a ring around one of three options she has listed. It turns out that actually the student courier did not understand what to do with the answer, and the situation is quickly corrected.

We approve more markschemes. The US deputy leader Po-Shen and I share our views on the challenge of correctly finding the bound in Q3, and our suggestion that this instead be worth 2 points is upheld. Various further discussions fill the morning, and we return just in time to meet the students at the end of the exam. Harvey claims all three problems with a relaxed grin, while Joe claims all three problems with the haunted look of a man whose twelfth espresso of the day has just worn off. Alexander and Thomas say that they spent most of the time making sure their solutions to Q1 were totally watertight, which, given the intricacy of the arguments, was clearly a very sensible strategy.

To provide a distraction, if not actually a break from time-pressured problem-solving, I’ve booked a pair of escape rooms for the UK students later in the afternoon. Bucharest is the home of these games, where the aim is to solve themed puzzles as part of a story in time to escape a locked room. I join one of the rooms, where there are some theatrical reveals involving wrenches, and clues hidden in combination-locked cabinets, where ability to add three-digit numbers proves useful. Someone’s carrying voice means we get to enjoy some of the drama and twists of the other room too. Anyway, this proved an ideal way to avoid useless post-mortems, and I highly recommend Vlad and his pair of rooms.

Later, James and I get to look at the students’ work from this morning. Their assessments are pretty accurate. Harvey’s solutions to everything are beautiful, while Neel’s bounding argument in Q2 is certainly the most vulgar (and, in fact, unnecessary) calculation of the year so far. Joe’s solution to Q3 bears such obvious resemblence to an official solution that his uncharacteristic abundance of small errors probably won’t matter, including the memorable set A_i\backslash\{i\}, where the two is mean different things. Some of the team might reflect that a moment of casualness in checking the n=2 case on Q2 is a frustrating way to lose a potential mark, but when I compare notes with James, it sounds like the slow and steady approach to Q1 has indeed paid off for everyone, so hopefully it will not be too painful to agree the scores tomorrow.

Saturday 25 February

It’s the second day of the competition, and the UK team look bright-eyed and positive at breakfast. They aren’t the only ones under pressure this morning, as James and I must settle the scores from yesterday’s questions with local markers, known as coordinators. It’s hard to guess in how much detail one will have to explain your contestants’ scripts, so it is safer to prepare almost line-by-line. On this occasion though, perhaps we have over-prepared, as every meeting ends quickly with offers of 7/7 exactly where we were hoping, and indeed in a couple of places where we were not hoping. The markschemes are very clear about certain omissions which carry a point deduction, so to ensure fairness and consistency, we insist that two scores are moved down. I’m confident that any British student would prefer an honourable 41/42 than an accidental 42/42.

No-one’s going to be scoring 41 nor 42 unless they solve the extremely challenging geometry Q6, and as we meet our students afterwards, it turns out they have not managed any progress there. However, they claim an almost full set of solutions to Questions 4 and 5, which, if accurate, is a very good return. Everyone is in a good mood, and after I explain a couple of approaches to Q6, no-one seems too disappointed that they didn’t spot these.

There are various schedules floating around, listing multiple locations and times for lunch, but our space-time trajectory intersects none of them, so we follow the Chinese team to a recommended cheap Szechuan restaurant round the corner. Various circle theorems are explored via the Lazy Susan, and there is a grand reveal of the marks we’ve recently confirmed. There’s time for another pair of escape rooms while the second day scripts arrive. As Rosie remarks, two in two days can lead to excessive outside-the-box thinking. Sometimes a radiator really isn’t a sinister prop, a device for encoding five-digit numbers, or a clue to a Templar tunnel; it’s just a radiator. Otherwise we’d be cold.

When the scripts arrive, as expected the cupboard is pretty bare on Q6. If there were marks for quantity, Neel might get some, and if there were marks for most uses of esoteric theory in a single page, Alexander might get one. No set of scripts for an international-level medium combinatorics problem will ever be perfect, but our Q5s come close. It’s therefore not a long evening, and we can join the students for dinner with the American team. For most of them it’s their first visit to Europe, and there’s much comparing of culture and maths training programmes. There’s also a long discussion of whether it’s sensible to teach maths in primary school. Those present who have small children or younger siblings weigh in on the mysteries of the ‘grid method’, and whether toddlers implicitly understand commutativity, even if they can’t spell it.

Sunday 26 February

The UK leaders gather early in the ‘philosophical anti-cafe’ opposite Vianu school, to ponder the final scripts with a coffee and a view of an artfully-arranged folio of Spinoza. James has a loyalty card here. Unfortunately two of our students have clear algebraic errors in Q4, but apart from that everything is very straightforward. Though following last night’s conversation, we note that maybe a revision clinic on mathematical spelling might prove useful. Anonymous student X thinks there’s one L in ‘ellipse’, counterbalanced by anonymous student Y who thinks there are two in ‘column’. The word ‘parallel’ comes in many disguises.

Of course, the coordinators couldn’t care less about that, and they don’t even mind Neel’s two-cases-at-once inductive step, so again we get what we ask for on Q5 immediately, and on Q4 in the time it takes James to draw a lozenge tiling representing Thomas’s shearing argument. For Q6, it turns out there clearly is a mark for most uses of esoteric theory in a single page, so Alexander gets it. They show us a diagram with over a hundred lines which suggests that the exotic equivalence he claims is actually true. There we go. Overall, the quality of our written solutions has been extremely high. It feels like I say this every time now, but it isn’t idle propaganda. We remember the horrors that used to emerge occasionally, and the effort to make this improvement permanent feels well worth it.

Meanwhile, to fill the day, the students have gone to Sinaia. Two of their guides went with them to help with tickets at the station, apparently under the impression that never having taken a train before wouldn’t be an obstacle to this role. Either way, they made it, and following my request for material for this report, I receive a trickle of presentable photos, though there is talk afterwards of some rather more informal versions which are apparently not suitable. The Transylvanian winter is thawing, but slowly and messily, and Harvey reports that several of the group spent more time horizontal than vertical. Irrespective of their preferred axis, there’s no comment on whether they saw my bear, or any other bear. But since my bear was scared of me, one wonders what it would make of MT’s telling-off face? (Last seen by me during the notorious ‘balcony incident’ at a summer school in 2005, but hardly forgotten.)

The students return in time for confirmation of the results and their medals. As so often, there is pleasure that we have done so well collectively, mixed with mild disappointment for those who ended up just short of a boundary, and that the UK was so close to placing first. Because of the strength of the invited countries, earning a medal of any colour is a very worthwhile achievement, and so Rosie is impressively sanguine about missing out so narrowly in such an unfortunate manner. Alexander was closer than it appears, and could have two more opportunities to take part.

The closing ceremony at Vianu school proceeds rapidly. There is the usual challenge of photographing the students receiving their prizes, but this time is easy. Thomas is about a foot taller than everyone else on the stage, while Neel is flanked by almost the entire Russian team, but his chutzpah trumps their numerical advantage, with laughter all round. Joe claims this year’s gold medal is substantially weightier. He hasn’t brought his previous pair, so the chance to verify this and recreate a Mark Spitz moment goes begging.

It’s 7pm, and UK student enthusiasm for the closing disco (not my words) is about as high as MT’s enthusiasm to chaperone the closing disco. Instead we find a Middle Eastern restaurant, and it’s refreshing to eat hummus in a place which doesn’t claim to be the ‘best in Israel’ though I don’t think Abu Said in Akko will be rushing to steal the recipe. Po-Shen outlines his vision of a year-long maths camp. I think present company are tired enough after five days here. Some are interested to view, if not actually participate in, the protests in Victory Square, but it seems tonight is a quiet one and nothing is being burned, so late-night cards and a perusal of each others’ scripts will have to do.

Monday 27th February

The rest of the group have a flight back to London later today which apparently cost 99p per person before tax. I don’t know how much less the 5am option was, but I think it’s probably worth it. My own flight is truly at 5am tomorrow and I plan to stay up all night. The students return to school tomorrow, doubtless to receive a glorious mix of adulation and apathy. Harvey requests whether next year this trip can be timed differently so that he can miss the whole of his local Eisteddfod, rather than just one day. I promise to ask the organisers, say goodbye, then head for the hills on a train journey long enough to write the entirety of this report.

3am at Bucharest airport, and thoughts can now turn to the future. Many of us will meet in five weeks’ for another round of mathematics in the more tranquil setting of Cambridge. Meanwhile, I certainly enjoyed, admittedly through red eyes, the entertainment of a flight to Israel where baggage size regulations are actually enforced at the boarding gate, and apparently everyone else made it back safely too.

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.

RMM 2017 – Problems 1, 4 and 5

I’ve recently taken a UK team to the 2017 edition of the Romanian Master of Mathematics competition in Bucharest. The British students did extremely well and we all enjoyed ourselves mathematically and generally. The customary diary may appear shortly, but this time I want to focus mainly on the questions, since that is after all the main point of these competitions! I hope that what follows is interesting, and at slightly education to potential future students.

I’ve split this into two posts based on my opinion on difficulty, which is subjective but probably correlates fairly positively with most people’s. The account of Q1 is guest-written by two British students, based on their solutions during the competition.

Problem 1

a) Prove that every positive integer n can be written uniquely in the form

n = \sum_{j=1}^{2k+1} (-1)^{j-1} 2^{m_j},

where k\geq 0 and 0 \leq m_1 < m_2 < \cdots < m_{2k+1} are integers. This number k is called the weight of n.

b) Find (in closed form) the difference between the number of positive integers at most 2^{2017} with even weight and the number of positive integers at most 2^{2017} with odd weight.

Rosie Cates and Neel Nanda:

a) We are trying to express n in terms of powers of 2, so it seems sensible to write in binary. As 2^{m_1} is the smallest power of 2, this term is responsible for the last 1 in the binary representation of n. Let $letx x = n – 2^{m_1}$ (ie n with the last 1 removed from its binary expansion). Now if we pair up terms in the sum to get

x = (2^{m_{2k}+1} - 2^{m_{2k}}) + \ldots + (2^{m_3} - 2^{m_2}),

we can see that each bracket looks like 11…100…0 when written in binary. Also, the condition that m_i < m_{i+1} is equivalent to ensuring that we do not break any strings of consecutive 1s that were in the binary expansion of x (so for example 111110 = 110000 +1110 is not allowed). So writing x in the desired form is the same as writing it as the sum of numbers of the form 11…100\ldots 0 without breaking any strings of 1s. For example

1110100110 = 1110000000 + 100000 + 110.

Clearly there is exactly one way of doing this for every x, so (as each n has exactly one x) there is exactly one way to do it for each n as well.

This approach allows k to be understood differently. Write n in binary and remove the last 1; now count the number of groups of consecutive 1s. This is equal to k.

b) The second half of the problem becomes a lot simpler with the observation that n\leq 2^{m_{2k+1}}, as

n=2^{m_{2k+1}}-(2^{m_{2k}}-2^{m_{2k-1}})-\ldots-(2^{m_2}-2^{m_1}),

and the sequence m_n is increasing, so each bracket is positive. As each sequence of (m_n)s corresponds uniquely to an integer, this means we just want to count sequences of (m_n)s with greatest term at most 2017. The sequence is increasing, so each sequence corresponds to a subset of {0, 1, …, 2017} of size (2k+1). There are \binom{2018}{2k+1} subsets of size (2k+1), so the question reduces to finding a closed form for \sum_{k=0}^{1008} (-1)^k {{2018}\choose{2k+1}}.

This is reminiscent of a classic problem in combinatorics: using the binomial theorem to evaluate sums of binomial coefficients weighted by powers. The best example is

\sum_{k=0}^n (-1)^k \binom{n}{k} =(1-1)^n=0,

but here rather than (-1) we want something whose square is $(-1)$, so we consider the complex number i. Using the same ideas, we get that

\sum_{r=0}^{2018} i^r \binom{2018}{r}=(1+i)^{2018},

which contains what we want, but also binomial coefficients with even r. But if r is even, i^r is real, and if r is odd, i^r is imaginary. So the sum we want appears as the imaginary part, that is

\mathrm{Im}\left((1+i)^{2018}\right)=\mathrm{Im}\left((\sqrt{2} \cdot e^{\frac{i\pi}{4}})^{2018}\right)=2^{1009}.

Dominic: note that in both parts, the respective authors find slightly more than what they were required to. That is, respectively, the interpretation of k, and a bound on m_{2k+1}. The latter is an excellent example of the general notion that sometimes it is better to use a stronger statement than what you actually require in an induction argument (here for existence). The stronger statement (which you guess from playing with examples) makes the inductive step easier, as it’s then clear that the new term you get is distinct from the terms you already have.

Problem 4

In the Cartesian plane, let \mathcal G_1, \mathcal G_2 be the graphs of the quadratic functions f_1(x) = p_1x^2 + q_1x + r_1, f_2(x) = p_2x^2 + q_2x + r_2, where p_1 > 0 > p_2. The graphs \mathcal G_1, \mathcal G_2 cross at distinct points A and B. The four tangents to \mathcal G_1, \mathcal G_2 at~A and B form a convex quadrilateral which has an inscribed circle. Prove that the graphs \mathcal{G}_1 and \mathcal{G}_2 have the same axis of symmetry.

This question is quite unusual for an olympiad of this kind, and I was initially skeptical, but then it grew on me. Ultimately, I was unsurprised that many contestants attacked entirely with coordinate calculations. If you use this strategy, you will definitely get there in the end, but you have to accept that you aren’t allowed to make any mistakes. And because of the amount of symmetry in the configuration, even if you make a mistake, you might still get the required answer, and so not notice that you’ve made a mistake. But I decided I liked it because various levels of geometric insight either reduced or removed the nastier calculations.

Typically, one could gain geometric insight by carefully observing an accurate diagram, but an accurate parabola is hard to draw. However, even from a vague diagram, we might guess the key intermediate property of the configuration, which is that the line joining the other two points in the quadrilateral is parallel to the y-axis. This means that they have the same x-coordinate, and indeed this x-coordinate must in fact be the same for any parabola through A and B, so it is reasonable to guess that it is \frac{x_A+x_B}{2}, the mean of the x-coordinates of A and B.

Since you know this is the goal, it’s not too bad to calculate the equations of the tangent lines directly, and demonstrate this algebraically. But I was determined to use the focus-directrix definition of a parabola. Either recall, or digest the interesting new fact that a parabola may be defined as the locus of points which are the same distance from a fixed point P (the focus), and a fixed line \ell (the directrix). Naturally, the distance to the line is perpendicular distance.

To ensure the form given in the statement where y is a quadratic function of x, in this setting the directrix should be parallel to the x-axis. To define the tangent to the parabola at A, let A’ be the foot of the perpendicular from A onto \ell, so AA’=PA. I claim that the tangent at A is given by the perpendicular bisector of A’P. Certainly this passes through A, and it is easy to convince yourself that it can’t pass through any other point B on the parabola, since BA’> PB, as A’ is on \ell but is not the foot of the perpendicular form B to \ell. This final observation is truly a lot more obvious if you’re looking at a diagram.

We now want to finish geometrically too. In our quadrilateral, one diagonal is parallel to the y-axis, and it will suffice to show that the existence of an incircle implies that A and B must have the same y-coordinate. We have just shown A and B are the same (horizontal) distance from the other diagonal. So certainly if they have the same y-coordinate, then the quadrilateral is a kite, and the sums of opposite sides are equal, which is equivalent to the existence of an incircle. One could then finish by arguing that this ceases to be true if you move one of A and B in either direction, or by some short explicit calculation if such a perturbation argument leaves you ill at ease.

Question 5

Fix an integer n \geq 2. An n x n  sieve is an n x n array with n cells removed so that exactly one cell is removed from every row and every column. A stick is a 1 x k or k x 1 array for any positive integer k. For any sieve A, let m(A) be the minimal number of sticks required to partition A. Find all possible values of m(A), as A varies over all possible n x n sieves.

This is a fairly classic competition problem, and while in my opinion the statement isn’t particularly fascinating, it’s interesting that it admits such a wide range of approaches.

As ever, you need to start by playing around with the setup, and guessing that the answer is 2n-2, and not thinking `it can’t possibly be the same answer as Q3??’ Then think about reasons why you couldn’t do better than 2n-2. My very vague reason was that if you only use horizontal sticks, the answer is clearly 2n-2, and the same if you only use vertical sticks. But it feels like you can only make life harder for yourself if you try to use both directions of sticks in lots of places. Note that some sort of argument involving averaging over stick lengths is definitely doomed to fail unless it takes into account the Latin square nature of the location of holes! For example, if you were allowed to put all the holes in the first row, m(A) would be n-1.

Induction is tempting. That is, you remove some number of sticks, probably those corresponding to a given hole, to reduce the board to an (n-1)x(n-1) configuration. If you do this, you need to be clear about why you can remove what you want to remove (in particular, the number of sticks you want to remove), and whether it’s qualitatively different if the hole in question lies on the border of the board. In all of these settings, you want to be careful about 1×1 sticks, which it’s easy inadvertently to count as both horizontal and vertical. This is unlikely to affect the validity of any argument (just picking either an arbitrary or a canonical direction if it’s 1×1 should be fine) but does make it much harder to check the validity.

Joe exhibited directly a construction of 2n-2 cells which must be covered by different sticks. This approach lives or dies by the quality of the written argument. It must look general, even though any diagram you draw must, almost by definition, correspond to some particular case. Alternatively, since the problem is set on a grid, the cells correspond naturally to edges of a bipartite graph, where classes correspond to rows and columns. The holes form a perfect matching on this bipartite graph. But, as Harvey observed, if you split the rows and columns in two, on either side of the relevant hole (or not in the 2+2 cases where the hole is at the border), you have a (2n-2)+(2n-2) bipartite graph, and a perfect matching here corresponds to a set of cells which must be covered by different sticks. This is an ingenious idea, and if you’ve recently met Hall’s Marriage Theorem, which gives a verifiable criterion for the existence of such a perfect matching, there are few better uses of your next ten minutes than to check whether Hall’s condition a) should hold; b) can be proven to hold in this setting.

Antichains in the grid

In the previous post on this topic, we discussed Dilworth’s theorem on chains and antichains in a general partially ordered set. In particular, whatever the size of the largest antichain in a poset, it is possible to partition the poset into exactly that many chains. So for various specific posets, or the directed acyclic graphs associated to them, we are interested in the size of this largest antichain.

The following example turned out to be more interesting than I’d expected. At a conventional modern maths olympiad, there are typically three questions on each paper, and for reasons lost in the mists of time, each student receives an integer score between 0 and 7 per question. A natural question to ask is “how many students need to sit a paper before it’s guaranteed that one will scores at least as highly as another on every question?” (I’m posing this as a straight combinatorial problem – the correlation between scores on different questions will be non-zero and presumably positive, but that is not relevant here.)

The set of outcomes is clearly \{0,1,\ldots,7\}^3, with the usual weak domination partial order inherited from \mathbb{R}^3. Then an antichain corresponds to a set of triples of scores such that no triple dominates another triple. So the answer to the question posed is: “the size of the largest antichain in this poset, plus one.”

In general, we might ask about \{1,2,\ldots,n\}^d, again with the weak domination ordering. This directed graph, which generalises the hypercube as well as our example, is called the grid.

Heuristics for the largest antichain

Retaining the language of test scores on multiple questions is helpful. In the previous post, we constructed a partition of the poset into antichains, indexed by the elements of some maximal chain, by starting with the sources, then looking at everything descended only from sources, and so on. (Recall that the statement that this is possible was referred to as the dual of Dilworth’s theorem.) In the grid, there’s a lot of symmetry (in particular under the mapping x\mapsto n+1-x in every coordinate), and so you end up with the same family of antichains whether you work upwards from the sources or downwards from the sinks. (Or vice versa depending on how you’ve oriented your diagram…) The layers of antichains also have a natural interpretation – each layer corresponds to a given total score. It’s clear a priori why each of these is an antichain. If A scores the same as B overall, but strictly more on the first question, this must be counterbalanced by a strictly lower score on another question.

So a natural guess for the largest antichain is the largest antichain corresponding to some fixed total score. Which total score should this be? It ought to be the middle layer, that is total score \frac{(n+1)d}{2}, or the two values directly on either side if this isn’t an integer. My intuition was probabilistic. The uniform distribution on the grid is achieved by IID uniform distributions in each coordinate, which you can think of as a random walk, especially if you subtract off the mean first. It feels that any symmetric random walk should have mode zero or next-to-zero. Certainly this works asymptotically in a rescaled sense by CLT, and in a slightly stronger sense by local CLT, but we don’t really want asymptotics here.

When I started writing the previous paragraph, I assumed there would be a simple justification for the claim that the middle layer(s) was largest, whether by straight enumeration, or some combinatorial argument, or even generating functions. Perhaps there is, and I didn’t spot it. Induction on d definitely works though, with a slightly stronger hypothesis that the layer sizes are symmetric around the median, and monotone on either side of the median. The details are simple and not especially interesting, so I won’t go into them.

From now on, the hypothesis is that this middle layer of the grid is the largest antichain. Why shouldn’t it, for example, be some mixture of middle-ish layers? (*) Well, heuristically, any score sequence in one layer removes several possibilities from a directly adjacent layer, and it seems unlikely that this effect is going to cancel out if you take some intermediate number of score sequences in the first layer. Also, the layers get smaller as you go away from the middle, so because of the large amount of symmetry (coordinates are exchangeable etc), it feels reasonable that there should be surjections between layers in the outward direction from the middle. The union of all these surjections gives a decomposition into chains.

This result is in fact true, and its proof by Bollobas and Leader, using shadows and compression can be found in the very readable Sections 0 and 1 of [1].

Most of the key ideas to a compression argument are present in the case n=2, for which some notes by Leader can be found here, starting with Proof 1 of Theorem 3, the approach of which is developed over subsequent sections. We treat the case n=2, but focusing on a particularly slick approach that does not generalise as successfully. We also return to the original case d=3 without using anything especially exotic.

Largest antichain in the hypercube – Sperner’s Theorem

The hypercube \{0,1\}^d is the classical example. There is a natural correspondence between the vertices of the hypercube, and subsets of [d]. The ordering on the hypercube corresponds to the ordering given by containment on \mathcal{P}([d]). Almost by definition, the k-th layer corresponds to subsets of size k, and thus includes \binom{d}{k} subsets. The claim is that the size of the largest antichain is \binom{d}{\lfloor d/2 \rfloor}, corresponding to the middle layer if d is even, and one of the two middle layers if d is odd. This result is true, and is called Sperner’s theorem.

I know a few proofs of this from the Combinatorics course I attended in my final year at Cambridge. As explained, I’m mostly going to ignore the arguments using compression and shadows, even though these generalise better.

As in the previous post, one approach is to exhibit a covering family of exactly this number of disjoint chains. Indeed, this can be done layer by layer, working outwards from the middle layer(s). The tool here is Hall’s Marriage Theorem, and we verify the relevant condition by double-counting. Probably the hardest case is demonstrating the existence of a matching between the middle pair of layers when d is odd.

Take d odd, and let d':= \lfloor d/2\rfloor. Now consider any subset S of the d’-th layer \binom{[d]}{d'}. We now let the upper shadow of S be

\partial^+(S):= \{A\in \binom{[d]}{d'+1}\,:\, \exists B\in S, B\subset A\},

the sets in the (d’+1)-th layer which lie above some set in S. To apply Hall’s Marriage theorem, we have to show that |\partial^+(S)|\ge |S| for all choice of S.

We double-count the number of edges in the hypercube from S to \partial^+(S). Firstly, for every element B\in S, there are exactly d’ relevant edges. Secondly, for every element A\in\partial^+(S), there are exactly d’ edges to some element of \binom{[d]}{d'}, and so in particular there are at most d’ edges to elements of S. Thus

d' |S|=|\text{edges }S\leftrightarrow\partial^+(S)| \le d' |\partial^+(S)|,

which is exactly what we require for Hall’s MT. The argument for the matching between other layers is the same, with a bit more notation, but also more flexibility, since it isn’t a perfect matching.

The second proof looks at maximal chains. Recall, in this context, a maximal chain is a sequence \mathcal{C}=B_0\subset B_1\subset\ldots\subset B_d where each B_k:= \binom{[d]}{k}. We now consider some largest-possible antichain \mathcal{A}, and count how many maximal chains include an element A\in\mathcal{A}. If |A|=k, it’s easy to convince yourself that there are \binom{d}{r} such maximal chains. However, given A\ne A'\in\mathcal{A}, the set of maximal chains containing A and the set of maximal chains containing A’ are disjoint, since \mathcal{A} is an antichain. From this, we obtain

\sum_{A\in\mathcal{A}} \binom{d}{|A|} \le d!. (**)

Normally after a change of notation, so that we are counting the size of the intersection of the antichain with each layer, this is called the LYM inequality after Lubell, Yamamoto and Meshalkin. The heuristic is that the sum of the proportions of layers taken up by the antichain is at most one. This is essentially the same as earlier at (*). This argument can also be phrased probabilistically, by choosing a *random* maximal chain, and considering the probability that it intersects the proposed largest antichain, which is, naturally, at most one. Of course, the content is the same as this deterministic combinatorial argument.

Either way, from (**), the statement of Sperner’s theorem follows rapidly, since we know that \binom{d}{|A|}\le \binom{d}{\lfloor d/2\rfloor} for all A.

Largest antichain in the general grid

Instead of attempting a proof or even a digest of the argument in the general case, I’ll give a brief outline of why the previous arguments don’t transfer immediately. It’s pretty much the same reason for both approaches. In the hypercube, there is a lot of symmetry within each layer. Indeed, almost by definition, any vertex in the k-th layer can be obtained from any other vertex in the k-th layer just by permuting the labels (or permuting the coordinates if thinking as a vector).

The hypercube ‘looks the same’ from every vertex, but that is not true of the grid. Consider for clarity the n=8, d=3 case we discussed right at the beginning, and compare the scores (7,0,0) and (2,2,3). The number of maximal chains through (7,0,0) is \binom{14}{7}, while the number of maximal chains through (2,2,3) is \binom{7}{2, 2,3}\binom{14}{4,5,5}, and the latter is a lot larger, which means any attempt to use the second argument is going to be tricky, or at least require an extra layer of detail. Indeed, exactly the same problem arises when we try and use Hall’s condition to construct the optimal chain covering directly. In the double-counting section, it’s a lot more complicated than just multiplying by d’, as was the case in the middle of the hypercube.

Largest antichain in the d=3 grid

We can, however, do the d=3 case. As we will see, the main reason we can do the d=3 case is that the d=2 case is very tractable, and we have lots of choices for the chain coverings, and can choose one which is well-suited to the move to d=3. Indeed, when I set this problem to some students, an explicit listing of a maximal chain covering was the approach some of them went for, and the construction wasn’t too horrible to state.

[Another factor is that it computationally feasible to calculate the size of the middle layer, which is much more annoying in d>3.]

[I’m redefining the grid here as \{0,1,\ldots,n-1\}^d rather than \{1,2,\ldots,n\}^d.]

The case distinction between n even and n odd is going to make both the calculation and the argument annoying, so I’m only going to treat the even case, since n=8 was the original problem posed. I should be honest and confess that I haven’t checked the n odd case, but I assume it’s similar.

So when n is even, there are two middle layers namely \frac{3n}{2}-2, \frac{3n}{2}-1 (corresponding to total score 10 and total score eleven in the original problem). I calculated the number of element in the \frac{3n}{2}-1 layer by splitting based on the value of the first coordinate. I found it helpful to decompose the resulting sum as

\sum_{k=0}^{n-1} = \sum_{k=0}^{\frac{n}{2}-1} + \sum_{k=\frac{n}{2}}^{n-1},

based on whether there is an upper bound, or a lower bound on the value taken by the second coordinate. This is not very interesting, and I obtained the answer \frac{3n^2}{4}, and of course this is an integer, since n is even.

Now to show that any antichain has size at most \frac{3n^2}{4}. Here we use our good control on the chain coverings in the case d=2. We note that there is a chain covering of the (n,d=2) grid where the chains have 2n-1, 2n-3,…, 3, 1 elements (%). We get this by starting with a maximal chain, then taking a maximal chain on what remains etc. It’s pretty much the first thing you’re likely to try.

Consider an antichain with size A in the (n,d=3) grid, and project into the second and third coordinates. The image sets are distinct, because otherwise a non-trivial pre-image would be a chain. So we have A sets in the (n,d=2) grid. How many can be in each chain in the decomposition (%). Well, if there are more than n in any chain in (%), then two must have been mapped from elements of the (n,d=3) grid with the same first coordinate, and so satisfy a containment relation. So in fact there are at most n image points in any of the chains of (%). So we now have a bound of n^2. But of course, some of the chains in (%) have length less than n, so we are throwing away information. Indeed, the number of images points in a given chain is at most

\max(n,\text{length of chain}),

and so the number of image points in total is bounded by

n+\ldots+n+ (n-1)+(n-3)+\ldots+1,

where there are n/2 copies of n in the first half of the sum. Evaluating this sum gives \frac{3n^2}{4}, exactly as we wanted.

References

[1] – Bollobas, Leader (1991) – Compressions and Isoperimetric Inequalities. Available open-access here.

BMO2 2017

The second round of the British Mathematical Olympiad was taken yesterday by about 100 invited participants, and about the same number of open entries. To qualify at all for this stage is worth celebrating. For the majority of the contestants, this might be the hardest exam they have ever sat, indeed relative to current age and experience it might well be the hardest exam they ever sit. And so I thought it was particularly worth writing about this year’s set of questions. Because at least in my opinion, the gap between finding every question very intimidating, and solving two or three is smaller, and more down to mindset, than one might suspect.

A key over-arching point at this kind of competition is the following: the questions have been carefully chosen, and carefully checked, to make sure they can be solved, checked and written up by school students in an hour. That’s not to say that many, or indeed any, will take that little time, but in principle it’s possible. That’s also not to say that there aren’t valid but more complicated routes to solutions, but in general people often spend a lot more time writing than they should, and a bit less time thinking. Small insights along the lines of “what’s really going on here?” often get you a lot further into the problem than complicated substitutions or lengthy calculations at this level.

So if some of the arguments below feel slick, then I guess that’s intentional. When I received the paper and had a glance in my office, I was only looking for slick observations, partly because I didn’t have time for detailed analysis, but also because I was confident that there were slick observations to be made, and I felt it was just my task to find them.

Anyway, these are the questions: (note that the copyright to these is held by BMOS – reproduced here with permission.)

Question One

2017-bmo2-q1I immediately tried the example where the perpendicular sides are parallel to the coordinate axes, and found that I could generate all multiples of 3 in this way. This seemed a plausible candidate for an answer, so I started trying to find a proof. I observed that if you have lots of integer points on one of the equal sides, you have lots of integer points on the corresponding side, and these exactly match up, and then you also have lots of integer points on the hypotenuse too. In my first example, these exactly matched up too, so I became confident I was right.

Then I tried another example ( (0,0), (1,1), (-1,1) ) which has four integer points, and could easily be generalised to give any multiple of four as the number of integer points. But I was convinced that this matching up approach had to be the right thing, and so I continued, trusting that I’d see where this alternate option came in during the proof.

Good setup makes life easy. The apex of the isosceles triangle might as well be at the origin, and then your other vertices can be (m,n), (n,-m) or similar. Since integral points are preserved under the rotation which takes equal side to the other, the example I had does generalise, but we really need to start enumerating. The number of integer points on the side from (0,0) to (m,n) is G+1, where G is the greatest common divisor of m and n. But thinking about the hypotenuse as a vector (if you prefer, translate it so one vertex is at the origin), the number of integral points on this line segment must be \mathrm{gcd}(m+n,m-n) +1.

To me, this felt highly promising, because this is a classic trope in olympiad problem-setting. Even without this experience, we know that this gcd is equal to G if m and n have different parities (ie one odd, one even) and equal to 2G if m and n have the same parity.

So we’re done. Being careful not to double-count the vertices, we have 3G integral points if m and n have opposite parities, and 4G integral points if m and n have the same parity, which exactly fits the pair of examples I had. But remember that we already had a pair of constructions, so (after adjusting the hypothesis to allow the second example!) all we had to prove was that the number of integral points is divisible by at least one of 3 and 4. And we’ve just done that. Counting how many integers less than 2017 have this property can be done easily, checking that we don’t double-count multiples of 12, and that we don’t accidentally include or fail to include zero as appropriate, which would be an annoying way to perhaps lose a mark after totally finishing the real content of the problem.

Question Two

2017-bmo2-q2(Keen observers will note that this problem first appeared on the shortlist for IMO 2006 in Slovenia.)

As n increases, obviously \frac{1}{n} decreases, but the bracketed expression increases. Which of these effects is more substantial? Well \lfloor \frac{n}{k}\rfloor is the number of multiples of k which are at most n, and so as a function of n, this increases precisely when n is a multiple of k. So, we expect the bracketed expression to increase substantially when n has lots of factors, and to increase less substantially when n has few factors. An extreme case of the former might be when n is a large factorial, and certainly the extreme case of the latter is n a prime.

It felt easier to test a calculation on the prime case first, even though this was more likely to lead to an answer for b). When n moves from p-1 to p, the bracketed expression goes up by exactly two, as the first floor increases, and there is a new final term. So, we start with a fraction, and then increase the numerator by two and the denominator by one. Provided the fraction was initially greater than two, it stays greater than two, but decreases. This is the case here (for reasons we’ll come back to shortly), and so we’ve done part b). The answer is yes.

Then I tried to do the calculation when n was a large factorial, and I found I really needed to know the approximate value of the bracketed expression, at least for this value of n. And I do know that when n is large, the bracketed expression should be approximately n\log n, with a further correction of size at most n to account for the floor functions, but I wasn’t sure whether I was allowed to know that.

But surely you don’t need to engage with exactly how large the correction due to the floors is in various cases? This seemed potentially interesting (we are after all just counting factors), but also way too complicated. An even softer version of what I’ve just said is that the harmonic function (the sum of the first n reciprocals) diverges faster than n. So in fact we have all the ingredients we need. The bracketed expression grows faster than n, (you might want to formalise this by dividing by n before analysing the floors) and so the a_ns get arbitrarily large. Therefore, there must certainly be an infinite number of points of increase.

Remark: a few people have commented to me that part a) can be done easily by treating the case n=2^k-1, possibly after some combinatorial rewriting of the bracketed expression. I agree that this works fine. Possibly this is one of the best examples of the difference between doing a problem leisurely as a postgraduate, and actually under exam pressure as a teenager. Thinking about the softest possible properties of a sequence (roughly how quickly does it grow, in this case) is a natural first thing to do in all circumstances, especially if you are both lazy and used to talking about asymptotics, and certainly if you don’t have paper.

Question 3

2017-bmo2-q3I only drew a very rough diagram for this question, and it caused no problems whatsoever, because there aren’t really that many points, and it’s fairly easy to remember what their properties are. Even in the most crude diagram, we see R and S lie on AC and AD respectively, and so the conclusion about parallel lines is really about similarity of triangles ARS and ACD. This will follow either from some equal angles, or by comparing ratios of lengths.

bmo2-2017-q3Since angle bisectors by definition involve equal angles, the first attack point seems promising. But actually the ratios of lengths is better, provided we know the angle bisector theorem, which is literally about ratios of lengths in the angle bisector diagram. Indeed

\frac{AR}{RC}=\frac{AQ}{CQ},\quad \frac{AS}{SD}=\frac{AP}{PD},     (1)

and so it only remains to show that these quantities are in fact all equal. Note that there’s some anti-symmetry here – none of these expressions use B at all! We could for example note that AP/PD = BP/PC, from which

\left(\frac{AS}{SD}\right)^2 = \frac{AP.BP}{PC.PD},     (2)

and correspondingly for R and Q, and work with symmetric expressions. I was pretty sure that there was a fairly well-known result that in a cyclic quadrilateral, where P is the intersection of the diagonals

\frac{AP}{PC} = \frac{AD.AB}{DC.BC},     (3)

(I was initially wondering whether there was a square on the LHS, but an example diagram makes the given expression look correct.)

There will be a corresponding result for Q, and then we would be almost done by decomposing (2) slightly differently, and once we’d proved (3) of course. But doing this will turn out to be much longer than necessary. The important message from (3) is that in a very simple diagram (only five points), we have a result which is true, but which is not just similar triangles. There are two pairs of similar triangles in the diagram, but they aren’t in the right places to get this result. What you do have is some pairs of triangles with one pair of equal angles, and one pair of complementary angles (that is, \theta in one, and 180-\theta in the other). This is a glaring invitation to use the sine rule, since the sines of complementary angles are equal.

But, this is also the easiest way to prove the angle bisector theorem. So maybe we should just try this approach directly on the original ratio-of-lengths statement that we decided at (1) was enough, namely \frac{AQ}{CQ}=\frac{AP}{PD}. And actually it drops out rapidly. Using natural but informal language referencing my diagram

\frac{AP}{PD} = \frac{\sin(\mathrm{Green})}{\sin(\mathrm{Pink})},\quad\text{and}\quad \frac{AQ}{CQ}= \frac{\sin(\mathrm{Green})}{\sin(180-\mathrm{Pink})}

and we are done. But whatever your motivation for moving to the sine rule, this is crucial. Unless you construct quite a few extra cyclic quadrilaterals, doing this with similar triangles and circle theorems alone is going to be challenging.

Remark: If you haven’t seen the angle bisector theorem before, that’s fine. Both equalities in (1) are a direct statement of the theorem. It’s not an intimidating statement, and it would be a good exercise to prove either of these statements in (1). Some of the methods just described will be useful here too!

Question 4

2017-bmo2-q4You might as well start by playing around with methodical strategies. My first try involved testing 000, 111, … , 999. After this, you know which integers appear as digits. Note that at this stage, it’s not the same as the original game with only three digits, because we can test using digits which we know are wrong, so that answers are less ambiguous. If the three digits are different, we can identify the first digit in two tests, and then the second in a further test, and so identify the third by elimination. If only two integers appear as digits, we identify each digit separately, again in three tests overall. If only one integer appears, then we are already done. So this is thirteen tests, and I was fairly convinced that this wasn’t optimal, partly because it felt like testing 999 was a waste. But even with lots of case tries I couldn’t do better. So I figured I’d try to prove some bound, and see where I got.

A crucial observation is the following: when you run a test, the outcome eliminates some possibilities. One of the outcomes eliminates at least half the codes, and the other outcome eliminates at most half the codes. So, imagining you get unlucky every time, after k tests, you might have at least 1000\times 2^{-k} possible codes remaining. From this, we know that we need at least 9 tests.

For this bound to be tight, each test really does need to split the options roughly in two. But this certainly isn’t the case for the first test, which splits the options into 729 (no digit agreements) and 271 (at least one agreement). Suppose the first test reduces it to 729 options, then by the same argument as above, we still need 9 tests. We now know we need at least 10 tests, and so the original guess of 13 is starting to come back into play.

We now have to make a meta-mathematical decision about what to do next. We could look at how many options might be left after the second test, which has quite a large number of cases (depending on how much overlap there is between the first test number and the second test number). It’s probably going to be less than 512 in at least one of the cases, so this won’t get us to a bound of 11 unless we then consider the third test too. This feels like a poor route to take for now, as the tree of options has branching at rate 3 (or 4 if you count obviously silly things) per turn, so gets unwieldy quickly. Another thought is that this power of two argument is strong when the set of remaining options is small, so it’s easier for a test to split the field roughly in two.

Now go back to our proposed original strategy. When does the strategy work faster than planned? It works faster than planned if we find all the digits early (eg if they are all 6 or less). So the worst case scenario is if we find the correct set of digits fairly late. But the fact that we were choosing numbers of the form aaa is irrelevant, as the digits are independent (consider adding 3 to the middle digit modulo 10 at all times in any strategy – it still works!).

This is key. For k\le 9, after k tests, it is possible that we fail every test, which means that at least (10-k) options remain for each digit, and so at least (10-k)^3 options in total. [(*) Note that it might actually be even worse if eg we get a ‘close’ on exactly one test, but we are aiming for a lower bound, so at this stage considering an outcome sequence which is tractable is more important than getting the absolute worst case outcome sequence if it’s more complicated.] Bearing in mind that I’d already tried finishing from the case of reduction to three possibilities, and I’d tried hard to sneak through in one fewer test, and failed, it seemed sensible to try k=7.

After 7 tests, we have at least 27 options remaining, which by the powers-of-two argument requires at least 5 further tests to separate. So 12 in total, which is annoying, because now I need to decide whether this is really the answer and come up a better construction, or enhance the proof.

Clearly though, before aiming for either of these things, I should actually try some other values of k, since this takes basically no time at all. And k=6 leaves 64 options, from which the power of two argument is tight; and k=5 leaves 125, which is less tight. So attacking k=6 is clearly best. We just need to check that the 7th move can’t split the options exactly into 32 + 32. Note that in the example, where we try previously unseen digits in every position, we split into 27 + 37 [think about (*) again now!]. Obviously, if we have more than four options left for any digit, we are done as then we have strictly more than 4x4x4=64 options. So it remains to check the counts if we try previously unseen digits in zero, one or two positions. Zero is silly (gives no information), and one and two can be calculated, and don’t give 32 + 32.

So this is a slightly fiddly end to the solution, and relies upon having good control over what you’re trying to do, and what tools you currently have. The trick to solving this is resisting calculations and case divisions that are very complicated. In the argument I’ve proposed, the only real case division is right at the end, by which point we are just doing an enumeration in a handful of cases, which is not really that bad.

Chains and antichains

I’ve recently been at the UK-Hungary winter olympiad camp in Tata, for what is now my sixth time. As well as doing some of my own work, have enjoyed the rare diversion of some deterministic combinatorics. It seems to be a local variant of the pigeonhole principle that given six days at a mathematical event in Hungary, at least one element from {Ramsay theory, Erdos-Szekeres, antichains in the hypercube} will be discussed, with probability one. On this occasion, all were discussed, so I thought I’d write something about at least one of them.

Posets and directed acyclic graphs

This came up on the problem set constructed by the Hungarian leaders. The original formulation asked students to show that among any 17 positive integers, there are either five such that no one divides any other, or five such that among any pair, one divides the other.

It is fairly clear why number theory plays little role. We assign the given integers to the vertices of a graph, and whenever a divides b, we add a directed edge from the vertex corresponding to a to the vertex corresponding to b. Having translated the given situation into a purely combinatorial statement, fortunately we can translate the goal into the same language. If we can find a chain of four directed edges (hence five vertices – beware confusing use of the word ‘length’ here) then we have found the second possible option. Similarly, if we can find an antichain, a set of five vertices with no directed edges between them, then we have found the first possible option.

It’s worth noting that the directed graph we are working with with is transitive. That is, whenever there is an edge a->b and b->c, there will also be an edge a->c. This follows immediately from the divisibility condition. There are also no directed cycles in the graph, since otherwise there would be a cycle of integers where each divided its successor. But of course, when a divides b and these are distinct positive integers, this means that b is strictly larger than a, and so this relation cannot cycle.

In fact, among a set of positive integers, divisibility defines a partial order, which we might choose to define as any ordering whether the associated directed graph is transitive and acyclic, although obviously we could use language more naturally associated with orderings. Either way, from now on we consider posets and the associated DAGs (directed acyclic graphs) interchangeably.

Dilworth’s theorem

In the original problem, we are looking for either a large chain, or a large antichain. We are trying to prove that it’s not possible to have largest chain size at most four, and largest antichain size at most four when there are 17 vertices, so we suspect there may some underlying structure: in some sense perhaps the vertex set is the ‘product’ of a chain and an antichain, or at least a method of producing antichains from a single vertex.

Anyway, one statement of Dilworth’s theorem is as follows:

Statement 1: in a poset with nm+1 elements, there is either a chain of size n+1, or an antichain of size m+1.

Taking n=m=4 immediately finishes the original problem about families of divisors. While this is the most useful statement here, it’s probably not the original, which says the following:

Statement 2: in a poset, there exists \mathcal{C} a decomposition into chains, and an antichain A such that |\mathcal{C}|=|A|.

Remark 1: Note that for any decomposition into chains and any antichain, we have |\mathcal{C}|\ge |A|, since you can’t have more than one representative from any chain in the antichain. So Statement 2 is saying that equality does actually hold.

Remark 2: Statement 1 follows immediately from Statement 2. If all antichains had size at most m, then there’s a decomposition into at most m chains. But each chain has size n, so the total size of the graph is at most mn. Contradiction.

Unsuccessful proof strategies for Dilworth

Since various smart young people who didn’t know the statement or proof of Dilworth’s theorem attempted to find it (in the form of Statement 1, and in a special case) in finite time conditions, it’s easy to talk about what doesn’t work, and try to gain intellectual value by qualifying why.

  • Forgetting directions: in general one might well attack a problem by asking whether we have more information than we need. But ignoring the directions of the edges is throwing away too much information. After doing this, antichains are fine, but maybe you need to exhibit some undirected ‘chains’. Unless these undirected chains are much longer than you are aiming for, you will struggle to reconstruct directed chains out of them.
  • Where can the final vertex go?: in a classic trope, one might exhibit a directed graph on nm vertices with neither a chain of size n+1 nor an antichain of size m+1. We attempt to argue that this construction is essentially unique, and that it goes wrong when we add an extra vertex. As a general point, it seems unlikely to be easier to prove that exactly one class of configurations has a given property in the nm case, than to prove no configurations has the same property in the nm+1 case. A standalone proof of uniqueness is likely to be hard, or a disguised rehash of an actual proof of the original statement.
  • Removing a chain: If you remove a chain of maximal length, then, for contradiction, what you have left is m(n-1)+1 vertices. If you have a long chain left, then you’re done, although maximality has gone wrong somewhere. So you have an antichain size n in what remains. But it’s totally unclear why it should be possible to extend the antichain with one of the vertices you’ve just removed.

An actual proof of Dilworth (Statement 1), and two consequences

This isn’t really a proof, instead a way of classifying the vertices in the directed graph so that this version of Dilworth. As we said earlier, we imagine there may be some product structure. In particular, we expect to be able to find a maximal chain, and a nice antichain associated to each element of the maximal chain.

dilworth-thmWe start by letting V_0 consist of all the vertices which are sources, that is, have zero indegree. These are minima in the partial ordering setting. Now let V_1 consist of all vertices whose in-neighbourhood is entirely contained in V_0, that is they are descendents only of V_0. Then let V_2 consist of all remaining vertices whose in-neighourhood is entirely contained in V_0\cup V_1 (but not entirely in V_0, otherwise it would have already been treated), and so on. We end up with what one might call an onion decomposition of the vertices based on how far they are from the sources. We end up with V_0,V_1,\ldots,V_k, and then we can find a chain of size k+1 by starting with any vertex in V_k and constructing backwards towards the source. However, this is also the largest possible size of a chain, because every time we move up a level in the chain, we must move from V_i to V_j where j>i.

It’s easy to check that each V_i is an antichain, and thus we can read off Statement 1. A little more care, and probably an inductive argument is required to settle Statement 2.

We have however proved what is often called the dual of Dilworth’s theorem, namely that in a poset there exists a chain C, and a decomposition into a collection \mathcal{A} of antichains, for which |C|=|\mathcal{A}|.

Finally, as promised returning to Erdos-Szekeres, if not to positive integers. We apply Dilworth Statement 1 to a sequence of m^2+1 real numbers a_0,a_1,\ldots,a_{m^2}, with the ordering a_i\rightarrow a_j if i\le j and a_i\le a_j. Chains correspond to increasing subsequences, and antichains to decreasing subsequences, so we have shown that there is either a monotone subsequence of length m+1.

 

BMO1 2016 – the non-geometry

Here’s a link to yesterday’s BMO1 paper, and the video solutions for all the problems. I gave the video solution to the geometric Q5, and discuss aspects of this at some length in the previous post.

In these videos, for obvious educational reasons, there’s a requirement to avoid referencing theory and ideas that aren’t standard on the school curriculum or relatively obvious directly from first principles. Here, I’ve written down some of my own thoughts on the other problems in a way that might add further value for those students who are already have some experience at olympiads and these types of problems. In particular, on problems you can do, it’s worth asking what you can learn from how you did them that might be applicable generally, and obviously for some of the harder problems, it’s worth knowing about solutions that do use a little bit of theory. Anyway, I hope it’s of interest to someone.

bmo1-2016-q1Obviously we aren’t going to write out the whole list, but there’s a trade-off in time between coming up with neat ideas involving symmetry, and just listing and counting things. Any idea is going to formalise somehow the intuitive statement ‘roughly half the digits are odd’. The neat ideas involve formalising the statement ‘if we add leading zeros, then roughly half the digits are odd’. The level of roughness required is less in the first statement than the second statement.

Then there’s the trade-off. Trying to come up with the perfect general statement that is useful and true might lead to something like the following:

‘If we write the numbers from 0000 to N, with leading zeros, and all digits of N+1 are even, then half the total digits, ie 2N of them, are odd.’

This is false, and maybe the first three such things you try along these lines are also false. What you really want to do is control the numbers from 0000 to 1999, for which an argument by matching is clear, and gives you 2000 x 4 / 2 = 4000 odd digits. You can exploit the symmetry by matching k with 1999-k, or do it directly first with the units, then with the tens and so on.

The rest (that is, 2000 to 2016) can be treated by listing and counting. Of course, the question wants an actual answer, so we should be wary of getting it wrong by plus or minus one in some step. A classic error of this kind is that the number of integers between 2000 and 2016 inclusive is 17, not 16. I don’t know why the memory is so vivid, but I recall being upset in Year 2 about erring on a problem of this kind involving fences and fenceposts.

bmo1-2016-q2As with so many new types of equation, the recipe is to reduce to a type of equation you already know how to solve. Here, because {x} has a different form on different ranges, it makes sense to consider the three ranges

x\in[0,1/25],\, x\in[1/25,1/8],\, x\in [1/8,\infty),

as for each of these ranges, we can rewrite 5y\{8y\}\{25y\} in terms of standard functions without this bracket notation. On each range we can solve the corresponding equation. We then have to check that each solution does actually lie in the appropriate range, and in two cases it does, and in one case it doesn’t.

bmo1-2016-q3Adding an appropriately-chosen value to each side allows you to factorise the quadratics. This might be very useful. But is it an invitation to do number theory and look at coprime factors and so on, or is a softer approach more helpful?

The general idea is that the set of values taken by any quadratic sequence with integer coefficients and leading coefficient one looks from a distance like the set of squares, or the set \{m(m+1), \,m\in\mathbb{N}\}, which you might think of as ‘half-squares’ or ‘double triangle numbers’ as you wish. And by, ‘from a distance’ I mean ‘up to an additive constant’. If you care about limiting behaviour, then of course this additive constant might well not matter, but if you care about all solutions, you probably do care. To see why this holds, note that

n^2+2n = (n+1)^2 - 1,

so indeed up to an additive constant, the quadratic on the LHS gives the squares, and similarly

n^2 - 7n = (n-4)(n-3)-12,

and so on. To solve the equation n^2=m^2+6, over the integers, one can factorise, but another approach is to argue that the distance between adjacent squares is much more than 6 in the majority of cases, which leaves only a handful of candidates for n and m to check.

The same applies at this question. Adding on 9 gives

n^2-6n+9 = m^2 + m -1,

which is of course the same as

(n-3)^2 = m(m+1)-1.

Now, since we now that adjacent squares and ‘half-squares’ are more than one apart in all but a couple of cases, we know why there should only be a small number of solutions. I would call a method of this kind square-sandwiching, but I don’t see much evidence from Google that this term is generally used, except on this blog.

Of course, we have to be formal in an actual solution, and the easiest way to achieve this is to sandwich m(m+1)-1 between adjacent squares m^2 and (m+1)^2, since it is very much clear-cut that the only squares which differ by one are zero and one itself.

bmo1-2016-q4I really don’t have much to say about this. It’s not on the school curriculum so the official solutions are not allowed to say this, but you have to use that all integers except those which are 2 modulo 4 can be written as a difference of two squares. The easiest way to show this is by explicitly writing down the appropriate squares, treating the cases of odds and multiples of four separately.

So you lose if after your turn the running total is 2 modulo 4. At this point, the combinatorics isn’t too hard, though as in Q1 one has to be mindful that making an odd number of small mistakes will lead to the wrong answer! As in all such problems, it’s best to try and give a concrete strategy for Naomi. And it’s best if there’s something inherent in the strategy which makes it clear that it’s actually possible to implement. (Eg, if you claim she should choose a particular number, ideally it’s obvious that number is available to choose.)

One strategy might be: Naomi starts by choosing a multiple of four. Then there are an even number of multiples of four, so Naomi’s strategy is:

  • whenever Tom chooses a multiple of four, Naomi may choose another multiple of four;
  • whenever Tom chooses a number which is one (respectively three) modulo 4, Naomi may choose another which is three (respectively one) modulo 4.

Note that Naomi may always choose another multiple of four precisely because we’ve also specified the second condition. If sometimes Tom chooses an odd number and Naomi responds with a multiple of four out an idle and illogical sense of caprice, then the first bullet point would not be true. One can avoid this problem by being more specific about exactly what the algorithm is, though there’s a danger that statements like ‘whenever Tom chooses k, Naomi should choose 100-k’ can introduce problems about avoiding the case k=50.

bmo1-2016-q6I started this at the train station in Balatonfured with no paper and so I decided to focus on the case of just m, m+1 and n, n+2. This wasn’t a good idea in my opinion because it was awkward but guessable, and so didn’t give too much insight into actual methods. Also, it didn’t feel like inducting on the size of the sequences in question was likely to be successful.

If we know about the Chinese Remainder Theorem, we should know that we definitely want to use it here in some form. Here are some clearly-written notes about CRT with exercises and hard problems which a) I think are good; b) cite this blog in the abstract. (I make no comment on correlation or causality between a) and b)…)

CRT is about solutions to sets of congruence equations modulo various bases. There are two aspects to this , and it feels to me like a theorem where students often remember one aspect, and forget the other one, in some order. Firstly, the theorem says that subject to conditions on the values modulo any non-coprime bases, there exist solutions. In many constructive problems, especially when the congruences are not explicit, this is useful enough by itself.

But secondly, the theorem tells us what all the solutions are. There are two stages to this: finding the smallest solution, then finding all the solutions. Three comments: 1) the second of these is easy – we just add on all multiples of the LCM of the bases; 2) we don’t need to find the smallest solution – any solution will do; 3) if you understand CRT, you might well comment that the previous two comments are essentially the same. Anyway, finding the smallest solution, or any solution is often hard. When you give students an exercise sheet on CRT, finding an integer which is 3 mod 5, 1 mod 7 and 12 mod 13 is the hard part. Even if you’re given the recipe for the algorithm, it’s the kind of computation that’s more appealing if you are an actual computer.

Ok, so returning to this problem, the key step is to phrase everything in a way which makes the application of CRT easy. We observe that taking n=2m satisfies the statement – the only problem of course is that 2m is not odd. But CRT then tells us what all solutions for n are, and it’s clear that 2m is the smallest, so we only need to add on the LCM (which is odd) to obtain the smallest odd solution.

Balkan MO 2016 – UK Team Blog Part Two

This short blog records the UK team at the Balkan Mathematical Olympiad 2016, held in Albania. The first part is here. A more mathematical version of this report, with commentaries on the problems, will appear at the weekend.

Sunday 8th May

Gerry and I are separated by 15km, so we can’t work together until this morning, when I also get a chance to see the UK team at their base in Vore, before they are whisked off to a beach. We now have the chance to work on the geometry together, which includes two sensible trigonometric arguments, and a nice synthetic proof only with reference to an inverted diagram. We quickly decide that this isn’t a major error, and aim to schedule our meetings as quickly as possible.

The coordinators for questions 3 and 4 seem very relaxed, and we quickly get exactly what we deserve, plus a spurious extra point for Michael because he used the phrase ‘taxicab metric’ in his rough. Thomas’s trigonometry, especially its bold claim that ‘by geometry, there are no other solutions’ when an expression becomes non-invertible, seems not to have been read entirely critically. Michael’s inverted diagram is briefly a point of controversy, but we are able to get 9 rather than the 7 which was proposed, absurdly for an argument that was elegant and entirely valid in the correct diagram up to directed angles. Question 1 is again rapid, as the coordinators say that the standard of writing is so clear that they are happy to ignore two small omissions. It transpires after discussion with, among others, the Italian leader, that such generosity may have been extended to some totally incorrect solutions, but in the final analysis, everything was fair.

So we are all sorted around 11.30am with a team score of 152, a new high for the UK at this competition. This is not necessarily a meaningful or consistent metric, but with scores of {20,21,22,29,30,30} everyone has solved at least two problems, and the three marks lost were more a matter of luck than sloppiness. Irrespective of the colours of medals this generates, Gerry and I are very pleased. We find a table in the sun, and I return to my introduction while we await progress from the other countries’ coordinations, and our students’ return.

This does not happen rapidly, so I climb the hill behind the hotel up a narrow track. A small boy is standing around selling various animals. Apparently one buys rabbits by the bucket and puppies by the barrel in Albania. Many chickens cross the road, but key questions remain unanswered. From the summit, there is a panorama across the whole Tirana area, and the ring of mountains encircling us. One can also see flocks of swifts, which are very similar to swallows, only about twice as large, and their presence in any volume makes no comment on the arrival of the British summer.

The students return mid-afternoon, and are pleased with their scores. Jamie explains their protracted misadventure with a camp bed in their ‘suite’ of rooms, and Jacob shows off his recent acquisitions: a felt hat, and a t-shirt outlining the border of a ‘greater Albania’. The fact that they didn’t have his size seems not to have been a deterrent, but hopefully the snug fit will discourage him from sporting it in Montenegro, which might lead to a political incident.

Hours pass and time starts to hang heavily as dinner approaches, with no sign of the concluding jury meeting. Finally, we convene at 10pm to decide the boundaries. The chair of the jury reads the regulations, and implements them literally. There’s a clump of contestants with three full solutions, so the boundaries are unusually compressed at 17, 30 and 32. A shame for Thomas on 29, but these things happen, and three full solutions minus a treatment of the constant case for a polynomial is still something to be happy about. Overall, 4 bronze and 2 silvers is a pleasing UK spread, and only the second time we have earned a full set of medals at this competition. The leaders are rushed back to Tirana, but hopefully the teams have enough energy left for celebration!

Monday 9th May

Today is the tutti excursion, but on the way the leaders stop at the city hall to meet the mayor of Tirana. He is new to the office, reminiscent of a young Marlon Brando, and has a bone-crushing handshake. He improvises an eloquent address, and negotiates with flair the awkward silence which follows when the floor is opened for speeches in response. In the end, the Saudi leader and I both say some words of thanks on behalf of the guest nations, and soon we are back on our way south towards Greece. The Albanian motorway is smooth and modern, but we find ourselves competing for space with communist-era windowless buses and the occasional pedestrian leading by hand a single cow.

Our destination is Berat, known as the city of a thousand windows, and home to a hilltop castle complex from which none of the thousand windows are visible. The old orthodox cathedral is now a museum of icons and other religious art, and we get a remarkably interesting tour from a local guide. The highlight is a mosaic representation of the Julian calendar, and we discuss whether the symmetries built into the construction would be more conducive to a geometry or a combinatorics question.

Back in Tirana, we reconverge at the closing ceremony, held in the theatre at a local university for the arts. While we wait, there is a photo montage, featuring every possible Powerpoint transition effect, in which Jacob and his non-standard hat usage makes a cameo appearance. We are then treated to a speech by Joszef Pelikan, who wows the crowd by switching effortlessly into Albanian, and some highly accomplished dancing, featuring both classical ballet and traditional local styles.

The ministry have taken over some aspects of the organisation here, and there is mild chaos when it’s medal time. The leaders are called upon to dispense the prizes, though the UK is snubbed for alphabetic reasons. The end result is that forty students are on stage with neither medals nor any instructions to leave. Eventually it vaguely resolves, though it is a shame there is no recognition for the two contestants (from Serbia and Romania) who solved the final problem and thus achieved a hugely impressive perfect score.

P1000371_compressed

As you can see, the UK team look extremely pleased with themselves, and Michael’s strategy to get to know all the other teams through the medium of the selfie is a storming success. A very large number of photographs are taken, and Thomas is not hiding in at least one of them. The closing dinner is back in Vore, which is very convivial and involves many stuffed vine leaves. Rosie suggests we retire somewhere quieter, but by the time we establish how to leave, she has instead dragged the rest of the team onto the dancefloor, where near-universal ignorance of the step pattern is no obstacle to enjoying the folk music. The DJ slowly transitions towards the more typical Year 11 disco playlist, and Jill feels ‘Hips don’t lie’ is a cue for the adults to leave.

Tuesday 10th May

Our flight leaves at 9pm so we have many hours to fill. It turns out that we have one of the shortest journeys. The Serbians have caught a bus at 3am, while the Cypriots are facing stopovers in Vienna and Paris! It is another beautiful day, so we hire a small van to take us to Lezhe, the hometown of our guide Sebastian, and the nearby beach at Shengjin.

We walk to the tip of the breakwater, and watch some fishermen hard at work, though apparently today is a lean catch. The buildings along the beachfront are a sequence of pastel colours, backing onto another sheer mountain, and we could easily be in Liguria. Jamie is revising for his A2-level physics and chemistry exams, which start at 9am tomorrow morning, and the rest of the team are trying to complete the shortlist of problems from IMO 2007. They progress through the questions in the sand, with a brief diversion as Jacob catches a crab in the shallows with his bare hands for no apparent reason.

After a fish-heavy lunch, we return to Vore, and I’ve run out of subsubsections to amend, so propose another walk into the hills. The animals we meet this time appear not to be for sale. Some scrabbling in the undergrowth is sadly not the longed-for bear or wolf. Many of its colleagues are loitering on the local saddle point, and our Albanian companion Elvis describes them as ‘sons of sheep’, while Renzhi confidently identifies them as cows. They are goats. There is a small but vigorous goatdog, who reacts with extreme displeasure to our attempt to climb to one viewpoint, so Gerry leads us off in another direction up the local version of the north face of the Eiger. We do emerge on the other side, dustier but with plenty of heavily silhouetted photographs.

Then the hour of departure, and time to say goodbye to the organisers, especially Adrian, Matilda and Enkel who have made everything happen, and in a wonderful spirit; and our guide Sebastian, who has set an impossibly high bar for any others to aspire to. We wish him well in his own exams, which start on Thursday! Albania has left a strong positive impression, and it will sit high on my list of places to explore more in the future, hopefully before too many others discover it. The airport affords the chance to spend the final Leke on brandy and figurines of Mother Teresa, and the flight the chance to finish problem N5, and discuss our geometry training regime with Rosie and Jacob as they work through some areal exercises.

2am is not a thrilling time to be arriving in Oxford, and 2.30am is not a thrilling time to be picking up solutions to past papers (and an even less thrilling time to discover that no such solutions have been handed in). But this has been a really enjoyable competition, at which the UK team were delightful company, and performed both strongly and stylishly at the competition, so it is all more than justified. We meet again at half-term in three weeks’ time to select the UK team for the IMO in Hong Kong, and hopefully explore some more interesting mathematics!

Balkan MO 2016 – UK Team Blog Part One

The Balkan Mathematical Olympiad is a competition for high school students from eleven countries in Eastern Europe, hosting on an annually rotating basis. For the 33rd edition it was Albania’s turn to host, and the UK was invited to participate as a guest nation.

A report with more mathematics, less frivolity and minimal chronological monotonicity can be found [SHORTLY].

Wednesday 4th May

I put the finishing touches to another draft of another chapter of my thesis, cajole the Statistics Department printer into issueing eighteen tickets, six consent forms and a terrifyingly comprehensive insurance policy, and head for Gatwick to meet the team. The UK imposes a policy that we will only take anyone to the Balkan MO once, so as to maximise the number of students who get to experience an international competition. The faces aren’t entirely new though – all six attended our winter programme in Hungary over New Year and the recent selection camp in Cambridge. They are showing the right level of excitement: the level that suggests they will enjoy the competition but won’t lose their passports in the next thirty minutes. As a point of trivia, this UK team are all sixth-formers, which, after checking not very carefully, doesn’t seem to have happened for any UK team for a long time, possibly not since 2008 when I was a contestant.

As of February this year, it’s now possible to fly direct to Albania on British Airways, which is a major improvement on the alternatives featuring either a seven-hour layover in Rome, or a nailbiting twenty-five minute interchange in Vienna. A drawback of the diary format is the challenging requirement to say interesting things about flights. In this instance, my principal challenge is to find some leftover room in my seat, as my neighbour’s physique has the same level of respect for the constraining power of armrests as the sea for the battlements of a child’s sandcastle. Across the aisle, Renzhi and Thomas face the twin challenges of a sheet of functional equations I’ve collated, and the well-meaning attempts of cabin attendants and their own neighbours to discuss said functional equations.

Later, over dinner next to Mother Teresa Airport in Tirana, we discuss the role of mathematics in recent films. Based on a sample size of at most two, we decide that `The Man who Knew Infinity’ is slightly better than `The Imitation Game’, partly because the former had fewer mathematical errors, or at least mispronunciations, about which Gerry feels strongly.

Thursday 5th May

The drawback of the new BA route is that it doesn’t run on Thursdays, so we are actually almost a full day early. Morning brings a cloudless summer’s day, and views of the imposing mountains that encircle Tirana. The students have assembled a healthy collection of past problems that they are keen to attempt as practice, and it seems natural to attempt this in a slightly more interesting place than the hotel lobby for at least some of the day.

Our guide Sebastian waves his Blackberry and rapidly conjures up an excursion to Mount Dajti, a small resort two-thirds of the way up a small mountain accessed from suburban Tirana via cable car. We follow a sign that seems to point to the summit, but the trail has distinctly horizontal ambitions. We are rewarded nonetheless with some pleasant views over the mountain range down past enclosed cerulean lakes down to the Adriatic, and even beyond to Italy.

Gerry is concerned about whether our return route is actually taking us where we want to go. He is right to be concerned, but not for that reason. It is the correct direction, but through a military base. Despite this, we make it back to the top of the cable car in the correct number of pieces. There’s the chance to alter this with some diverting activities, namely horse-riding and target-shooting. The targets are balloons, mounted on a clothes line at roughly horse-head-height. We move along.

Several years of attending maths competitions has increased both my ability to solve problems in Euclidean geometry, and also my suspicion of anything with a title like ‘Museum of National History’. I’m going to have to adjust the latter, because the recently-opened Albanian version, called BunkART, was actually excellent. It was housed in the five-level 108-room bunker built into the mountain to protect Enver Hoxha from nuclear attack. The rooms detailed the recent, fragmented history of the country, and were interspersed with aggressively modern art installations. In one basement which used to house the isotope filters, we were treated to a video loop of blood dripping onto barbed wire set to Mahler’s 5th Symphony.

While some regional competitions have adopted the ‘benign dictatorship’ approach to choosing the problems, the Balkan MO still has a problem selection phase. So I separate from the students and spend a pleasant few hours playing around with some of the proposals in the rooftop lounge of the leaders’ hotel on a balmy night in central Tirana.

Friday 6th May

The task for today is to construct a paper. A committee has selected a shortlist of problems, and we have to narrow this down to four, with one from each topic area, with an appropriate range of difficulty. The shortlist definitely contains some gems and some anti-gems, and more thoughts about these can be found in the official report.

The only dramatic moment comes when the Greek leader flourishes a webpage and an old IMO shortlist problem, which does indeed contain a proposed question as a lemma, and so it is rejected. Partly as a result of this, a medium geometry problem is chosen quickly; and the hard combinatorics shortly after lunch, since everyone likes it, and no-one can propose a better alternative. Selecting the final two problems, from number theory and algebra produces several combinatorial challenges in its own right. A rather complicated, multi-round election takes place (in which the UK, as a guest nation, does not get a say), and the final two problems are chosen, and the paper is complete.

Interestingly, this matches exactly the ideal paper I’d been hoping for last night, but with the middle questions the other way round. I think the UK students will enjoy it, and I’ll be very pleased for anyone from any country who solves the final problem. It’s fascinating to talk to the leaders of Bosnia and Montenegro, who discuss in detail why their respective education systems mean they are confident their students will struggle much more with Q3.

P1000166_compressed

In the middle of the selection process, there was a rapid transfer to the students’ site in Vore, 15km away, to attend a brief opening ceremony. There is a warm speech from the deputy minister for education, some brief dancing, and the parade of teams. The wholesaler had a bargain on quartered polo shirts, so, unlike the UK flag they are carrying, our team are invariant under both reflection and rotation.

I am summoned to be an expert on the usage of English to prepare the final version of the paper. I feel that the problem authors have done an excellent job, and there is little work to do except suggest some extra sentence breaks and delete some appearances of the word ‘the’. Pity then the other leaders who return to the Harry Fultz school to translate and approve all the versions in their respective languages. It’s midnight as a I write this, and no sign of their return…

Saturday 7th May

This is what we’ve all come for, as the contestants are transported into Tirana for the 4.5 hours of the competition paper. They are allowed to ask questions of clarification during the first half hour. Twenty-five minutes pass, and we are untroubled, so we smugly conclude we must have achieved a wording with total clarity. In fact, the exam is starting slightly late, and a mild deluge begins, mostly concerning the definition of ‘injective’. Both the era of UK students asking joke questions and UK students asking genuine questions have passed, so I am left in peace.

Somehow, Enkel Hysnelaj has single-handedly produced LaTeX markschemes for all four problems overnight, and these are discussed at some length, though it’s to his credit that they didn’t require even longer. The leaders and deputies are then wheeled off on an excursion. Our destination is Kruje, famous as the hometown of Skenderbeg, the Albanian national hero, and just before that is Fushe-Kruje, famous as the place where George W. Bush’s watch was stolen during an official visit. On the way up to the castle and museum we pass through a bazaar where there is the opportunity to buy a carpet, a felt hat, or a mug decorated with a picture of Enver Hoxha. I will be sure to drop some hints to the UK students about ideal choices of gift for Gerry.

The scripts will be arriving a bit later, so there’s the chance for a wander around Tirana in the early evening sun. My planned trip to the Museum of Secret Surveillance is sadly foiled since it hasn’t yet been opened, but there are several more statues of Skenderbeg to enjoy. The question of why he wears a goat head on his helmet remains open. Since dinner is a mere two hours after another meat-centric five course lunch, I turn my attention to the UK scripts which have just arrived. I glance at questions 1 and 4 and the latter is mostly bare while the former is pointedly well-written. The same applies to question 3. All of our nagging about clear written work has very much been rewarded here. As a personal bonus, I can therefore spare time for a late dinner. My attempt at ordering a quick snack results in about a kilo of ribs with the ubiquitous lemons, but will hopefully deflate slightly during coordination in the morning.