Tag Archives: modulo

BMO1 2017 – Questions 1-4

Posted on by
1

The first round of the British Mathematical Olympiad was sat yesterday. The questions can be found here. I recorded some thoughts on the questions while I was in Cyprus, hence the nice Mediterranean sunset above. I hope this might be useful to current or future contestants, as a supplement to the concise official solutions available. It goes without saying that while these commentaries may be interesting at a general level, they will be much more educational to students who have at least digested and played around with the questions, so consider trying the paper first. Video solutions are available here. These have more in common with this blog post than the official solutions, though inevitably some of the methods are slightly different, and the written word has some merits and demerits over the spoken word for clarity and brevity.

The copyright for these questions lies with BMOS, and are reproduced here with permission. Any errors or omissions are obviously my own.

I found the paper overall quite a bit harder than in recent years, or at least harder to finish quickly. I’ve therefore postponed discussion of the final two problems to a second post, to follow shortly.

Question One

A recurring theme of Q1 from BMO1 in recent years has been: “it’s possible to do this problem by a long, and extremely careful direct calculation, but additional insight into the setup makes life substantially easier.”

This is the best example yet. It really is possible to evaluate Helen’s sum and Phil’s sum, and compare them directly. But it’s easy to make a mistake in recording all the remainders when the divisor is small, and it’s easy to make a mistake in summation when the divisor is large, and so it really is better to have a think for alternative approaches. Making a mistake in a very calculation-heavy approach is generally penalised heavily. And this makes sense intellectually, since the only way for someone to fix an erroneous calculation is to repeat it themselves, whereas small conceptual or calculation errors in a less onerous solution are more easily isolated and fixed by a reader. Of course, it also makes sense to discourage such attempts, which aren’t really related to enriching mathematics, which is the whole point of the exercise!

Considering small divisors (or even smaller versions of 365 and 366) is sometimes helpful, but here I think a ‘typical’ divisor is more useful. But first, some notation will make any informal observation much easier to turn into a formal statement. Corresponding to Helen and Phil, let h(n) be the remainder when n is divided by 365, and p(n) the remainder when n is divided by 366. I would urge students to avoid the use of ‘mod’ in this question, partly because working modulo many different bases is annoying notationally, partly because the sum is not taken modulo anything, and partly because the temptation to use mod incorrectly as an operator is huge here [1].

Anyway, a typical value might be n=68, and we observe that 68 x 5 + 25 = 365, and so h(68)=25 and p(68)=26. Indeed, for most values of n, we will have p(n)=h(n)+1. This is useful because

p(1)+p(2)+\ldots+p(366) - \left(h(1)+h(2)+\ldots+h(365)\right)

= \left(p(1)-h(1)\right) + \ldots+\left(p(365)-h(365)\right) + p(366),

and now we know that most of the bracketed terms are equal to one. We just need to handle the rest. The only time it doesn’t hold that p(n)=h(n)+1 is when 366 is actually a multiple of n. In this case, p(n)=0 and h(n)=n-1. We know that 366 = 2 x 3 x 61, and so its divisors are 1, 2, 3, 6, 61, 122, 183.

Then, in the big expression above, seven of the 365 bracketed terms are not equal to 1. So 358 of them are equal to one. The remaining ones are equal to 0, -1, -2, -5, -60, -121, -182 respectively. There are shortcuts to calculate the sum of these, but it’s probably safer to do it by hand, obtaining -371. Overall, since p(366)=0, we have

p(1)+p(2)+\ldots+p(366) - \left(h(1)+h(2)+\ldots+h(365)\right)

= -371 + 358 + 0 = -13.

So, possibly counter-intuitively, Helen has the larger sum, with difference 13, and we didn’t have to do a giant calculation…

Question Two

Suppose each person chooses which days to go swimming ‘at random’, without worrying about how to define this. Is this likely to generate a maximum or minimum value of n? I hope it’s intuitively clear that this probably won’t generate an extreme value. By picking at random we are throwing away lots of opportunity to force valuable overlaps or non-overlaps. In other words, we should start thinking about ways to set up the swimming itinerary with lots of symmetry and structure, and probably we’ll eventually get a maximum or a minimum. At a more general level, with a problem like this, one can start playing around with proof methods immediately, or one can start by constructing lots of symmetric and extreme-looking examples, and see what happens. I favour the latter approach, at least initially. You have to trust that at least one of the extreme examples will be guess-able.

The most obvious extreme example is that everyone swims on the first 75 days, and no-one swims on the final 25 days. This leads to n=75. But we’re clearly ‘wasting’ opportunities in both directions, because there are never exactly five people swimming. I tried a few more things, and found myself simultaneously attacking maximum and minimum, which is clearly bad, so focused on minimum. Just as a starting point, let’s aim for something small, say n=4. The obstacle is that if you demand at most four swimmers on 96 days, then even with six swimmers on the remaining four days, you don’t end up with enough swimming having taken place!

Maybe you move straight from this observation to a proof, or maybe you move straight to a construction. Either way, I think it’s worth saying that the proof and the construction come together. My construction is that everyone swims on the first 25 days, then on days 26-50 everyone except A and B swim, on days 51-75 everyone except C and D swim, and on days 76-100 everyone except E and F swim. This exactly adds up. And if you went for the proof first, you might have argued that the total number of swim days is 6×75 = 450, but is at most 4n + 6(100-n). This leads immediately to n\ge 25, and I just gave the construction. Note that if you came from this proof first, you can find the construction because your proof shows that to be exact you need 25 days with six swimmers, and 75 days with four swimmers, and it’s natural to try to make this split evenly. Anyway, this clears up the minimum.

[Less experienced contestants might wonder why I was worried about generating a construction despite having a proof. Remember we are trying to find the minimum. I could equally have a proof for n\ge 10 which would be totally totally valid. But this wouldn’t show that the minimum was n=10, because that isn’t in fact possible (as we’ve seen), hence it’s the construction that confirms that n=25 is the true minimum.]

It’s tempting to go back to the drawing board for the maximum, but it’s always worth checking whether you can directly adjust the proof you’ve already given. And here you can! We argued that

450\le 4n + 6(100-n)

to prove the minimum. But equally, we know that on the n days we have at least five swimmers, and on the remaining days, we have between zero and four swimmers, so

450 \ge 5n + 0\times (100-n), (*)

which gives n\le 90. If we have a construction that attains this bound then we are done. Why have I phrased (*) with the slightly childish multiple of zero? Because it’s a reminder that for a construction to attain this bound, we really do need the 90 days to have exactly five swimmers, and the remaining ten days to have no swimmers. So it’s clear what to do. Split the first 90 days into five groups of 15 days. One swimmer skips each group. No-one swims in the final ten days, perhaps because of a jellyfish infestation. So we’re done, and 25\le n\le 90.

At a general level, it’s worth noting that in the story presented, we found an example for the minimum which we turned into a proof, and then a proof for the maximum, which we then analysed to produce a construction.

Note that similar bounding arguments would apply if we fiddled with the numbers 5, 75 and 100. But constructions matching the bounds might not then be possible because the splits wouldn’t work so nicely. This would make everything more complicated, but probably not more interesting.

Question Three

It’s understandable that lots of students attempting this paper might feel ill-at-ease with conventional Euclidean geometry problems. A good first rule of thumb here, as in many settings, is “don’t panic!”, and a more specific second rule of thumb is “even if you think you can calculate, try to find geometric insight first.”

Here, it really does look like you can calculate. A configuration based on a given isosceles triangle and a length condition and a perpendicular line is open to several coordinate approaches, and certainly some sensible trigonometry. It’s also very open to organised labelling of the diagram. You have three equal lengths, and a right-angle, as shown.

The key step is this. Drop the perpendicular from A to BC, and call its foot D. That alone really is the key step, as it reduces both parts of the question to an easy comparison. It’s clear that the line AD splits the triangle into two congruent parts, and thus equal areas and perimeters. So it is enough to show that triangle BMN has the same area as triangle ABD, and that their outer-perimeters (ie the part of its perimeter which is also the perimeter of ABC) are the same.

But they’re congruent, so both of these statements are true, and the problem is solved.

My solution could be as short as two or three lines, so for the purposes of this post all that remains is to justify why you might think of the key step. Here are a few possible entry routes:

  • You might notice that line AD induces the required property for triangle ABD.
  • You might try to find a triangle congruent to AMN, and come up with D that way.
  • There’s already a perpendicular in the question so experimenting with another one is natural, especially since the perpendicular from A has straightforward properties.
  • AMN is a right angle, and so constructing D gives a cyclic quadrilateral. We didn’t use that directly in the proof above, but constructing cyclic quadrilaterals is usually a good idea.
  • If you were trying a calculation approach, you probably introduced the length AD, or at least the midpoint D as an intermediate step.

On the video, Mary Teresa proposes a number of elegant synthetic solutions with a few more steps. You might find it a useful exercise to try to come up with some motivating reasons like the bullet points above to justify her suggestion to reflect A in M as a first step.

Question Four

BMO1 2017Q4

I wasn’t paying enough attention initially, and I calculated a_2=0\text{ or }2. This made life much much more complicated. As with IMO 2017 Q1, if trying to deduce general behaviour from small examples, it’s essential to calculate the small examples correctly!

Once you engage your brain properly, you find that a_2=0 \text{ or }3, and of course a_2=0 is not allowed, since it must be positive. So a_2=3, and a similar calculation suggests a_3=1\text{ or }6. It’s clear that the set of values for a_{k+1} depends only on a_k, so if you take a_3=1, then you’re back to the situation you started with at the beginning. If you choose to continue the exploration with a_3=6, you will find a_4=2\text{ or }10, at which point you must be triggered by the possibility that triangle numbers play a role here.

As so often with a play-around with small values, you need to turn a useful observation into a concrete statement, which could then be applied to the problem statement. It looks like in any legal sequence, every term will be a triangle number, so we only need to clarify which triangle number. An example of a suitable statement might be:

Claim: If a_n=T_k=\frac{k(k+1)}{2}, the k-th triangle number, then a_{n+1}=T_{k-1}\text{ or }T_{k+1}.

There are three stages. 1) Checking the claim is true; 2) checking the claim is maximally relevant; 3) proving it. In this case, proving it is the easiest bit. It’s a quick exercise, and I’m omitting it. Of course, we can’t prove any statement which isn’t true, and here we need to make some quick adjustment to account for the case k=1, for which we are forced to take a_{n+1}=T_{k+1}.

The second stage really concerns the question “but what if a_n\ne T_k?” While there are deductions one could make, the key is that if a_1 is a triangle number, the claim we’ve just made shows that a_n is always a triangle number, so this question is irrelevant. Indeed the claim further shows that a_{2017}\le T_{2017}, and also that a_{2017}=T_k for some odd value of k. To be fully rigorous you should probably describe a sequence which attains each odd value of k, but this is really an exercise in notation [2], and it’s very obvious they are all attainable.

In any case, the set of possible values is \{T_1,T_3,\ldots,T_{2017}\}, which has size 1009.

Final two questions

These are discussed in a subsequent post.

Footnotes

[1] – mod n is not an operator, meaning you shouldn’t think of it as ‘sending integers to other integers’, or ‘taking any integer, to an integer in {0,1,…,n-1}’. Statements like 19 mod 5 = 4 are useful at the very start of an introduction to modular arithmetic, but why choose 4? Sometimes it’s more useful to consider -1 instead, and we want statements like a^p\equiv a modulo p to make sense even when a\ge p. 19 = 4 modulo 5 doesn’t place any greater emphasis on the 4 than the 19. This makes it more like a conventional equals sign, which is of course appropriate.

[2] – Taking a_n=T_n for $1\le n\le k$, and thereafter a_n=T_k if k is odd, and $a_n=T_{k+1}$ if k is even will certainly work, as will many other examples, some perhaps easier to describe than this one, though make sure you don’t accidentally try to use T_0!

Modular arithmetic – Beyond the Definitions

Posted on by
Reply

Modular arithmetic is a relatively simple idea to define. The natural motivation is to consider a clock. The display of a standard analogue clock makes no distinction between 4am, 4pm, and 4pm next Thursday. This is a direct visualisation of the integers modulo 12. Instead of counting in the usual way, where each successive integer is different to all those considered previously, here, every time we get to a multiple of 12, we reset our count back to zero. As a result, this procedure is often referred to as `clock arithmetic’.

A common problem for good students, for example those starting the UKMT’s Senior Mentoring Scheme, is that the idea of modular arithmetic seems very simple, but it’s hard to work out how it might be useful in application to problems. My claim is that the language of modular arithmetic is often the best way to discuss divisibility properties in problems about whole numbers. In particular, the behaviour of powers (ie m^n and so forth) is nice in this context, and the notation of modular arithmetic is the only sensible way to approach it. Anyway, let’s begin with a quick review of the definitions.

Definitions

We are interested in divisibility by some fixed integer n\geq 2, and the remainders given after we divide by n. Given an integer M, we can write this as:

M=kn+a,\quad\text{ where }a=0,1,\ldots,n-1,

and this decomposition is unique. We then say that M is congruent to a modulo n. Note that working modulo n, means that we are interested in remainders after division by n (rather than a or k or M or anything else). This has the feeling of a function or algorithm applied to M. We get told what M is, then work out the remainder after division by n, and say that this is `M mod n‘.

This is fine, but it very much worth bearing in mind a slightly different interpretation. Working modulo n is a way of saying that we aren’t interested in the exact value of an integer, only where it lies on the n-clock. In particular, this means we are viewing lots of integers as the same. The `sameness’ is actually more important in lots of arguments than the position on the n-clock.

More formally, we say that a\equiv b or a is congruent to b modulo n, if they have the same remainder after division by n. Another way of writing this is that

a\equiv b\quad \iff \quad n|a-b.

Sets of integers which are equivalent are called congruence classes. For example \{\ldots,-4,-1,2,5,8,\ldots\} is a congruence class modulo 3. Note that under the first definition, we consider all elements here to be congruent to 2, but in a particular question it may be more useful to consider elements congruent to -1, or some combination.

These definitions are equivalent, but it can be more useful to apply this second definition for proving things, rather than writing out b=kn+a or whatever all the time.

Addition and Multiplication

Everything has been set up in terms of addition, so it is easy to see that addition works well on congruence classes. That is:

\text{If }a\equiv b,c\equiv d,\quad\text{then }a+c\equiv b+d.

We could argue via a clock argument, but the second definition works very well here:

\text{We have }n|a-b,n|c-d,\quad\text{and so }n|(a+c)-(b+d),\text{ exactly as required.}

We want to show that a similar result happens for multiplication. But this holds as well:

\text{If }a\equiv b,c\equiv d,\quad\text{then }n|c(b-a)\text{ and }n|b(c-d).

\Rightarrow n|ac-bd,\text{ that is }ac\equiv bd.

Let’s just recap what this means. If we want to know what 157\times 32 is modulo 9, it suffices to say that 157\equiv 4 and 32\equiv 5, and so 157\times 32\equiv 4\times 5\equiv 2. In a more abstract setting, hopefully the following makes sense:

\text{ODD}\times\text{ODD}=\text{ODD};\quad \text{EVEN}\times\text{EVEN}=\text{EVEN};\quad \text{ODD}\times\text{EVEN}=\text{EVEN}.

This is exactly the statement of the result in the case n=2, where the congruence classes are the odd integers and the even integers.

Powers

What happens if we try to extend to powers? Is it the case that

\text{if }a\equiv b,c\equiv d,\quad\text{then }a^c\equiv b^d? Continue reading →

Senior Mentoring – Solving equations in integers

Posted on by
Reply

At school, we learn how to solve equations like 4x+3=-5. Sometimes the answer is an integer (that is, a whole number), sometimes it isn’t. If we change that -5 to a -6, the solution to the equation above won’t be an integer any more. What is more, if we change the 5 to \sqrt{5}, the solution won’t even be rational (that is, a normal fraction that looks like \frac{p}{q}). But, the key point is that in the introduction to the chapter on linear equations, or whatever they call it, in a textbook, there will be an explanation of how to solve this generic class of problems, which will work whether the numbers in the equation are integers, fractions, or even complex numbers!

Later, we move on to quadratic equations. Spotting factorisations is a good way to get started, then you could learn the quadratic formula to use in those cases where the factors are harder to spot. Alternatively, there’s the method of ‘completing the square’, which takes more steps, but means you can do the arithmetic in clear stages. Then, if you think about why the quadratic formula works, you realise that you are just completing the square for all quadratics (using a, b, c in place of any numerical coefficients). In other words, though there are a few different ways of approaching the problem, the sensible methods are essentially the same. And then you might get problems about logarithms or matrices for which you use your new knowledge about these objects to turn the question into a quadratic equation, say. At all times, there’s an implicit assumption that any question can be turned into an equation which you ‘know how to solve’.

So when you first come across a problem which asks you to find integer solutions to an equation, as have appeared a few times on this year’s Senior Mentoring scheme, it is hard to know where to start. You could try to solve it as if it wasn’t about integers, then select the integer solutions at the end. But this could be difficult, or might not even make sense. You might have a condition that x is odd: what does this mean if x isn’t even an integer? You also often start making sensible-looking substitutions: x is odd, so write x=2n+1 for some n which is also an integer, then work with n. But this can sometimes cause you to end with a huge number of variables which you can’t really relate to, and horribly complicated expressions.

As with so much of maths, experience is very useful. If you’ve seen solutions to twenty moderately tricky integer equations, you’ll have more ideas about how to think about starting another problem. So here are a few tricks that might come in handy.

Smallest solution: Are you stuck trying to prove there aren’t any solutions? Do all your substitutions just give more complicated versions of the original equation? What about considering the smallest solution? You might have to be careful about what you mean by ‘small’, but suppose you consider the smallest solution x, and end up finding a smaller solution x'<x. What could this mean? Well it can only mean that there isn’t a smallest solution! In other words, there are no solutions. You should think about why the fact that we are working with integers means that if there is any solution there must be a smallest one. Then see if you can find all solutions in positive (>0) integers to x^2-2y^2=0. Continue reading →