IMO 2008 Shortlisted Problems PDF

In Exercises 1-15 use mathematical induction to establish the formula for n ? 1. 1. 1. 2. + 2. 2. + 3. 2. + ··· + n. 2. = n(n + 1)(2n + 1).

MATHEMATICAL INDUCTION SEQUENCES and SERIES

?n is always divisible by 30. Use the fact that n. 5. ?n = (n?1)n(n+1)(n. 2. +1) to prove that it is divisible by 2 and 3 as well as 5.

Problem: For each positive integer n the formula 1 · 3+2 · 4+3 · 5 +

1 · 3+2 · 4+3 · 5 + ··· + n(n + 2) = n(n + 1)(2n + 7). 6 is valid. Proof: (formal style; it is good to do a few proofs this way) We will use the Principle

Proof by Induction - University of Plymouth

12-Feb-2006 Example 3: for n a natural number prove that: 1) if n ? 2 then n3 ? n is always divisible by 3

Problem Solving for Math Competitions Harm Derksen

* Prove that. 12 + 22 + ··· + n2 = n(n + 1)(2n + 1). 6 for all positive integers n. Exercise 1.2. * Show that. 1 ?. 1. 2. +. 1. 3. ?

BINOMIAL THEOREM

8.1.3 Some important observations. 1. The total number of terms in the binomial expansion of (a + b)n is n + 1 i.e. one more than the exponent n. 2.

CS240 Solutions to Induction Problems Fall 2009 1. Let P(n) be the

If we had shown P(3) as our basis step then the inequality would only be proven for n ? 3. 2. For any positive integer n n. ? i=1. 1 i(i + 1). = 1. 1 · 2.

IMO 2008 Shortlisted Problems

(a ? 1)(b ? 1)(c ? 1) = abc. ?=(a ? 1)2 ? 4a(a ? 1) = (1 ? a)(1 + 3a). ... (i) f(2n ? t(m)) ? 3(n?1)/2 if 2n + m is divisible by 3;.

Untitled

principle of induction P(n) is true for all positive integers n > 1. herefore each term in the product (1+2+22)(1 +3 +3² +3³)(1 +.

Polynomials II - Divisibility and Irreducibles

So now for instance x2 ?2 is not divisible by x? ? 2 over Q since x? ? 2 doesn’t exist over Q Problem 9 Show that x2?2 is irreducible over Q (Hint: Suppose it were reducible What would the degrees of the factors have to be and what does that mean?) Problem 10 Show that x3 ?2 is irreducible over Q (Hint: This is similar

Math 115 Exam Solutions - Colorado State University

1+n2 = 0 and (ii) the sequence of terms 1+n2 are decreasing To see (i) notice that we can divide numerator and denominator by n2 to get lim n?? 1 n2 ·n 1 n2 (1+n 2) = lim n?? 1 n 1 n2 +1 = 0 To see (ii) let f(x) = x 1+x2 Then f0(x) = (1+x2)·1?x·2x (1+x2)2 = 1?x2 (1+x2)2 ? 0 for x ? 1 Therefore f is a decreasing

3 Mathematical Induction 31 First Principle of

3 MATHEMATICAL INDUCTION 89 Which shows 5(n+ 1) + 5 (n+ 1)2 By the principle of mathematical induction it follows that 5n+ 5 n2 for all integers n 6 Discussion In Example 3 4 1 the predicate P(n) is 5n+5 n2 and the universe of discourse

How to prove n is true for all integers n 1?

Mathematical induction can be used to prove that a statement about n is true for all integers n ? 1. We have to complete three steps. In the basis step, verify the statement for n = 1. In the inductive hypothesis, assume that the statement holds when n = k for some integer k ? 1.

Does f(n) = n 1+n2 converge?

Therefore, f is a decreasing function in the relevant range, so the terms f(n) =n 1+n2are decreasing. 1 We know that the series converges, but we need to determine whether it converges absolutely or not. In other words, we must determine if X? n=1 (?1) nn 1+n2 = X? n=1 n 1+n2 . converges or not.

Is p divisible by Q over C?

Definition 1Let p and q be polynomials in the complex numbers C. We say that p is divisble by q over C if there exists a polynomial r such that p(z) = q(z)r(z). Problem 1 By long division (which we learned how to do last week), answer the following: • Is x3?2x2+ x?2 divisible by x?2 over C?

49thInternational Mathematical Olympiad

Spain 2008

Shortlisted Problems with Solutions

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),

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

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.quotesdbs_dbs35.pdfusesText_40

[PDF] la gestion d'entreprise pdf

[PDF] montrer que n(n+1)(2n+1) est divisible par 3

[PDF] n^3-n est divisible par 6

[PDF] montrer que n(n+1)(n+2) est multiple de 3

[PDF] montrer que n^3-n est divisible par 3

[PDF] montrer que n(n 1)(n 2)(n 3) est divisible par 24

[PDF] الموقع الرسمي للتكوين المهن

[PDF] التكوين المهني بالمغرب

[PDF] ofppt sidi maarouf

[PDF] التسجيل في التكوين المهني

[PDF] ista meknes

[PDF] takwine

[PDF] rapport pisa 2016 france

[PDF] pisa classement

[PDF] pisa 2015 france

[PDF] IMO 2008 Shortlisted Problems