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

where and 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 with even weight and the number of positive integers at most 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 n in binary. As 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

we can see that each bracket looks like 11…100…0 when written in binary. Also, the condition that 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 , as

and the sequence is increasing, so each bracket is positive. As each sequence of s corresponds uniquely to an integer, this means we just want to count sequences of 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 subsets of size (2k+1), so the question reduces to finding a closed form for .

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

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

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

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 . 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 be the graphs of the quadratic functions , where . The graphs cross at distinct points A and B. The four tangents to at~A and B form a convex quadrilateral which has an inscribed circle. Prove that the graphs and 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 , 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 (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 , 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 but is not the foot of the perpendicular form B to . 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 . 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.

Advertisement