BMO2 2019

The second round of the British Mathematical Olympiad was taken on Thursday by the 100 or so top scoring eligible participants from the first round, as well as some open entries. Qualifying for BMO2 is worth celebrating in its own right. The goal of the setters is to find the sweet spot of difficult but stimulating for the eligible participants, which ultimately means it’s likely to be the most challenging exam many of the candidates sit while in high school, at least in mathematics.

I know that lots of students view BMO2 as something actively worth preparing for. As with everything, this is a good attitude in moderation. Part of the goal in writing about the questions at such length is because I think at this level it’s particularly easy to devote more time than needed to preparation, and use it poorly. This year time is tight at the end of semester, and so what follows is closer to a set of complete solutions than usual, for which apologies, although I hope it is still possible to get a sense of how one might have come across the solutions yourself. Of course, this means that what follows will certainly spoil the problems for anyone who hasn’t tried them by themselves already.

The copyright for the problems is held by BMOS, and reproduced here with permission.

Question 1

As if often the case in geometry questions, what you’ve been asked to prove here isn’t the most natural property of the configuration. A good first step would be to see if there are stronger statements which are true.You are asked to show that triangle BPE is isosceles, but you aren’t told which of the three vertices is the apex. In fact, the task is to show that $BP=EP$ or, alternatively, $\angle BEP=\angle PBE$ . It’s not in general true that BE is equal to BP=EP. Unless you’re very unlucky, you can establish this from one diagram.

Now, you don’t immediately know whether it’s going to be easier to show that two lengths are equal, or that two angles are equal. However, you know that P lies on the perpendicular bisector of BC, hence BP=CP, which is a big clue. In particular, this means that P would be the centre of the circle through BCE. This clearly implies the given result, so deciding to prove this instead is a good strategy.

There are now a number of ways to prove this. Note that D lies on the altitude from A, and the feet of the perpendiculars from D to sides AB and AC are both present in the configuration so (just as for the orthocentre diagram) we can calculate most of the angles involving {A,B,C,D,E}.

For example, ABDE is cyclic, so $\angle BED=\angle BAD = 90-\hat{B}$ , hence $\angle AEB=\hat{B},\,\angle EBA=\hat{C}$ . This shows that AB is tangent to the circumcircle of BCE. But then the line L is a radius of this circle, and so its centre must be P, the unique point on L which is equidistant from B and C.

Alternatively, we could directly calculate $\angle BEC=180-\hat{B}$ and $\angle CBP=90-\hat{B}$ . But BPC is isosceles so $\angle BPC=2\hat{B}$ . In general, the converse of ‘angle at centre is twice angle at circumference’ does not hold, but when we know P is equidistant from B and C this does hold, and so the angle relations precisely confirm that P is the centre of the circle through BPE.

My intention had been that the triangle would be acute-angled, to reduce the number of diagram options based on the magnitude of $\hat{B}$ . If pursuing this second approach, one would need to be careful to account for whether P is on the same side or the opposite side of BC to E. That said, unless you do something very exotic, it should be exactly the same argument or calculation, and such a case distinction probably isn’t very important.

Question 2

First, a short remark. As stated, if n=5, a piece could move 3 squares to the left then 4 squares up, by Pythagoras. Handling all such options is likely to be quite annoying, since some values of n can be written in this Pythagorean form, and others cannot. This brings us to some good general principles for olympiad problems which look like this one:

A construction, when one exists, will probably be possible using simple versions of the allowed moves / structures.
An argument why a construction is impossible should probably be based on ideas which treat the simple moves similarly to the more complicated moves.

The setup of the problem encourages you to think about dividing the board into $n^2$ sub-boards, each with dimensions $n\times n$ . But you also have to ensure that there is initially one piece in each row and column, so the easiest way to do that is to put all the pieces on the main diagonal. Now you notice that n of the sub-boards have some pieces on them, and the rest have none. In the case n=2, you can then come up with a construction as shown below

by moving sub-boards around, rather than by worrying about individual pieces. Whether you think about n=4 separately, or go straight for the case n even, you might notice that this idea generalises.

Since you should explain where you are using the fact that n is even in this construction, you might choose to do this by saying that you are now really dividing the whole board into $2n \times 2n$ sub-boards (which is possible precisely when n is even) and defining your construction entirely through the sub-boards corresponding to the main diagonal.

The fact that this construction doesn’t work when n is odd is not a valid argument that no construction works when n is odd. The case n=1 is content-free and adds little insight, but n=3 is already large enough to be challenging to handle with a case analysis. Roughly speaking, a good piece of advice is that if nothing straightforward seems to work as a construction, start looking for an argument why there’s no construction.

We are on a square grid, and are looking for a contradiction depending on the parity of n. This is a big clue to consider a so-called colouring argument. (Remember, after all, how non-magical chessboards are coloured!) Let’s say that the colours and black and white, and the colours and diagonals are black, so (since n is odd) there is one more black square than white.

The simplest observation is that if a piece moves n steps up/down/left/right, the colour of its square changes. Furthermore, this remains true if one moves a distance n *not* parallel to the axes. Think about the parities of the side lengths of a integer-side-length right-angled triangle whose hypotenuse is odd.

So if we were to have a construction, if it started with an odd number of pieces on black, and an even number on white (note n pieces in total and n is odd!) then it will finish with an even number on black, and an odd number on white. (*)

At this point, return to the question. What haven’t we used? We haven’t used the fact that there is one piece in each row and in each column, both before and after. It would be reasonable to guess at this stage that such a configuration allows one of the options in (*) but not both! This turns out to be true. If you want one piece in each row and in each column, then you must have an odd number on black, and an even number on white.

[At this point the fact that the board has dimensions $n^2\times n^2$ ceases to be important, so I will abuse notation and assume the board has dimensions $n\times n$ .]

How to prove this? I have a number of suggestions, and will not give full details for any of them.

For each piece, count the total number of black squares and white squares across its row and column (including the piece’s square’s colour twice). A white piece gives equal counts, while a black piece gives either two more blacks or two fewer blacks. If we now add up these counts over all pieces, we should get two more blacks overall, since every square is counted exactly twice. So by computing this sum in two different ways (so-called double-counting), and working modulo 4, it must hold that the number of pieces on black squares is odd.
The pieces define a bijection between rows and columns, which we might as well label {1,2,…,n}. Then if a piece matches a row and a column with the same parity, it is on a black square, and if the parities are different, it is on a white square. It might now seem obvious that the number of white pieces must be even. This does need to be justified, and by comparing odd rows and odd columns (which are sometimes matched by a piece on a black square in an odd row and column), we find that the number of white pieces in odd rows is equal to the number of white pieces in even rows, and so the total number of white pieces is even.
Similarly, the mapping from row labels to column labels is a permutation of {1,2,…,n}. Look at any cycle of this permutation. A white piece corresponds to changing the parity of the labels as you go round the cycle. Therefore each cycle is driven by some number of pieces, of which an even number are white.
On can also induct on n, by removing a row and column containing a piece on a square of some colour. Before starting this, it would be wise to make a corresponding conjecture for the case where n is even, and induct alternately between the two hypotheses. (Any approach along these lines will be hugely complicated if still working with the assumption that the board is $n^2\times n^2$ .)

Question 3

If you take the sums of all the possible subsets, and study their values modulo p, intuitively it doesn’t feel like there anything special about zero. All congruences should be roughly equally likely. There are $2^{p-1}-1$ non-empty subsets, and by Fermat’s Little Theorem, this is divisible by p, which is a good clue that the answer might be $\frac{2^{p-1}-1}{p}$ .

However, one needs justification that all congruences are equally likely to appear as the sum. (This wouldn’t be true if we considered all subsets, for example, or all non-empty proper subsets.)

The most natural way to achieve this is to group the subsets into collections of size p, with one representative of each congruence in every collection. That’s easier said than done, however, since it’s not clear at all how to generate p-1 subsets from a given subset, let alone p-1 subsets with the right congruence classes amongst the sums.

One possibility that seems promising is adding some number i to all the elements in the subset, and then reducing modulo p. The issue is that this will give us some zeros, which are not currently allowed. But maybe this is actually a more natural question: how many subsets of P={0,1,…,p-1} have sum divisible by p?

[In what follows, $\varnothing$ is the empty set, which is a subset of P. The sum of its elements is zero.]

Because suppose we have a subset $A\subset P$ , and we add on some number $i\in\{0,1,\ldots,p-1\}$ , to obtain subsets $A_0,A_1,\ldots,A_{p-1}$ . Clearly $A_0=A$ . But what about the rest? If $A=\varnothing$ or P, then all of $A_0,A_1,\ldots,A_{p-1}$ are equal to A. But otherwise, suppose $A=A_i$ . Then starting from any element $a\in A$ , we have $a+i\in A_i$ and thus $a+i\in A$ . Repeating, we find $a+i,a+2i,a+3i,\ldots \in A$ . Crucially, since p is prime, $\{a,a+i,a+2i,\ldots\}=P$ , and so either A=P, or there was no such element a, meaning $A=\varnothing$ . A similar argument can be used to show that $A_i\ne A_j$ for each $i\ne j$ .

In conclusion, we can partition all the subsets of P apart from $\varnothing, P$ into collections of size p. Suppose $|A|=k$ in the previous description. Then

$\sum_{a\in A_i}a = \sum_{a\in A}(a+i)\equiv ki+\sum_{a\in A}a,\;\mod p.$

Since $0<k<p$ , this takes every congruence class exactly once as i varies in {0,1,\ldots,p-1}.

We conclude that the number of subsets of P which have sum divisible by p is $\frac{2^p-2}{p} + 2$ , where the +2 accounts for $\varnothing,P$ , both of which have sum divisible by p.

Finally, we have to convert this back to the original question. For any subset B of {1,2,…,p-1} with sum divisible by p, we associate two subsets of {0,1,2,…,p} with sum divisible by p, namely B and $B\cup\{0\}$ . This is certainly reversible, and gives us $\frac{2^{p-1}-1}{p}+1$ subsets of {1,2,…,p-1} with sum divisible by p. However, we were specifically told not to include the empty set, so in fact the total number of non-empty subsets with sum divisible by p is $\frac{2^{p-1}-1}{p}$ , exactly as we’d suspected.

Question 4

I also wrote this problem, but it’s not one of my favourites. As with all functional equations, it’s good to get a handle on the setup by substituting in natural values, and here it’s clearly useful to consider x=1, since this gives 4f(1)=4, and so f(1)=1, which we can then eliminate from the statement, leaving

$f(x^4)+f(x^2)+f(x)=x^4+x^2+x.$ (*)

Don’t forget that you’re not allowed to assume that f is a polynomial! This will probably turn out to be the case, but you can’t use this unless you somehow prove it. The golden rule of functional equations is:

“Choose substitutions to make as much cancel as possible (but not everything).”

The fact that the powers 1,2,4 form a geometric progression is useful, because then substituting $x^2$ gives

$f(x^8)+f(x^4)+f(x^2)=x^8+x^4+x^2,$

which has lots of terms in common with (*) on both sides, and so will lead to lots of cancellation when we compare. In particular, we obtain

$f(x^8)-f(x)=x^8-x,$

$f(x^8)-x^8 = f(x)-x.$

At this point, it’s worth taking a step back, and thinking about what this means. It means that if we know the value of f at x, then we also know the values of f at

$\{\ldots,x^{1/64},x^{1/8},x,x^8,x^{64},\ldots\}.$ (**)

In particular, if $f(x)=x+c$ , then $f(x^{8^{-n}})=x^{8^{-n}}+c$ . This seems promising, because large values of n might give us a contradiction to the increasing property if c is not zero. Indeed, by taking n large so that $x^{8^{-n}}$ is close to 1, we know that $f(x^{8^{-n}})\ge f(1)=1$ , and so we must have $c\ge 0$ . As in the arguments to follow, note that it’s not important to clarify exactly how large n has to be for this step of the argument to work. It suffices that we can choose n so as to make $x^{8^{-n}}$ arbitrarily close to 1.

For clarity, let’s assume now that x>1. Then sets of the form (**) partition the interval of real numbers $(1,\infty)$ . We now want to relate the values of c corresponding to different sets of this form.

Precisely, take $x<y<x^8$ , for which $f(y)=y+d$ . Then we have $x^{8^{-n}}<y^{8^{-n}}<x^{8^{-(n-1)}}$ from which, applying f to all these values and using the increasing property:

$x^{8^{-n}}+c \le y^{8^{-n}}+d \le x^{8^{-(n-1)}}+c.$

Again, if n is large, the first summand in each of these expressions vanishes to zero, and the only possibility is that c=d.

As always, it’s good to return to the original equation after a big deduction, and here this is achieved by taking $y=x^2,\,y=x^4$ , from which we find

$f(x)=x+c,\quad f(x^2)=x^2+c,\quad f(x^4)=x^4+c,$

and so the original equation holds only if c=0.

Exactly the same argument works to show that $f(x)=x$ when x<1, though one does have to check it separately since many but not all of the inequalities I just used will be reversed. So the reason why it’s not my favourite is that one has to do exactly the same argument twice. This is a requirement of including +f(1) and +1 in the statement, without which we could have defined the function’s domain as $(1,\infty)$ . Although broadly irrelevant to the main body of the solution, this seemed a good way to obscure the deeply relevant observation that the exponents 1,2,4 form a geometric series.

However, the rough method is broadly similar to standard approaches to Cauchy’s functional equation $f(x+y)=f(x)+f(y)$ , where one establishes the form of the solution on $\mathbb{Q}$ , and then on other sets which look a bit like $\mathbb{Q}$ , for example $\mathbb{Q}+\alpha$ where $\alpha\in\mathbb{R}$ , and use some condition like ‘f increasing’ to piece them together. More exotic things can happen though, when you don’t have such a condition…

1 thought on “BMO2 2019”

Charlie Thomas on May 12, 2020 at 10:51 pm said:

Hi! Thank you for posting this! I’m struggling to understand what you’re doing on question 3.
Specifically, I’m unclear how if A is the empty set then how A1, A2, … are equal to A?

Also, I’m confused by this sentence: Crucially, since p is prime, {a,a+i,a+2i, ….}=P, and so either A=P, or there was no such element a, meaning A={}(empty set).

Any extra guidance you could provide would be really appreciated. Thank you!

Reply ↓

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

BMO2 2019

1 thought on “BMO2 2019”

Leave a Reply Cancel reply

Share this:

Like this:

Related

1 thought on “BMO2 2019”

Leave a Reply Cancel reply