BLOG DO ENG. ARMANDO CAVERO MIRANDA -BRASIL


MACHUPICHU MARAVILHA DO MUNDO

"Two things are infinite: the universe and human stupidity; and I'm not sure about the the universe." ALBERT EINSTEIN - “SE SEUS PROJETOS FOREM PARA UM ANO,SEMEIE O GRÂO.SE FOREM PARA DEZ ANOS,PLANTE UMA ÁRVORE.SE FOREM PARA CEM ANOS,EDUQUE O POVO.” "MATH IS POWER TO CHANGE THE WORLD AND THE KEY TO THE FUTURE" 'OBRIGADO DEUS PELA VIDA,PELA MINHA FAMILIA,PELO TRABALHO,PELO PÃO DE CADA DIA,PROTEGENOS E GUARDANOS DE TODO MAL"

terça-feira, 1 de outubro de 2013

19th Chinese Mathematical Olympiad 2004 Problems & Solutions

A1.  ABCD is a quadrilateral. E, F, G, H are points on AB, BC, CD, DA respectively such that (AE/EB)(BF/FC)(CG/GD)(DH/HA) = 1. The lines through A parallel to HE, through B parallel to EF, through C parallel to FG, and through D parallel to GH form a quadrilateral E1F1G1H1 (E1 is the intersection of the lines through A and B, F1 is the intersection of the lines through B and C, and so on). Find CF1/CG1 in terms of AH1/AE1.
A2.  a1/, a2, a3, ... is a sequence of integers with a1 positive and an = [(1 + 2/n)(an-1 - 1)] + 1. Find an in terms of a1 and n.
A3.  S is a set of n points. It contains a convex 7-gon and given any convex pentagon in S, there is a point of S inside it. Find the minimum possible value of n. (Note that 5 points are not considered to form a convex pentagon if any of them lies in the convex hull of the other 4, so in particular they cannot form a convex pentagon if three of them are collinear.)
B1.  a is a real. The sequence of reals x0, x1, ... , xn+1 satisfies x0 = xn+1 = 0 and (xi-1 + xi+1)/2 = xi + xi3 - a3 for i = 1, 2, ... , n. Show that the sequence is uniquely determined by n and a and that |xi| ≤ |a|.
B2.  a1 < a2 < ... < an is a sequence of positive integers with ∑ 1/ai ≤ 1. Prove that (∑ 1/(ai2 + x2) )2 ≤ 1/(2a12-2a1+2x2) for any real x.
B3.  Show that any sufficiently large integer can be expressed as a sum of distinct positive integers a1, a2, ... , a2004 such that each ai is divisible by its predecessor. 

Solutions

Problem A1
ABCD is a quadrilateral. E, F, G, H are points on AB, BC, CD, DA respectively such that (AE/EB)(BF/FC)(CG/GD)(DH/HA) = 1. The lines through A parallel to HE, through B parallel to EF, through C parallel to FG, and through D parallel to GH form a quadrilateral E1F1G1H1 (E1 is the intersection of the lines through A and B, F1 is the intersection of the lines through B and C, and so on). Find CF1/CG1 in terms of AH1/AE1.
Answer
CF1/CG1 = 1/(AH1/AE1)
Solution
Let the diagonals AC, BD meet at O. Suppose the lines EF and AC meet at P (we consider later what happens if they are parallel). Then the heights of A and C above EF are proportional to PA and PC, so area AEF/area CEF = PA/PC. But area AEF/area BEF = AE/BE, and area CEF/area BEF = CF/BF, so PA/PC = (AE/EB)(BF/CF). Similarly, if GH meets AC at Q, then QA/QC = area AGH/area BGH = (AH/DH)(GD/CG). But (AE/EB)(BF/CF) = (AH/DH)(GD/GC), so PA/PC = QA/QC and hence P and Q coincide.
Let E1F1 and G1H1 meet at R. Then area PAD/area PDH = AD/DH = area ARH1/area HRH1. Similarly, area PBA/area PBE = BA/BE = area ARE1/area ERE1. Hence (area PAD/area PDH)(area PBE/area PBA) = (area ARH1/area HRH1)(area ERE1/area ARE1). But area PAD/area PBA = DO/BO and area ARH1/area ARE1 = AH1/AE1, so (DO/BO)(area PBE/area PDH) = (AH1/AE1)(area ERE1/area HRH1). Now the bases PE and RE1 of PBE and ERE1 are parallel and the heights are the same, so area PBE/area ERE1 = PE/RE1. Similarly, the bases PH and RH1 of PDH and HRH1 are parallel and the heights are the same, so area PDH/area HRH1 = PH/RH1. Also triangles PHE and RH1E1 are similar (corresponding sides are parallel, so the angles are equal). Hence PE/RE1 = PH/RH1. Hence AH1/AE1 = DO/BO.
A similar argument gives CG1/CF1 = DO/BO. Hence AH1/AE1 = CG1/CF1.
It remains to consider the case where EF is parallel to AC. In that case AE/EB = CF/FB. Hence AH/DH = CG/GD, so GH is also parallel to AC. Hence E1F1 and H1G1 are parallel to AC. So AH1/E1H1 = area AH1G1/area E1H1G1 = area CH1G1/area F1H1G1 = CG1/F1G1. Hence AH1/AE1 = CG1/CF1.
Thanks to Polly T Wang

Problem A2
a1/, a2, a3, ... is a sequence of integers with a1 positive and an = [(1 + 2/n)(an-1 - 1)] + 1. Find an in terms of a1 and n.
Answer
If a1 = 3k, then an = 1 + [(n+2)2/4] + (k-1)(n+1)(n+2)/2
if a1 = 3k+1, then an = 1 + k(n+1)(n+2)/2
if a1 = 3k+2, then an = (n+1)(1 + k(n+2)/2)
Solution
It is convenient to put bn = an - 1, so bn = [bn-1(n+2)/n]. It is a trivial induction that bn = k(n+1)(n+2)/2 is a solution for k a positive integer. Note that in this case we do not need the [ ], so we can add this solution to others. It gives b1 = 3k and hence a1 = 3k+1.
We claim that bn = n is also a solution. For [(n-1)(n+2)/n] = [(n2+n-2)/n] = [n+1-2/n] = n (for n ≥ 2). We can add this to the previous solution to get bn = n + k(n+1)(n+2)/2 which gives b1 = 3k+1 and hence a1 = 3k+2.
Finally, we claim that bn = [(n+2)2/4] is also a solution. That implies b2m = (m+1)2 and b2m-1 = m(m+1). Then b2m+1 = [(m+1)2(2m+3)/(2m+1)] = [(m+1)2 + 2(m+1)2/(2m+1)] = [(m+1)2 + (m+1)(2m+1)/(2m+1) + (m+1)/(2m+1)] = [(m+1)(m+2) + (m+1)/(2m+1)] = (m+1)(m+2). Also b2m+2 = [(m+1)(m+2)(2m+4)/(2m+2)] = [(m+2)(m+2)] = (m+2)2, which proves the claim. It gives b1 = 2. Adding to the first solution we get the solution bn = [(n+2)2/4] + (k-1)(n+1)(n+2)/2 which gives b1 = 3k-1 and hence a1 = 3k.
The sequence is obviously determined by a1 and the recurrence rule, so we have found solutions for all positive integers a1


Problem A3
S is a set of n points. It contains a convex 7-gon and given any convex pentagon in S, there is a point of S inside it. Find the minimum possible value of n. (Note that 5 points are not considered to form a convex pentagon if any of them lies in the convex hull of the other 4, so in particular they cannot form a convex pentagon if three of them are collinear.)
Answer
11
Solution
Thanks to Polly T Wang
We show that there must be at least 4 points inside the convex 7-gon.
There must be at least one, because there must be a point inside the convex hull formed by 5 of the points. If there is just one, X, then take a line through the point which does not contain any other points in the set. At least 4 points must lie on one side of the line. With X they form a convex pentagon, which must have a point inside. Contradiction.
If there are just two, X and Y. Take the line through X and Y. It can pass through at most 2 of the 7 points, so at least 3 of the 7 points must lie on one side of the line. With X and Y they form a convex pentagon, which must have a point inside. Contradiction.
Finally, suppose there are just three, X, Y and Z. Let HZ be the open half-plane on the opposite side of XY to Z. Similarly, let HY be the open half-plane on the opposite side of ZX to Y, and HX the open half-plane on the opposite side of YZ to X. Then HX ∪ HY ∪ HZ is the whole plane outside XYZ. So all 7 vertices of the convex 7-gon belong to HX ∪ HY ∪ HZ. Hence one of HX, HY, HZ contains at least 3 vertices of the 7-gon. With the two points on the line they form convex 5-gon. Contradiction.
So we have shown that 11 points are necessary. The diagram shows that they are sufficient.

Problem B1
a is a real. The sequence of reals x0, x1, ... , xn+1 satisfies x0 = xn+1 = 0 and (xi-1 + xi+1)/2 = xi + xi3 - a3 for i = 1, 2, ... , n. Show that the sequence is uniquely determined by n and a and that |xi| ≤ |a|.
Solution
Suppose first a = 0. Suppose some xi > 0. Then take xj to be the largest xi. We have xj > 0 and hence j ≠ 0 or n+1. So (xj-1 + xj+1)/2 = xj + xj3 > xj. So xj-1 or xj+1 > xj. Contradiction. So all xi ≤ 0. Similarly, if some xi < 0, the take xj to be the smallest. But then (xj-1 + xj+1)/2 = xj + xj3 < xj. Contradiction. So all xi ≥ 0. Hence all xi = 0. It is easy to check that for a = 0, x0 = x1 = ... = xn+1 = 0 satisfies the conditions and so is the unique solution for any n.
Now suppose a > 0. Suppose some xi < 0. Then take xj to be the smallest xi. But then (xj-1 + xj+1)/2 = xj + xj3 - a3 < xj. Contradiction. So all xj ≥ 0. Suppose some xi = 0 for i ≠ 0 or n+1. Then (xi-1 + xi+1)/2 = xi + xi3 - a3 = -a3 < 0, so xi-1 or xi+1 < 0. Contradiction. Thus all the terms except the first and last are positive. Let xj be the largest term. Then we must have xj ≤ a, because otherwise (xj-1 + xj+1)/2 = xj + xj3 - a3 > xj. Contradiction. In fact we must have xj < a, because if xj = a, then (xj-1 + xj+1)/2 = xj + xj3 - a3 = xj and hence xj-1 = xj+1 = a. Repeating, we get eventually x0 or xn+1 = a. Contradiction.
Now suppose x1 = x. We ignore for the moment the requirement that xn+1 = 0. We show by induction on k that xk and xk-xk-1 are continuous, strictly increasing functions of x. That is obvious for k=1. Put k=2. We have x2 = 2x + 2x3 - 2a3, and x2-x1 = x + 2x3 - 2a3, which are both continuous, strictly increasing functions of x. Suppose it is true for k. Then xk+1 = 2xk + 2xk3 - 2a3 - xk-1 = xk + 2xk3 - 2a3 + (xk - xk-1) and xk+1 - xk = 2xk3 - 2a3 + (xk - xk-1). Since both xk and (xk - xk-1) are both continuous, strictly increasing functions of x, so are xk+1 and (xk+1 - xk).
In particular, if follows that xn+1 is a continuous, strictly increasing function of x. Put xn+1 = f(x). Now if we take x = a, then x2 = 2a > a, and by a trivial induction xk > a for all k > 1. So, in particular, f(a) > a. On the other hand, if we take x = 0, then x2 = -2a3 < 0, and by a trivial induction xk < 0 for all k > 1. So, in particular f(0) < 0. Thus there must be a unique x in the interval (0,a) such that f(x) = 0. Since x uniquely determines the entire sequence, we have established that the entire sequence is uniquely determined by n and a.
Now suppose a < 0. If xi is the sequence uniquely determined by n and -a, then it is clear that the sequence -xi is a solution for n and a. Conversely, if yi is a solution for n and a, then -yi is a solution for n and -a and hence must be the unique sequence xi. So the result is also true for a negative. 

Problem B2
a1 < a2 < ... < an is a sequence of positive integers with ∑ 1/ai ≤ 1. Prove that (∑ 1/(ai2 + x2) )2 ≤ 1/(2a12-2a1+2x2) for any real x.
Solution
Appying Cauchy-Schwartz, we have lhs = (∑ (√ai/(ai2+x2))(1/√ai) )2 ≤ (∑ ai/(ai2+x2)2 )(∑ 1/ai) ≤ ∑ ai/(ai2+x2)2.
Now (ai2+x2)2 > (ai2+x2)2 - ai2 > 0, so ∑ ai/(ai2+x2)2 < (1/2) ∑ (1/(ai2+x2-ai) - 1/(ai2+x2+ai) ).
Now ai+1 ≥ ai+1, so ai+12-ai+1+x2 ≥ ai2+ai+x2 and hence ∑ (1/(ai2+x2-ai) ≤ 1/(a12+x2-a1) + (∑ 1/(ai2+x2+ai) ) - 1/(an2+x2+an) ≤ 1/(a12+x2-a1) + (∑ 1/(ai2+x2+ai) ). Hence lhs < (1/2) 1/(a12+x2-a1), as required. 

Thanks to Li Yi

WEBSITE ORIGINAL SOURCE
http://www.kidsmathbooks.com/2011/01/19th-chinese-mathematical-olympiad-2004.html 

Nenhum comentário:

Postar um comentário