Welcome to NRICH.

 
IMO Question
By Anthony Cardell Tony on Tuesday, September 11, 2001 - 02:44 am:

This problem looks easy, but even at the international level, the average score (out of seven) was less than one:

Let a, b, c, d be integers with a > b > c > d > 0. Suppose that

ac + bd = (b + d + a - c)(b + d - a + c).

Prove that ab + cd is not prime.

By Anthony Cardell Tony on Tuesday, September 11, 2001 - 02:45 am:

By the way...most competitors had about an hour left to do it..

By David Loeffler on Tuesday, September 11, 2001 - 11:11 am:

There is a solution (in fact, two solutions) on the web at the Wolfram Research IMO site

(I scored 0 on that question - it was by far the hardest problem on this year's papers. Our team leader showed me my marked script afterwards; the comment on this question was "Random attempts at factorisation - 0".)

As for difficulty, I don't agree that it looks easy. The immediate impression one gets is that it must be either trivial or furiously difficult, and I've yet to see a trivial IMO problem.

David

By Arun Iyer on Tuesday, September 11, 2001 - 07:50 pm:

I was just going through the site for the medal winners and I see.....

CONGRATS DAVID LOEFFLER FOR WINNING THE SILVER MEDAL IN MATHS OLYMPIAD

That was absolutely brilliant!!!!

love arun

By Anthony Cardell Tony on Wednesday, September 12, 2001 - 03:07 am:

WOW..I am very impressed that you went to the IMO...and placed best of the United Kingdom team!!

Would you recommend any particular websites or books to help learn the advanced math needed to do well in the USA Math Olympiad (similar to IMO)? I really want to be good at math..but I got a zero last year on the USAMO.

By David Loeffler on Wednesday, September 12, 2001 - 10:22 am:

I personally find that the best way to learn how to do IMO-type problems is to do IMO-type problems. There are quite a few compilations of old IMO problems, with solutions, available (Murray Klamkin has done two books of them, which are published by the Mathematical Assosciation of America).

There is also a reading list on an
IMO website.
You could also look at www.imo.math.ca#anchor (there is no single IMO website, but various ones run by different people).

Also, check out Crux Mathematicorum magazine. This is published 8 times a year and has loads of problems in each issue, both from IMOs and other olympiads and original ones devised specially for the magazine. More information at journals.cms.math.ca/CRUX/. I highly recommend Crux (although it does tend to concentrate on geometry a bit too much; but since geometry has historically been a weakness of UK IMO teams, this was a good thing from my point of view).

If it's a gentle introduction to problem solving you're after, I know of no better book than the [British] Mathematical Olympiad Handbook, which is based on questions from the British olympiad but should be applicable to most others. It makes a point of carefully explaining all its solutions - a lot of books tend to make steps in proofs that appear totally random, without saying how they were arrived at; this is what the BMO handbook tries to avoid.

Anyway, that should keep you going for a while - good luck! Maybe I'll see you at next year's IMO (where I will probably be working as a volunteer - it's in the UK, in Glasgow. I will be too old to compete myself L)

David

By Anthony Cardell Tony on Thursday, September 13, 2001 - 03:28 am:

Thanks for your websites and references! Unfortunately I highly doubt I will be at next year's IMO. I will keep trying though...Thanks again!

By Michael Doré on Friday, September 14, 2001 - 01:09 am:

For Q6, the following is certainly a lot less elegant than the solutions David has referred, but I think it's a bit easier to see assuming it is correct of course. (I don't see how anyone, even IMO people, could spot solution 1. Why would you think of splitting ab + cd up like that? Solution 2 looks a little more likely, but still pretty well impossible, unless you happened to think of geometry.)

Anyway, we have:

ac + bd = (b + d + a - c)(b + d - a + c)

So ac + bd = (b + d)2 - (a - c)2 = -a2 + b2 - c2 + d2 + 2bd + 2ac

And so b2 + bd + d2 = a2 - ac + c2.

Multiply through by 4 and write in terms of squares:

3(b + d)2 + (b - d)2 = 3(a - c)2 + (a + c)2

Re-arranging and using the difference of two squares:

3(a + b - c + d)(-a + b + c + d) = (a + b + c - d)(a - b + c + d)

Set:

K = a + b + c - d
L = a + b - c + d
M = a - b + c + d
N = -a + b + c + d

So K,L,M,N are all integers. Clearly K,L,M are positive integers since a - d, a - c, a - b > 0. But we have 3LN = KM so it follows that N is also a positive integer. And K > L > M > N. The difference between any two is even, thus they are all odd or all even.

Adding the four equations we obtain K + L + M + N = 2(a + b + c + d). Subsequently:

K + L + M - N = 4a
K + L - M + N = 4b
K - L + M + N = 4c
-K + L + M + N = 4d

Then 16ab + 16cd = (K + L + M - N)(K + L - M + N) + (K - L + M + N)(-K + L + M + N)

The right hand side looks horrible but it simplifies using difference of two squares to become:

(K + L)2 - (M - N)2 + (M + N)2 - (K - L)2 = 4KL + 4MN

For a contradiction suppose ab + cd = (KL + MN)/4 is prime. We know 3LN = KM.

We show that (K,M), (K,N), (L,M), (L,N) are either all 1 or all 2.

If K,L,M,N are even then set K = 2K', L = 2L', M = 2M', N = 2N'. Then K'L' + M'N' is prime and 3L'N' = K'M'. It is clear that (K',M') = (K',N') = (L',M') = (L',N') = 1 otherwise the expression wouldn't be prime, which shows that (K,M) = (K,N) = (L,M) = (L,N) = 2.

If K,L,M,N are odd then (K,M) = (K,N) = (L,M) = (L,N) = 1. Otherwise at least one pair would have an odd common factor > 1, which (KL + MN)/4 would also have to have. Since the expression is a prime, it would have to equal its odd factor. This is impossible; it is easy to check this as there are only finitely many cases.

This means that we can find integers P,Q,R,S such that 0 < S < R < Q < P with (P,R) = (P,S) = (Q,R) = (Q,S) = 1 and 3QS = PR (take P,Q,R,S to be K/2,L/2,M/2,N/2 in the first case and K,L,M,N in the second).

Then:

P|3QS

Since (P,S) = 1, we have P|3Q. Now it can't be that P|Q since P > Q > 0. So P is a multiple of 3.

Likewise:

R|3QS

Since (Q,R) = 1, R|3S. We can't have R|S as R > S > 0 so we know that R is also a multiple of 3.

So P,R are both multiples of 3. But P,Q,R,S are either K/2,L/2,M/2,N/2 respectively, or K,L,M,N. This means that in either case K,M are multiples of 3, so ab + cd is a multiple of 3. The only prime which is a multiple of 3 is 3 itself, and it is easy to check ab + cd cannot equal 3. So we apparently have our result.

Is that correct?

By Michael Doré on Friday, September 21, 2001 - 08:46 pm:

Speaking of CRUX, David, congratulations on getting an article published in the Mayhem section! If you're lucky your result could become known as the Loeffler-Ptolemy theorem...

By Olof Sisask on Friday, September 21, 2001 - 11:38 pm:

Oh what's this? Whatever it is, it sounds impressive. Well done David!

Does anyone know if universities usually subscribe to magazines like CRUX or do you have to subscribe yourself?

Regards,
Olof

By Michael Doré on Sunday, September 23, 2001 - 10:14 pm:

It's a generalisation of Ptolemy's theorem. Ptolemy's theorem states that for a convex, cyclic quadrilateral ABCD then we have AC.BD = AB.CD + BC.AD. This is also used in the second proof David referred in his first message.

David's result generalises this for quadrilaterals which aren't necessarily cyclic. I'll let him describe the details...

As for CRUX, I would have thought that universities would keep them in stock somewhere. But ideally if you were going to use it, you should have your own copy, since you will probably want to refer to it at odd intervals, in between gargantuan efforts at solving the problems which vary in difficulty from trivial to incredibly difficult (namely the Challenge Board problems, and a few of the questions proposed by the readers at the end of the magazine). I think you can obtain subscription from the Canadian Mathematical Society.

It is clear that this type of magazine will not be every mathematicians' cup of tea - you need to have a special enthusiasm for solving hard and interesting problems involving only the most basic maths. Or maybe I'm just bitter because it has so many problems I can't do...

By Arun Iyer on Monday, September 24, 2001 - 07:28 pm:

Loeffler-Ptolemy theorem eh!!!
i am eagerly waiting to see this one DAVID!!!

Hey!!i just had this wonderful thought.If david's theorem gets established,i could tell everyone that this great mathematician is my friend.Man!!!would that make me proud!!!!!

love arun