[PDF] IMO 2008 Shortlisted Problems 49th International Mathematical Olympiad. Spain

View - Download IMO 2008 Shortlisted Problems

Previous PDF

Next PDF

49thInternational Mathematical Olympiad

Spain 2008

Shortlisted Problems with Solutions

Contents

Contributing Countries & Problem Selection Committee 5

Algebra7

Problem A1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Problem A2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Problem A3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Problem A4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Problem A5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Problem A6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Problem A7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Combinatorics21

Problem C1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Problem C2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Problem C3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Problem C4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Problem C5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Problem C6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Geometry29

Problem G1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Problem G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Problem G3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Problem G4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Problem G5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Problem G6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Problem G7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Number Theory43

Problem N1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Problem N2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Problem N3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Problem N4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Problem N5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Problem N6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Contributing Countries

Australia, Austria, Belgium, Bulgaria, Canada, Colombia,Croatia, Czech Republic, Estonia, France, Germany, Greece, Hong Kong, India, Iran, Ireland, Japan, Korea (North), Korea (South), Lithuania, Luxembourg, Mexico, Moldova, Netherlands, Pakistan, Peru, Poland, Romania, Russia, Serbia, Slovakia, South Africa, Sweden, Ukraine, United Kingdom, United States of America

Problem Selection Committee

Vicente Mu˜noz Vel´azquez

Juan Manuel Conde Calero

G´eza K´os

Marcin Kuczma

Daniel Lasaosa Medarde

Ignasi Mundet i Riera

Svetoslav Savchev

AlgebraA1.Find all functionsf: (0,∞)→(0,∞) such that f(p)2+f(q)2 f(r2) +f(s2)=p2+q2r2+s2 for allp,q,r,s >0 withpq=rs. Solution.Letfsatisfy the given condition. Settingp=q=r=s= 1 yieldsf(1)2=f(1) and hencef(1) = 1. Now take anyx >0 and setp=x,q= 1,r=s=⎷ xto obtain f(x)2+ 1

2f(x)=x2+ 12x.

This recasts into

xf(x)2+x=x2f(x) +f(x),?xf(x)-1??f(x)-x?= 0.

And thus,

for everyx >0,eitherf(x) =xorf(x) =1 x.(1)

Obviously, if

f(x) =xfor allx >0 orf(x) =1 xfor allx >0 (2) then the condition of the problem is satisfied. We show that actually these two functions are the only solutions. So let us assume that there exists a functionfsatisfying the requirement, other than those in (2). Thenf(a)?=aandf(b)?= 1/bfor somea,b >0. By (1), these values must be f(a) = 1/a,f(b) =b. Applying now the equation withp=a,q=b,r=s=⎷ abwe obtain (a-2+b2)/2f(ab) = (a2+b2)/2ab; equivalently, f(ab) =ab(a-2+b2) a2+b2.(3) We know however (see (1)) thatf(ab) must be eitherabor 1/ab. Iff(ab) =abthen by (3) a -2+b2=a2+b2, so thata= 1. But, asf(1) = 1, this contradicts the relationf(a)?=a. Likewise, iff(ab) = 1/abthen (3) givesa2b2(a-2+b2) =a2+b2, whenceb= 1, in contradiction tof(b)?= 1/b. Thus indeed the functions listed in (2) are the only two solutions. 8 Comment.The equation has as many as four variables with only one constraintpq=rs, leaving

three degrees of freedom and providing a lot of information.Various substitutions force various useful

properties of the function searched. We sketch one more method to reach conclusion (1); certainly there are many others. Noticing thatf(1) = 1 and setting, first,p=q= 1,r=⎷ x,s= 1/⎷x, and thenp=x,q= 1/x, r=s= 1, we obtain two relations, holding for everyx >0, f(x) +f?1 x? =x+1xandf(x)2+f?1x? 2 =x2+1x2.(4)

Squaring the first and subtracting the second gives 2f(x)f(1/x) = 2. Subtracting this from the second

relation of (4) leads to f(x)-f?1 x?? 2 x-1x? 2 orf(x)-f?1x? x-1x? The last two alternatives combined with the first equation of(4) imply the two alternatives of (1). 9

A2.(a) Prove the inequality

x 2 (x-1)2+y2(y-1)2+z2(z-1)2≥1 for real numbersx,y,z?= 1 satisfying the conditionxyz= 1. (b) Show that there are infinitely many triples of rational numbersx, y, zfor which this inequality turns into equality.

Solution 1.(a) We start with the substitution

x x-1=a,yy-1=b,zz-1=c,i.e.,x=aa-1, y=bb-1, z=cc-1. The inequality to be proved readsa2+b2+c2≥1. The new variables are subject to the constraintsa,b,c?= 1 and the following one coming from the conditionxyz= 1, (a-1)(b-1)(c-1) =abc.

This is successively equivalent to

a+b+c-1 =ab+bc+ca,

2(a+b+c-1) = (a+b+c)2-(a2+b2+c2),

a

2+b2+c2-2 = (a+b+c)2-2(a+b+c),

a

2+b2+c2-1 = (a+b+c-1)2.

Thus indeeda2+b2+c2≥1, as desired.

(b) From the equationa2+b2+c2-1 = (a+b+c-1)2we see that the proposed inequal- ity becomes an equality if and only if both sumsa2+b2+c2anda+b+chave value 1. The first of them is equal to (a+b+c)2-2(ab+bc+ca). So the instances of equality are described by the system of two equations a+b+c= 1, ab+bc+ca= 0 plus the constrainta,b,c?= 1. Elimination ofcleads toa2+ab+b2=a+b, which we regard as a quadratic equation inb, b

2+ (a-1)b+a(a-1) = 0,

with discriminant

Δ = (a-1)2-4a(a-1) = (1-a)(1 + 3a).

We are looking for rational triples (a,b,c); it will suffice to havearational such that 1-a and 1 + 3aare both squares of rational numbers (then Δ will be so too). Seta=k/m. We wantm-kandm+ 3kto be squares of integers. This is achieved for instance by taking m=k2-k+ 1 (clearly nonzero); thenm-k= (k-1)2,m+ 3k= (k+ 1)2. Note that dis- tinct integerskyield distinct values ofa=k/m. And thus, ifkis any integer andm=k2-k+ 1,a=k/mthen Δ = (k2-1)2/m2and the quadratic equation has rational rootsb= (m-k±k2?1)/(2m). Choose e.g. the larger root, b=m-k+k2-1

2m=m+ (m-2)2m=m-1m.

10 Computingcfroma+b+c= 1 then givesc= (1-k)/m. The conditiona,b,c?= 1 eliminates onlyk= 0 andk= 1. Thus, askvaries over integers greater than 1, we obtain an infinite family of rational triples (a,b,c)-and coming back to the original variables (x=a/(a-1) etc.)-an infinite family of rational triples (x,y,z) with the needed property. (A short calculation shows that the resulting triples arex=-k/(k-1)2,y=k-k2,z= (k-1)/k2; but the proof was complete without listing them.) Comment 1.There are many possible variations in handling the equationsystema2+b2+c2= 1, a+b+c= 1 (a,b,c?= 1) which of course describes a circle in the (a,b,c)-space (with three points excluded), and finding infinitely many rational points on it. Also the initial substitutionx=a/(a-1) (etc.) can be successfully replaced by other similar substitutions, e.g.x= 1-1/α(etc.); orx=x?-1 (etc.); or 1-yz=u(etc.)-eventually reducing

the inequality to (···)2≥0, the expression in the parentheses depending on the actualsubstitution.

Depending on the method chosen, one arrives at various sequences of rational triples (x,y,z) as needed; let us produce just one more such example:x= (2r-2)/(r+ 1)2,y= (2r+ 2)/(r-1)2, z= (r2-1)/4 wherercan be any rational number different from 1 or-1. Solution 2(an outline).(a) Without changing variables, just settingz= 1/xyand clearing fractions, the proposed inequality takes the form (xy-1)2?x2(y-1)2+y2(x-1)2?+ (x-1)2(y-1)2≥(x-1)2(y-1)2(xy-1)2. With the notationp=x+y,q=xythis becomes, after lengthy routine manipulation and a lot of cancellation q

4-6q3+ 2pq2+ 9q2-6pq+p2≥0.

It is not hard to notice that the expression on the left is just(q2-3q+p)2, hence nonnegative. (Without introducingpandq, one is of course led with some more work to the same expression, just written in terms ofxandy; but then it is not that easy to see that it is a square.) (b) To have equality, one needsq2-3q+p= 0. Note thatxandyare the roots of the quadratic trinomial (in a formal variablet):t2-pt+q. Whenq2-3q+p= 0, the discriminant equals

δ=p2-4q= (3q-q2)2-4q=q(q-1)2(q-4).

Now it suffices to have bothqandq-4 squares of rational numbers (thenp= 3q-q2and⎷ are also rational, and so are the roots of the trinomial). On settingq= (n/m)2= 4 + (l/m)2the requirement becomes 4m2+l2=n2(withl,m,nbeing integers). This is just the Pythagorean equation, known to have infinitely many integer solutions. Comment 2.Part (a) alone might also be considered as a possible contestproblem (in the category of easy problems). 11 A3.LetS?Rbe a set of real numbers. We say that a pair (f,g) of functions fromSintoS is aSpanish CoupleonS, if they satisfy the following conditions: (i) Both functions are strictly increasing, i.e.f(x)< f(y) andg(x)< g(y) for allx,y?S withx < y; (ii) The inequalityf(g(g(x)))< g(f(x)) holds for allx?S.

Decide whether there exists a Spanish Couple

(a) on the setS=Nof positive integers; (b) on the setS={a-1/b:a,b?N}. Solution.We show that the answer is NO for part (a), and YES for part (b). (a) Throughout the solution, we will use the notationgk(x) =k g(g(...g(x)...)), including g

0(x) =xas well.

Suppose that there exists a Spanish Couple (f,g) on the setN. From property (i) we have f(x)≥xandg(x)≥xfor allx?N. fromktok+ 1, apply the induction hypothesis ong2(x) instead ofx, then apply (ii): Sincegis increasing, it follows thatgk+1(x)< f(x). The claim is proven. Ifg(x) =xfor allx?Nthenf(g(g(x))) =f(x) =g(f(x)), and we have a contradiction with (ii). Therefore one can choose anx0?Sfor whichx0< g(x0). Now consider the sequence x

0,x1,...wherexk=gk(x0). The sequence is increasing. Indeed, we havex0< g(x0) =x1,

andxk< xk+1impliesxk+1=g(xk)< g(xk+1) =xk+2. Hence, we obtain a strictly increasing sequencex0< x1< ...of positive integers which on the other hand has an upper bound, namelyf(x0). This cannot happen in the setNof positive integers, thus no Spanish Couple exists onN. (b) We present a Spanish Couple on the setS={a-1/b:a,b?N}. Let f(a-1/b) =a+ 1-1/b, g(a-1/b) =a-1/(b+ 3a). These functions are clearly increasing. Condition (ii) holds, since f(g(g(a-1/b))) = (a+ 1)-1/(b+ 2·3a)<(a+ 1)-1/(b+ 3a+1) =g(f(a-1/b)). Comment.Another example of a Spanish couple isf(a-1/b) = 3a-1/b,g(a-1/b) =a-1/(a+b). More generally, postulatingf(a-1/b) =h(a)-1/b,g(a-1/b) =a-1/G(a,b) withhincreasing

andGincreasing in both variables, we get thatf◦g◦g < g◦fholds ifG?a,G(a,b)?< G?h(a),b?.

A search just among linear functionsh(a) =Ca,G(a,b) =Aa+Bbresults in finding that any in- tegersA >0,C >2 andB= 1 produce a Spanish couple (in the example above,A= 1,C= 3). The proposer"s example results from takingh(a) =a+ 1,G(a,b) = 3a+b. 12 A4.For an integerm, denote byt(m) the unique number in{1,2,3}such thatm+t(m) is a multiple of 3. A functionf:Z→Zsatisfiesf(-1) = 0,f(0) = 1,f(1) =-1 and f(2n+m) =f(2n-t(m))-f(m) for all integersm,n≥0 with 2n> m. Prove thatf(3p)≥0 holds for all integersp≥0. Solution.The given conditions determinefuniquely on the positive integers. The signs of f(1),f(2),...seem to change quite erratically. However values of the formf(2n-t(m)) are sufficient to compute directly any functional value. Indeed,letn >0 have base 2 representation

n= 2a0+2a1+···+2ak,a0> a1>···> ak≥0, and letnj= 2aj+2aj-1+···+2ak,j= 0,...,k.

Repeated applications of the recurrence show thatf(n) is an alternating sum of the quantities f(2aj-t(nj+1)) plus (-1)k+1. (The exact formula is not needed for our proof.) So we focus attention on the valuesf(2n-1),f(2n-2) andf(2n-3). Six cases arise; more specifically, t(22k-3) = 2, t(22k-2) = 1, t(22k-1) = 3, t(22k+1-3) = 1, t(22k+1-2) = 3, t(22k+1-1) = 2. Claim.For all integersk≥0 the following equalities hold: f(22k+1-3) = 0, f(22k+1-2) = 3k, f(22k+1-1) =-3k, f(22k+2-3) =-3k, f(22k+2-2) =-3k, f(22k+2-1) = 2·3k. Proof.By induction onk. The basek= 0 comes down to checking thatf(2) =-1 and f(3) = 2; the given valuesf(-1) = 0,f(0) = 1,f(1) =-1 are also needed. Suppose the claim holds fork-1. Forf(22k+1-t(m)), the recurrence formula and the induction hypothesis yield f(22k+1-3) =f(22k+ (22k-3)) =f(22k-2)-f(22k-3) =-3k-1+ 3k-1= 0, f(22k+1-2) =f(22k+ (22k-2)) =f(22k-1)-f(22k-2) = 2·3k-1+ 3k-1= 3k, f(22k+1-1) =f(22k+ (22k-1)) =f(22k-3)-f(22k-1) =-3k-1-2·3k-1=-3k. Forf(22k+2-t(m)) we use the three equalities just established: f(22k+2-3) =f(22k+1+ (22k+1-3)) =f(22k+1-1)-f(22k+1-3) =-3k-0 =-3k, f(22k+2-2) =f(22k+1+ (22k+1-2)) =f(22k+1-3)-f(22k-2) = 0-3k=-3k, f(22k+2-1) =f(22k+1+ (22k+1-1)) =f(22k+1-2)-f(22k+1-1) = 3k+ 3k= 2·3k.

The claim follows.

A closer look at the six cases shows thatf(2n-t(m))≥3(n-1)/2if 2n-t(m) is divisible if and only if 2 n+mis. Therefore, for all nonnegative integersmandn, (i)f(2n-t(m))≥3(n-1)/2if 2n+mis divisible by 3;

3·3n/2for allm,n≥0.

The last inequality enables us to find an upper bound for|f(m)|formless than a given with 2 n> m. 13 The basen= 0 is clear asf(0) = 1. For the inductive step fromnton+ 1, letmandn satisfy 2 n+1> m. Ifm <2n, we are done by the inductive hypothesis. Ifm≥2nthen

3·3n/2and the inductive assumption,

3·3n/2+ 3n/2<3(n+1)/2.

The induction is complete.

We proceed to prove thatf(3p)≥0 for all integersp≥0. Since 3pis not a power of 2, its binary expansion contains at least two summands. Hence one can write 3p= 2a+2b+cwhere a > band 2b> c≥0. Applying the recurrence formula twice yields f(3p) =f(2a+ 2b+c) =f(2a-t(2b+c))-f(2b-t(c)) +f(c).

Since 2

a+ 2b+cis divisible by 3, we havef(2a-t(2b+c))≥3(a-1)/2by (i). Since 2b+cis f(c)≥ -3b/2. Thereforef(3p)≥3(a-1)/2-3b/2which is nonnegative becausea > b. 14

A5.Leta,b,c,dbe positive real numbers such that

abcd= 1 anda+b+c+d >a b+bc+cd+da.

Prove that

a+b+c+d By applying the AM-GM inequality to the numbers a b,ab,bcandad, we obtain a=4? a4 abcd=4? a ab+ab+bc+ad?

Analogously,

4? bc+bc+cd+ba? cd+cd+da+cb? da+da+ab+dc?

Summing up these estimates yields

4? ab+bc+cd+da? +14? ba+cb+dc+ad?

In particular, ifa+b+c+d >a

b+bc+cd+dathena+b+c+d 0 and abcd= 1 then?a b+bc+cd+da?

3?ba+cb+dc+ad?

≥(a+b+c+d)4. It suffices to apply H¨older"s inequality to the sequences in the four rows, with weights 1/4: ?a b+bc+cd+da?

1/4?ab+bc+cd+da?

1/4?bc+cd+da+ab?

1/4?ad+ba+cb+dc?

1/4 ?aaba bbcd? 1/4 +?bbcbccda? 1/4 +?ccdcddab? 1/4 +?ddadaabc? 1/4 =a+b+c+d. 15

A6.Letf:R→Nbe a function which satisfies

f x+1 f(y)? =f? y+1f(x)? for allx,y?R. (1) Prove that there is a positive integer which is not a value off. Solution.Suppose that the statement is false andf(R) =N. We prove several properties of the functionfin order to reach a contradiction. To start with, observe that one can assumef(0) = 1. Indeed, leta?Rbe such that f(a) = 1, and consider the functiong(x) =f(x+a). By substitutingx+aandy+aforx andyin (1), we have g x+1 g(y)? =f? x+a+1f(y+a)? =f? y+a+1f(x+a)? =g? y+1g(x)? Sogsatisfies the functional equation (1), with the additional propertyg(0) = 1. Also,gandf have the same set of values:g(R) =f(R) =N. Henceforth we assumef(0) = 1.

Claim 1.For an arbitrary fixedc?Rwe have?

f? c+1 n? :n?N? =N.

Proof.Equation (1) andf(R) =Nimply

f(R) =? f? x+1 f(c)? :x?R? f? c+1f(x)? :x?R? f? c+1n? :n?N? ?f(R).

The claim follows.

We will use Claim 1 in the special casesc= 0 andc= 1/3: f?1 n? :n?N? f?13+1n? :n?N? =N.(2) Claim 2.Iff(u) =f(v) for someu,v?Rthenf(u+q) =f(v+q) for all nonnegative rationalq. Furthermore, iff(q) = 1 for some nonnegative rationalqthenf(kq) = 1 for allk?N.

Proof.For allx?Rwe have by (1)

f u+1 f(x)? =f? x+1f(u)? =f? x+1f(v)? =f? v+1f(x)? Sincef(x) attains all positive integer values, this yieldsf(u+1/n) =f(v+1/n) for alln?N. Letq=k/nbe a positive rational number. Thenkrepetitions of the last step yield f(u+q) =f? u+k n? =f? v+kn? =f(v+q). Now letf(q) = 1 for some nonnegative rationalq, and letk?N. Asf(0) = 1, the previous conclusion yields successivelyf(q) =f(2q),f(2q) =f(3q),...,f((k-1)q) =f(kq), as needed. Claim 3.The equalityf(q) =f(q+ 1) holds for all nonnegative rationalq. Proof.Letmbe a positive integer such thatf(1/m) = 1. Such anmexists by (2). Applying the second statement of Claim 2 withq= 1/mandk=myieldsf(1) = 1. Given thatf(0) =f(1) = 1, the first statement of Claim 2 impliesf(q) =f(q+ 1) for all nonnegative rationalq. 16

Claim 4.The equalityf?1n?

=nholds for everyn?N. Proof.For a nonnegative rationalqwe setx=q,y= 0 in (1) and use Claim 3 to obtain f ?1 f(q)? =f? q+1f(0)? =f(q+ 1) =f(q). By (2), for eachn?Nthere exists ak?Nsuch thatf(1/k) =n. Applying the last equation withq= 1/k, we have n=f?1 k? =f?1f(1/k)? =f?1n? Now we are ready to obtain a contradiction. Letn?Nbe such thatf(1/3 + 1/n) = 1. Such annexists by (2). Let 1/3 + 1/n=s/t, wheres,t?Nare coprime. Observe thatt >1 as 1/3 + 1/nis not an integer. Choosek,l?Nso that thatks-lt= 1. Becausef(0) =f(s/t) = 1, Claim 2 impliesf(ks/t) = 1. Nowf(ks/t) =f(1/t+l); on the other handf(1/t+l) =f(1/t) bylsuccessive applications of Claim 3. Finally,f(1/t) =tby Claim 4, leading to the impossiblet= 1. The solution is complete. 17 A7.Prove that for any four positive real numbersa,b,c,dthe inequalityquotesdbs_dbs47.pdfusesText_47