quinta-feira, 3 de outubro de 2013

Ashani Dasgupta's Math Blog

EXCELLENT BLOG MATHEMATICS
http://cheentasutra.wordpress.com/

Crease of a square paper

A square sheet of paper ABCD is so folded that B falls on the mid-point of M of CD. Prove that the crease will divide BC in the ratio 5:3.
Discussion:

Assuming the side of the square is ‘s’. Let a part of the crease be ‘x’ (hence the remaining part is ‘s-x’). We apply Pythagoras Theorem we solve for x:
$x^2 + \frac {s^2 }{4} = (s-x)^2$ implies $x = \frac {3s}{8}$ and $s-x = \frac {5s}{8}$
Hence the ratio is 5:3.

Indian Math Olympiad

RMO 1990

Two boxes contain between them 65 balls of several different sizes. Each ball is white, black, red or yellow. If you take any five balls of the same colour, at least two of them will always be of the same size (radius). Prove that there are at least three balls which lie in the same box have the same colour and have the same size (radius).
For all positive real numbers a, b, c prove that $\frac{a}{b+c} + \frac{b}{a+c}+ \frac{c}{a+b} \ge \frac{3}{2}$
A square sheet of paper ABCD is so folded that B falls on the mid-point of M of CD. Prove that the crease will divide BC in the ratio 5:3.

Discussion
Find the remainder when $2^{1990}$ is divided by 1990.
P is any point inside a triangle ABC. The perimeter of the triangle AB +BC +CA=2s. Prove that s < AP + BP + CP < 2s.
N is a 50 digit number (in a decimal scale). All digits except the $26^{th}$ digit (from the left) are 1.If N is divisible by 13, find the $26^{th}$ digit.
A census-man on duty visited a house in which the lady inmates declined to reveal their individual ages, but said “We do not mind giving you the sum of the ages of any two ladies you may choose”. There upon the census man said, “In that case, please give me the sum of the ages of every possible pair of you”. They gave the sums as follows: 30, 33, 41, 58, 66, 69. The census-man took these figures and happily went away. How did he calculate the individual ages of the ladies from these figures?
If the circumcenter and centroid of a triangle coincide, prove that the triangle must be equilateral.

Indian Math Olympiad

INMO 2012

Let ABCD be a quadrilateral inscribed in a circle. Suppose AB = $\sqrt {2 + \sqrt {2} }$ and AB subtends 1350 at the center of the circle. Find the maximum possible area of ABCD.
Let $p_1<p_2< p_3< p_4$ and $q_1<q_2<q_3<q_4$ be two sets of prime numbers such that $p_4 - p_1 = 8$ and $q_4 - q_1 = 8$ . Suppose $p_1>5$ and $q_1>5$ . Prove that 30 divides $p_1 - q_1$ .
Define a sequence $<fn(x)>$ n∈N of functions as $f_0(x )=1, f_1(x )=x$ , $(f_n(x))^2 - 1 = f_{n-1} (x) f_{n+1} (x)$ , for $n \ge 1$ . Prove that each $f_n(x )$ is a polynomial with integer coefficients.
Let ABC be a triangle. An interior point P of ABC is said to be good if we can find exactly 27 rays emanating from P intersecting the sides of the triangle ABC such that the triangle is divided by these rays into 27 smaller triangles of equal area. Determine the number of good points for a given triangle ABC.
Let ABC be an acute angled triangle. Let D, E, F be points on BC, CA, AB such that AD is the median, BE is the internal bisector and CF is the altitude. Suppose that angle FDE = angle C and angle DEF = angle A and angle EFD = angle B. Show that ABC is equilateral.
Let be a function satisfying , and
1. $f(xy) + f(x)f(y) = f(x) + f(y)$ ,
2. for all x , simultaneously.
  1. Find the set of all possible values of the function f.
  2. If $f(10) \neq 0$ and $f(2) = 0$ , find the set of all integers n such that $f(n) \neq 0$ .

quarta-feira, 2 de outubro de 2013

IMTOT1997-2002

LINK
http://keoserey.files.wordpress.com/2012/12/tot97-02.pdf

Australian Mathematical Olympiads 1996-2011 Book 2

Not Full version, just enjoy it now

Download Australian Mathematical Olympiads 1996-2011 Book 2

WEBSITE ORIGINAL
http://keoserey.wordpress.com/

terça-feira, 1 de outubro de 2013

Complex Numbers from A to. . . Z Titu Andreescu Dorin Andrica

About the Authors
Titu Andreescu received his BA, MS, and PhD from the West University
of Timisoara, Romania. The topic of his doctoral dissertation was “Research
on Diophantine Analysis and Applications.” Professor Andreescu currently
teaches at the University of Texas at Dallas.
LINK
http://limtaosin.files.wordpress.com/2012/09/26-complexnumbersfromatoz.pdf

USSR Mathematical Olympiads 1989-1992

SURFANDO EN LA INTERNET ENCONTRE ESTE IMPORTANTE LIBRO PARA ENTRENAMIENTO DE OLIMPIADAS DE MATEMATICAS DE LA CELEBRE ESCUELA RUSA DE MATEMATICAS SON LAS OLIMPIADAS DESDE 1989-1992.
LO PUEDES BAJAR TRANQULAMENTE EN LOS SITIOS WEB QUE ENCONTRE:
http://limtaosin.files.wordpress.com/2012/08/arkadii-m-slinko-ussr-mathematical-olympiads-1989-19921.pdf

http://www.mediafire.com/?91zgkz21zgjuh6w

18th Chinese Mathematical Olympiad 2003 Problems & Solutions

A1. ABC is an acute-angled triangle with AB and AC unequal, incenter I and orthocenter H. BB₁ and CC₁ are medians. The line IB₁ meets the line AB at B₂, and the line IC₁ meets the line CA at C₂. The line B₂C₂ meets the line BC at K. The circumcenter of BHC is O'. Show that A, I and O' are collinear iff area BKB₂ = area CKC₂.

A2. S is a subset of {1, 2, 3, ... , 100} such that given any two elements a, b in S, there is an element c in S coprime to a and b, and there is an element d in S which has a common factor with a and a common factor with b. What is the largest possible number of elements in S?

A3. The reals x₁, x₂, ... , x_n all satisfy 0 < x_i < π/2. Also tan x₁ tan x₂ ... tan x_n = 2^n/2. Find the smallest L such that cos x₁ + cos x₂ + ... + cos x_n ≤ L for all such x_i.

B1. Find all positive integer triples (d, m, n) with d > 1, m> 1 such that d^m + 1 divides dⁿ + 203.

B2. There are 10 applicants for a job, labeled 1, 2, ... , 10. Their suitability for the job is ranked in this order (so 1 is more suitable than 2, who is more suitable than 3 and so on). But an applicant's ability is only measured when they are interviewed. They are interviewed in the order a₁, a₂, ... , a₁₀. The first three interviewed are automatically rejected. Thereafter if an applicant's suitability is better than that of all previous applicants they are accepted (without interviewing the other applicants). If the first nine applicants interviewed are not accepted, then the tenth is automatically accepted. Let n_i be the number of permutations a₁, ... , a₁₀ which result in applicant i getting the job. Show that n₁ > n₂ > ... > n₈ = n₉ = n₁₀. Show that the probability that one of 1, 2, 3 gets the job is over 70% and that the probability of one of 8, 9, 10 getting the job is not more than 10%.

B3. a, b, c d are positive reals satisfying ab + cd = 1 and the four points (x₁, y₁), (x₂, y₂), (x₃, y₃), (x₄, y₄) lie on the circle x² + y² = 1. Show that (ay₁ + by₂ + cy₃ + dy₄)² + (ax₄ + bx₃ + cx₂ + dx₁)² ≤ 2(a/b + b/a + c/d + d/c).

Solutions

Problem A1

ABC is an acute-angled triangle with AB and AC unequal, incenter I and orthocenter H. BB₁ and CC₁ are medians. The line IB₁ meets the line AB at B₂, and the line IC₁ meets the line CA at C₂. The line B₂C₂ meets the line BC at K. The circumcenter of BHC is O'. Show that A, I and O' are collinear iff area BKB₂ = area CKC₂.

Solution

Thanks to Allen Zhang

We show that A, I and O' are collinear iff angle BAC = 60^o. Take O as the circumcenter of ABC and let the line AI meet the circumcircle again at P. Since O' and P both lie on the perpendicular bisector of BC, O' lies on the line AI iff O' = P. ∠HBC = 90^o-∠C, ∠HCB = 90^o-∠B, so ∠BHC = ∠B + ∠C. So if P = O', then ∠BPC = 2 x ∠ at circumference = 2(180^o - ∠B - ∠C) = 2∠A. But BACP is cyclic, so ∠A + 2∠A = 180^o. Hence ∠A = 60^o.

Conversely, if ∠A = 60^o, then ∠BO'C = 2(180^o - ∠BHC) = 2∠A = 120^o, so BACO' is cyclic, so O' = P.

Note that area BKB₂ = area CKC₂ iff area ABC = area AB₂C₂. But area ABC = AB·AC sin A, area AB₂C₂ = AB₂·AC₂ sin A, so area BKB₂ = area CKC₂ iff AB·AC = AB₂·AC₂.

We have area AIB₂ = rAB₂/2, area AIB₁ = ½ area AIC = br/4, area AB₁B₂ = AB₂ x height/2 = AB₂ (ht C from AB)/4 = AB₂ r(a+b+c)/4c. Hence 2c AB₂ + bc = AB₂(a+b+c), so AB₂ = bc/(a+b-c). Similarly, AC₂ = bc/(a-b+c).

Thus AB·AC = AB₂·AC₂ is equivalent to bc = (a+b-c)(a-b+c) = a²-b²+2bc-c², or (b²+c²-a²)/2bc = 1/2. But by the cosine rule, lhs = cos A. So AB·AC = AB₂·AC₂ iff A = 60^o.

Problem A2

S is a subset of {1, 2, 3, ... , 100} such that given any two elements a, b in S, there is an element c in S coprime to a and b, and there is an element d in S which has a common factor with a and a common factor with b. What is the largest possible number of elements in S?

Answer 72

Solution

Thanks to Polly T Wang

Let S be the set of all integers n ≤ 100 divisible by just one or two elements of T = {2, 3, 5, 7, 11}. If m, n are two elements in S, then they can be divisible by at most four elements of T, so the fifth member of T is relatively prime to m and n. does not divide either. Also we can pick a prime p in T which divides m and a prime q in T which divides n. If p = q, then p is in S and has a common factor with m and n. If p and q are unequal, then pq is in S and has a common factor with m and n.

The 50 even numbers 2, 4, ... , 100 are in S, except for 30, 60, 90, 42, 84, 66, 70, giving 43 members. The odd multiples of 3 are also in S - 3, 9, 15, ... , 99, giving a further 17 members. The multiples of 5 not divisible by 2 or 3 are in S - 5, 25, 35, 55, 65, 85, 95, giving a further 7 members. Finally, 7, 49, 77, 91, 11 are in S, giving a total of 72 members.

We show that we cannot do better. Clearly 1 ∉ S. There are 21 primes > 10: 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Not more than one of these primes can be in S, for if two were in S, then the smallest number having a common factor with both is > 100. So we have a total so far of 1 + 20 = 21 exclusions.

Suppose no prime > 10 is in S. Then 3 and 70 cannot both be in S, because there cannot be an element coprime to both. Similarly, at least one of (5,42), (7,30), (6,35), (10,21), (14,15), (28,45) is not in S. So we have an additional 1 (the other prime > 10) + 7 (one from each of 7 pairs) = 8 exclusions and hence a total of 29 exclusions, so S cannot have more than 71 members.

So suppose there is a prime p > 10 in S.
(1) If 7p ∈ S, then 30, 60, 90 ∉ S (because there is no available number coprime to both). If 7p ∉ S, then 7, 49, 77, 91 ∉ S (if 7 and p are in S, then 7p must be in S).
(2) if 5p ∈ S, then 42, 84 ∉ S. If 5p ∉ S, then 5, 25 ∉ S.
(3) one of 3p, 70 is not in S.
(4) one of 6p, 35 is not in S.
(5) if 5p and 7p are not in S, then 35 is not in S.

If p = 11 or 13, then (1), (2), (3), (4) exclude 3+2+1+1 = 7 elements. If p = 17 or 19, then 7p ∉ S, so (1) excludes 4 elements and (1), (2), (3) exclude 4+2+1 = 7 elements. If p ≥ 23, then (1), (2), (5) exclude 4+2+1 = 7 elements. So we always get at least 21 + 7 = 28 exclusions, implying that S has at most 72 elements.

Problem A3

The reals x₁, x₂, ... , x_n all satisfy 0 < x_i < π/2. Also tan x₁ tan x₂ ... tan x_n = 2^n/2. Find the smallest L_n such that cos x₁ + cos x₂ + ... + cos x_n ≤ L_n for all such x_i.

Answer

L₁ = 1/√3, L₂ = 2/√3, L_n = n-1 for n > 2.

Solution

Thanks to Li Yi

The case n = 1 is trivial, because x₁ is fixed.

For n = 2 we wish to prove that if tan x₁ tan x₂ = 2, then cos x₁ + cos x₂ ≤ 2/√3. That is equivalent to cos²x₁ + cos²x₂ + 2 cos x₁ cos x₂ ≤ 4/3, or 1/(1 + tan²x₁) + 1/(1 + tan²x₂) + 2/√((1 + tan²x₁)(1 + tan²x₂)) ≤ 4/3. Put k = √((1 + tan²x₁)(1 + tan²x₂)) = √(5 + tan²x₁ + tan²x₂). Then we wish to show that (k² - 3)/k² + 2/k ≤ 4/3 or 2/k - 3/k² ≤ 1/3 or (k-3)² ≥ 0, which is obviously true. Moreover, if we take x₁ = x₂ = tan^-1√2, then tan x₁ tan x₂ = 2, and cos x₁ = cos x₂ = 1/√3, so cos x₁ + cos x₂ = 2/√3. Hence 2/√3 is best possible.

Now take n = 3. We show that if tan x₁ tan x₂ tan x₃ = 2√2, then cos x₁ + cos x₂ + cos x₃ < 2. Take x₁ ≥ x₂ ≥ x₃. If tan²x₂ + tan²x₃ ≥ 7, then tan²x₁ ≥ tan²x₂ ≥ 7/2, so cos x₁ and cos x₂ ≤ (√2)/3 and hence cos x₁ + cos x₂ + cos x₃ ≤ (2√2)/3 + 1 < 2. So assume tan²x₂ + tan²x₃ < 7.

We have cos x₂ ≤ (1 + cos²x₂)/2 = 1 - ½sin²x₂. Similarly for x₃, so cos x₂ + cos x₃ ≤ 2 - (sin²x₂ + sin²x₃)/2 ≤ 2 - sin x₂ sin x₃. Also cos x₁ = 1/√(1+tan²x₁) = 1/√(1+8/(tan²x₂ tan²x₃)) = sin x₂ sin x₃/√(8 cos²x₂ cos²x₃ + sin²x₂ sin²x₃). So cos x₁ + cos x₂ + cos x₃ ≤ 2 - sin x₂ sin x₃ (1 - 1/√(8 cos²x₂ cos²x₃ + sin²x₂ sin²x₃). So we have to show that 8 cos²x₂ cos²x₃ + sin²x₂ sin²x₃ > 1, or 8 + tan²x₂ tan²x₃ > sec²x₂ sec²x₃ (= (1 + tan²x₂)(1 + tan²x₃) ), or tan²x₂ + tan²x₃ < 7.

Finally, if we take x₁ and x₂ close to zero, so that cos x₁ and cos x₂ > 1 - ε/2, then we can take x₃ so that tan x₁ tan x₂ tan x₃ = 2√2. We have cos x₃ > 0, so cos x₁ + cos x₂ + cos x₃ > 2 - ε. Thus 2 is the best possible limit.

For n > 3, take x₁, x₂, x₃ to be the three largest x_i. Then we must have tan x₁ tan x₂ tan x₃ ≥ 2√2. Take y₁ ≤ x₁ so that tan y₁ tan x₂ tan x₃ = 2√2. Then cos x₁ + cos x₂ + cos x₃ ≤ cos y₁ + cos x₂ + cos x₃ < 2. But cos x_i < 1 for i > 3, so cos x₁ + cos x₂ + ... + cos x_n < n-1.

An alternative solution

First we establish a more general result for n = 2, that if tan x tan y = c ≥ 2, then cos x + cos y ≤ c/√(c²-1).

Put 1/w² = (1 + tan²x)(1 + tan²y) = sec²x sec²y, so 2 cos x cos y = 2w and cos²x + cos²y = (sec²x + sec²y)/(sec²x sec²y) = w²(2 + tan²x + tan²y) = w²(1/w² + 1 - c²). So (cos x + cos y)² = 1 + 2w - w²(c² - 1) = c²/(c²-1) - (c²-1)(w - 1/(c²-1) )² ≤ c²/(c²-1).

For c = 2 we can exhibit x, y which achieve this limit (as in the first solution), thus demonstrating that it is best possible. For c > 2 we do not need to show it is best possible. Take n = 3, so that tan x tan y tan z = 2√2. Take x to be the smallest, so that tan y tan z ≥ 2. Then, using the extended result for n = 2, cos x + cos y + cos z ≤ cos x + (2√2)/√(8 - tan²x). We wish to show that this is < 2. Squaring, that is equivalent to 8 ≤ (8 - tan²x)(4 - 4 cos x + cos²x). Expanding and putting k = cos x, we get 0 ≤ 23 - 32k + 9k² - 4(1-k²)/k² + 4(1-k²)/k, or 9k⁴ - 36k³ + 27k² + 4k - 4 > 0. Factorising, (k-1)(9k³ - 27k² + 4) > 0 (*). But tan x ≤ √2, so k ≥ 1/√3 and hence 9k³ - 27k² + 4 = 9k²(k - 3) + 4 < 3(1-3) + 4 < 0. Since x > 0, k < 1, so (*) holds and hence the limit 2 holds for n = 3. We show that 2 is best possible as in the first solution. The case n > 3 also follows as in the first solution.

Problem B1

Find all positive integer triples (d, m, n) with d > 1, m > 1 such that d^m + 1 divides dⁿ + 203.

Answer

(d,m,n) = (2,2,1), (2,3,2), (2,4,8), (2,6,9), (3,2,3), (4,2,4), (5,2,1), (8,2,3), (10,2,2), (203,m,m+1)

Also if (d,m,n) is a solution, then so is (d,m,n+2km) for any positive integer k.

Solution

Thanks to Polly T Wang

(d^2m - 1) = (d^m - 1)(d^m + 1) is a factor of (d^2mk - 1) and hence also of (d^n+2mk - dⁿ) for any positive integer k. Hence d^m + 1 divides dⁿ + 203 iff it divides d^n+2mk + 203. Thus we need only consider 1 ≤ n ≤ 2m. We consider separately the cases n = m, n = 2m, 1 ≤ n ≤ m-1, and m+1 ≤ n ≤ 2m-1.

Case 1. n = m. Then d^m + 1 divides d^m + 203 and hence also 202 = 2·101. But d, m > 1, so d = 10, m = 2 and (d,m,n) = (10,2,2) is a solution.

Case 2. n = 2m. Then d^m + 1 divides d^2m + 203 and d^2m - 1 and hence 204 = 2²3·17. The only possibility is d^m = 16, giving (4,2,4) and (2,4,8).

Case 3. 1 ≤ n ≤ m-1. Then d(d-1) ≤ d^m - d^m-1 ≤ d^m - dⁿ ≤ 202 (since we must have dⁿ + 203 ≥ d^m + 1). Hence d ≤ 14. We now use d^m-1(d-1) ≤ 202 to give: if d=2, m-1 ≤ 7; if d=3, m-1 ≤ 4; if d=4, m-1 ≤ 3; if d=5,6, m-1 ≤ 2; if d=7,...,14 then m-1 = 1. We now check all these cases.

For d=2, we have 2^m+1 = 5, 9, 17, 33, 65, 129, 257 for m=2,...,8, and 2ⁿ+203 = 205=5·41, 207=9·23, 211, 219=3·73, 235=5·47, 267=3·89, 331. So the only cases where 2^m+1 divides 2ⁿ+203 and n ≤ m-1 are: (d,m,n) = (2,3,2), (2,2,1). For d=3, we have 3ⁿ+203 = 206=2·103, 212=4·53, 230=2·5·23 or 284=4·71 and 3^m+1 = 10, 28, 82 or 244, which gives no solutions. For d=4, we have 4ⁿ+203 = 207=9·23, 219=3·73 or 267=3·89 and 4^m+1 = 17, 65, 257, which gives no solutions. For d=5, we have 5ⁿ+203 = 208=16·13 or 228=4·3·19 and 5^m+1 = 26 or 126, which gives the solution (d,m,n) = (5,2,1). For d=6, we have 6ⁿ+203 = 209=11·19 or 239, and 6^m+1 = 37 or 217, which gives no solutions. For d=7, we must have 7²+1=50 divide 7¹+203=210, which fails. Similarly, 8²+1=65 does not divide 8+203=211, 9²+1=82 does not divide 212, 10²+1 does not divide 213, 11²+1=122 does not divide 214, 12²+1=145 does not divide 215, 13²+1=170 does not divide 216, and 14²+1=197 does not divide 217.

Case 4. m+1 ≤ n ≤ 2m-1. We have dⁿ + 203 = a(d^m + 1), so a = dⁿ - ad^m + 203 = 203 mod d^m. So put a = bd^m + 203. If b > 0, then a ≥ d^m + 203, so a(d^m + 1) > d^2m + 203 > dⁿ + 1. Contradiction, so b ≤ 0.

We have dⁿ + 203 = a(d^m + 1) = bd^2m + 203d^m + bd^m + 203, so d^n-m = 203 + bd^m + b. Hence d^n-m divides b+203. Put c = (b+203)/d^n-m. Then d^n-m + 203d^m = bd^m + 203 + b + 203d^m = (b + 203)(d^m + 1) = cd^n-m(d^m+1), so c(d^m+1) = 203d^2m-n + 1. Hence d^m+1 ≤ 203d^2m-n + 1, so d^m ≤ 203d^2m-n, so d^n-m ≤ 203 (*).

Suppose n=m+1. Then d^m+1 divides d^m+1+203 and d(d^m+1) and hence their difference 203-d (**) (which is positive by (*) ). If d = 203, then it is easily checked that any m works, giving the solution (203,m,m+1). If d < 203, then d^m + 1 ≤ 203 - d, so d^m + d ≤ 202 (**). But m ≥ 2 (given), so d ≤ 13. It is easily checked that the pairs (d,m) satisfying (**) are (13,2), (12,2), (11,2), (10,2), (9,2), (8,2), (7,2), (6,2), (5,2), (5,3), (4,2), (4,3), (3,2), (3,3), (3,4), (2,2), (2,3), (2,4), (2,5), (2,6), (2,7). It is easy to check that of these only (8,2) and (3,2) satisfy (**), giving the solutions (3,2,3), (8,2,3).

Finally suppose n-m ≥ 2. The condition (*) implies d = 2 and n-m ≤ 7, d = 3 and n-m ≤ 4, d = 4 or 5 and n-m ≤ 3, or d = 6,7, ...,13 and n-m = 2. We have d^n-m = 203 + b(d^m+1). If b = 0, then a = 203, so dⁿ = 203d^m, giving d = 203 and n = m+1. But we are assuming n-m > 1, so we must have b ≠ 0. Hence d^m + 1 divides 203 - d^n-m (***).

We now have to examine the twenty odd cases to see if they satisfy (***). Take d = 2. We are looking for a factor of 203 - d^n-m which is 1 more than a power of 2. For d^n-m = 4, 199 is prime and 198 not a power of 2. For d^n-m = 8, 195 = 3·5·13 with factors 2+1, 4+1 and 64+1. 2+1 gives m = 1, 4+1 gives n>2m, but 64+1 gives the solution (2,6,9). For d^n-m = 16, 187 = 11·17, the only factor of the required form is 17, but that gives n=2m. For d^n-m = 32, 171 = 9·19 has no factors of the required form. For d^n-m = 64, 139 is prime and 138 is not a power of 2. For d^n-m = 128, 75 has no factors of the required form. That exhausts d = 2.

Take d = 3. 203 - 3² = 194 = 2·97 has no factors of the form 3^k+1. Similarly, 203 - 3³ = 176 = 16·11 has no factors of the required form. Similarly, 203 - 3⁴ = 122 = 2·61 has no factors of the required form.

Take d = 4. 203 - 4² = 187. The only factor of the required form is 17, but then n>2m. 203 - 4³ = 139, which has no factors of the required form.

Take d = 5. 203 - 5² = 2·89, which has no factors of the required form. 203 - 53 = 78 = 2·3·13, which has no factors of the required form.

Similarly for d = 6, 7, ... , 13, we note that 203 - 36 = 167 is not divisible by 37 (the only possible candidate, since 6³+1 is too big), 203 - 49 is not divisible by 50, 203 - 64 is not divisible by 65, 203 - 81 is not divisible by 82, 203 - 100 is not divisible by 101, 203 - 121 is not divisible by 122, 203 - 144 is not divisible by 145, 203 - 169 is not divisible by 170.

Whilst I am grateful for this solution, it seems a fairly horrendous slog. Any more elegant solutions would be welcome.

Problem B2

There are 10 applicants for a job, labeled 1, 2, ... , 10. Their suitability for the job is ranked in this order (so 1 is more suitable than 2, who is more suitable than 3 and so on). But an applicant's ability is only measured when they are interviewed. They are interviewed in the order a₁, a₂, ... , a₁₀. The first three interviewed are automatically rejected. Thereafter if an applicant's suitability is better than that of all previous applicants they are accepted (without interviewing the other applicants). If the first nine applicants interviewed are not accepted, then the tenth is automatically accepted. Let n_i be the number of permutations a₁, ... , a₁₀ which result in applicant i getting the job. Show that n₁ > n₂ > ... > n₈ = n₉ = n₁₀. Show that the probability that one of 1, 2, 3 gets the job is over 70% and that the probability of one of 8, 9, 10 getting the job is not more than 10%.

Solution

Thanks to Li Yi

Let A(i, j) be the number of permutations in which i is the highest ranked in the first three applicants, and j gets the job. Evidently, A(1, 1) = 0, and A(1, j) = 3·8! for j > 1, because there are 3 possibilities for 1's position, j must come last, then there are 8! possibilities for the other 8.

Obviously A(9, j) = A(10, j) = 0, because the highest ranked in the first three must be 8 or better. For 9 > i > 1, A(i, j) = 0 for j ≥ i, and 3( 7C(i-1) ) (i-2)! (10-i)! for j < i. Because there are 3 possibilities for i's position. All of 1, 2, ... , i-1 must come in the last 7 ( 7C(i-1) possibilities), and j must be the first of them. There are then (i-2)! possibilities for the others amongst 1, 2, ... , i-1. Finally the remaining numbers i+1, i+2, ... , 10 can be arranged in (10-i)! ways. It is convenient to put k = 3·8!, a_i = A(i,j) for i > j (and i = 2, 3, ... , 8). So we have:

n₁ = a₂ + a₃ + ... + a₈
n₂ = k + a₃ + ... + a₈
n₃ = k + a₄ + ... + a₈
...
n₇ = k + a₈
n₈ = n₉ = n₁₀ = k

It is now immediate that n₂ > n₃ > ... > n₇ > n₈ = n₉ = n₁₀ and (n₈ + n₉ + n₁₀)/10! = 1/10. Moreover a₂ = 3·7·8! > k, so n₁ > n₂.

Finally, we find n₁ = 3·7!·3349/35, n₂ = 3·7!·1669/35, n₃ = 3·7!·934/35, and hence (n₁ + n₂ + n₃)/10! = 124/175 > 70%.

Problem B3

a, b, c d are positive reals satisfying ab + cd = 1 and the four points (x₁, y₁), (x₂, y₂), (x₃, y₃), (x₄, y₄) lie on the circle x² + y² = 1. Show that (ay₁ + by₂ + cy₃ + dy₄)² + (ax₄ + bx₃ + cx₂ + dx₁)² ≤ 2(a/b + b/a + c/d + d/c).

Solution

Thanks to Li Yi

We have (ay₁ + by₂)² ≤ (ay₁ + by₂)² + (ax₁ - bx₂)² = a² + b² + 2ab(y₁y₂ - x₁x₂). Similarly, (cx₂ + dx₁)² ≤ c² + d² + 2cd(x₁x₂ - y₁y₂).

Hence (ay₁ + by₂)²/ab + (cx₂ + dx₁)²/cd ≤ (a² + b²)/ab + (c² + d²)/cd = (a/b + b/a + c/d + d/c). The same argument shows that (ax₄ + bx₃)²/ab + (cy₃ + dy₄)²/cd ≤ (a/b + b/a + c/d + d/c).

But now Cauchy-Schwartz gives ( (ay₁ + by₂) + (cy₃ + dy₄) )² = ( √(ab) (ay₁ + by₂)/√(ab) + √(cd) (cy₃ + dy₄)/√(cd) )² ≤ (ab + cd)( (ay₁ + by₂)²/ab + (cy₃ + dy₄)²/cd ) = (ay₁ + by₂)²/ab + (cy₃ + dy₄)²/cd. Similarly ( (ax₄ + bx₃) + (cx₂ + dx₁) )² ≤ (ax₄ + bx₃)²/ab + (cx₂ + dx₁)²/cd. So, adding, (ay₁ + by₂ + cy₃ + dy₄)² + (ax₄ + bx₃ + cx₂ + dx₁)² ≤ 2(a/b + b/a + c/d + d/c)

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

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 E₁F₁G₁H₁ (E₁ is the intersection of the lines through A and B, F₁ is the intersection of the lines through B and C, and so on). Find CF₁/CG₁ in terms of AH₁/AE₁.

A2. a_1/, a₂, a₃, ... is a sequence of integers with a₁ positive and a_n = [(1 + 2/n)(a_n-1 - 1)] + 1. Find a_n in terms of a₁ 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 x₀, x₁, ... , x_n+1 satisfies x₀ = x_n+1 = 0 and (x_i-1 + x_i+1)/2 = x_i + x_i³ - a³ for i = 1, 2, ... , n. Show that the sequence is uniquely determined by n and a and that |x_i| ≤ |a|.

B2. a₁ < a₂ < ... < a_n is a sequence of positive integers with ∑ 1/a_i ≤ 1. Prove that (∑ 1/(a_i² + x²) )² ≤ 1/(2a₁²-2a₁+2x²) for any real x.

B3. Show that any sufficiently large integer can be expressed as a sum of distinct positive integers a₁, a₂, ... , a₂₀₀₄ such that each a_i 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 E₁F₁G₁H₁ (E₁ is the intersection of the lines through A and B, F₁ is the intersection of the lines through B and C, and so on). Find CF₁/CG₁ in terms of AH₁/AE₁.

Answer

CF₁/CG₁ = 1/(AH₁/AE₁)

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 E₁F₁ and G₁H₁ meet at R. Then area PAD/area PDH = AD/DH = area ARH₁/area HRH₁. Similarly, area PBA/area PBE = BA/BE = area ARE₁/area ERE₁. Hence (area PAD/area PDH)(area PBE/area PBA) = (area ARH₁/area HRH₁)(area ERE₁/area ARE₁). But area PAD/area PBA = DO/BO and area ARH₁/area ARE₁ = AH₁/AE₁, so (DO/BO)(area PBE/area PDH) = (AH₁/AE₁)(area ERE₁/area HRH₁). Now the bases PE and RE₁ of PBE and ERE₁ are parallel and the heights are the same, so area PBE/area ERE₁ = PE/RE₁. Similarly, the bases PH and RH₁ of PDH and HRH₁ are parallel and the heights are the same, so area PDH/area HRH₁ = PH/RH₁. Also triangles PHE and RH1E1 are similar (corresponding sides are parallel, so the angles are equal). Hence PE/RE₁ = PH/RH₁. Hence AH₁/AE₁ = DO/BO.

A similar argument gives CG₁/CF₁ = DO/BO. Hence AH₁/AE₁ = CG₁/CF₁.

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 E₁F₁ and H₁G₁ are parallel to AC. So AH₁/E₁H₁ = area AH₁G₁/area E₁H₁G₁ = area CH₁G₁/area F₁H₁G₁ = CG₁/F₁G₁. Hence AH₁/AE₁ = CG₁/CF₁.

Thanks to Polly T Wang

Problem A2

a_1/, a₂, a₃, ... is a sequence of integers with a₁ positive and a_n = [(1 + 2/n)(a_n-1 - 1)] + 1. Find a_n in terms of a₁ and n.

Answer

If a₁ = 3k, then a_n = 1 + [(n+2)²/4] + (k-1)(n+1)(n+2)/2
if a₁ = 3k+1, then a_n = 1 + k(n+1)(n+2)/2
if a₁ = 3k+2, then a_n = (n+1)(1 + k(n+2)/2)

Solution

It is convenient to put b_n = a_n - 1, so b_n = [b_n-1(n+2)/n]. It is a trivial induction that b_n = 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 b₁ = 3k and hence a₁ = 3k+1.

We claim that b_n = n is also a solution. For [(n-1)(n+2)/n] = [(n²+n-2)/n] = [n+1-2/n] = n (for n ≥ 2). We can add this to the previous solution to get b_n = n + k(n+1)(n+2)/2 which gives b₁ = 3k+1 and hence a₁ = 3k+2.

Finally, we claim that b_n = [(n+2)²/4] is also a solution. That implies b_2m = (m+1)² and b_2m-1 = m(m+1). Then b_2m+1 = [(m+1)²(2m+3)/(2m+1)] = [(m+1)² + 2(m+1)²/(2m+1)] = [(m+1)² + (m+1)(2m+1)/(2m+1) + (m+1)/(2m+1)] = [(m+1)(m+2) + (m+1)/(2m+1)] = (m+1)(m+2). Also b_2m+2 = [(m+1)(m+2)(2m+4)/(2m+2)] = [(m+2)(m+2)] = (m+2)², which proves the claim. It gives b₁ = 2. Adding to the first solution we get the solution b_n = [(n+2)²/4] + (k-1)(n+1)(n+2)/2 which gives b₁ = 3k-1 and hence a₁ = 3k.

The sequence is obviously determined by a₁ and the recurrence rule, so we have found solutions for all positive integers a₁.

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

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 H_Z be the open half-plane on the opposite side of XY to Z. Similarly, let H_Y be the open half-plane on the opposite side of ZX to Y, and H_X the open half-plane on the opposite side of YZ to X. Then H_X ∪ H_Y ∪ H_Z is the whole plane outside XYZ. So all 7 vertices of the convex 7-gon belong to H_X ∪ H_Y ∪ H_Z. Hence one of H_X, H_Y, H_Z 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 x₀, x₁, ... , x_n+1 satisfies x₀ = x_n+1 = 0 and (x_i-1 + x_i+1)/2 = x_i + x_i³ - a³ for i = 1, 2, ... , n. Show that the sequence is uniquely determined by n and a and that |x_i| ≤ |a|.

Solution

Suppose first a = 0. Suppose some x_i > 0. Then take x_j to be the largest x_i. We have x_j > 0 and hence j ≠ 0 or n+1. So (x_j-1 + x_j+1)/2 = x_j + x_j³ > x_j. So x_j-1 or x_j+1 > x_j. Contradiction. So all x_i ≤ 0. Similarly, if some x_i < 0, the take x_j to be the smallest. But then (x_j-1 + x_j+1)/2 = x_j + x_j³ < x_j. Contradiction. So all x_i ≥ 0. Hence all x_i = 0. It is easy to check that for a = 0, x₀ = x₁ = ... = x_n+1 = 0 satisfies the conditions and so is the unique solution for any n.

Now suppose a > 0. Suppose some x_i < 0. Then take x_j to be the smallest x_i. But then (x_j-1 + x_j+1)/2 = x_j + x_j³ - a³ < x_j. Contradiction. So all x_j ≥ 0. Suppose some x_i = 0 for i ≠ 0 or n+1. Then (x_i-1 + x_i+1)/2 = x_i + x_i³ - a³ = -a³ < 0, so x_i-1 or x_i+1 < 0. Contradiction. Thus all the terms except the first and last are positive. Let x_j be the largest term. Then we must have x_j ≤ a, because otherwise (x_j-1 + x_j+1)/2 = x_j + x_j³ - a³ > x_j. Contradiction. In fact we must have x_j < a, because if x_j = a, then (x_j-1 + x_j+1)/2 = x_j + x_j³ - a³ = x_j and hence x_j-1 = x_j+1 = a. Repeating, we get eventually x₀ or x_n+1 = a. Contradiction.

Now suppose x₁ = x. We ignore for the moment the requirement that x_n+1 = 0. We show by induction on k that x_k and x_k-x_k-1 are continuous, strictly increasing functions of x. That is obvious for k=1. Put k=2. We have x₂ = 2x + 2x³ - 2a³, and x₂-x₁ = x + 2x³ - 2a³, which are both continuous, strictly increasing functions of x. Suppose it is true for k. Then x_k+1 = 2x_k + 2x_k³ - 2a³ - x_k-1 = x_k + 2x_k³ - 2a³ + (x_k - x_k-1) and x_k+1 - x_k = 2x_k³ - 2a³ + (x_k - x_k-1). Since both x_k and (x_k - x_k-1) are both continuous, strictly increasing functions of x, so are x_k+1 and (x_k+1 - x_k).

In particular, if follows that x_n+1 is a continuous, strictly increasing function of x. Put x_n+1 = f(x). Now if we take x = a, then x₂ = 2a > a, and by a trivial induction x_k > a for all k > 1. So, in particular, f(a) > a. On the other hand, if we take x = 0, then x₂ = -2a³ < 0, and by a trivial induction x_k < 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 x_i is the sequence uniquely determined by n and -a, then it is clear that the sequence -x_i is a solution for n and a. Conversely, if y_i is a solution for n and a, then -y_i is a solution for n and -a and hence must be the unique sequence x_i. So the result is also true for a negative.

Problem B2

a₁ < a₂ < ... < a_n is a sequence of positive integers with ∑ 1/a_i ≤ 1. Prove that (∑ 1/(a_i² + x²) )² ≤ 1/(2a₁²-2a₁+2x²) for any real x.

Solution

Appying Cauchy-Schwartz, we have lhs = (∑ (√a_i/(a_i²+x²))(1/√a_i) )² ≤ (∑ a_i/(a_i²+x²)² )(∑ 1/a_i) ≤ ∑ a_i/(a_i²+x²)².

Now (a_i²+x²)² > (a_i²+x²)² - a_i² > 0, so ∑ a_i/(a_i²+x²)² < (1/2) ∑ (1/(a_i²+x²-a_i) - 1/(a_i²+x²+a_i) ).

Now a_i+1 ≥ a_i+1, so a_i+1²-a_i+1+x² ≥ a_i²+a_i+x² and hence ∑ (1/(a_i²+x²-a_i) ≤ 1/(a₁²+x²-a₁) + (∑ 1/(a_i²+x²+a_i) ) - 1/(a_n²+x²+a_n) ≤ 1/(a₁²+x²-a₁) + (∑ 1/(a_i²+x²+a_i) ). Hence lhs < (1/2) 1/(a₁²+x²-a₁), as required.

Thanks to Li Yi

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

William Lowell Putnam Mathematical Competition

64th Putnam Mathematical Competition 2003 Problems

A1. Given n, how many ways can we write n as a sum of one or more positive integers a₁ ≤ a₂ ≤ ... ≤ a_k with a_k - a₁ = 0 or 1.
A2. a₁, a₂, ... , a_n, b₁, ... , b_n are non-negative reals. Show that (∏ a_i)^1/n + (∏b_i)^1/n ≤ (∏(a_i+b_i))^1/n.
A3. Find the minimum of \|sin x + cos x + tan x + cot x + sec x + cosec x\| for real x.
A4. a, b, c, A, B, C are reals with a, A non-zero such that \|ax² + bx + c\| ≤ \|Ax² + Bx + C\| for all real x. Show that \|b² - 4ac\| ≤ \|B² - 4AC\|.
A5. An n-path is a lattice path starting at (0,0) made up of n upsteps (x,y) → (x+1,y+1) and n downsteps (x,y) → (x-1,y-1). A downramp of length m is an upstep followed by m downsteps ending on the line y = 0. Find a bijection between the (n-1)-paths and the n-paths which have no downramps of even length.
A6. Is it possible to partition {0, 1, 2, 3, ... } into two parts such that n = x + y with x ≠ y has the same number of solutions in each part for each n?
B1. Do their exist polynomials a(x), b(x), c(y), d(y) such that 1 + xy + x²y² ≡ a(x)c(y) + b(x)d(y)?
B2. Given a sequence of n terms, a₁, a₂, ... , a_n the derived sequence is the sequence (a₁+a₂)/2, (a₂+a₃)/2, ... , (a_n-1+a_n)/2 of n-1 terms. Thus the (n-1)th derivative has a single term. Show that if the original sequence is 1, 1/2, 1/3, ... , 1/n and the (n-1)th derivative is x, then x < 2/n.
B3. Show that ∏_i=1ⁿ lcm(1, 2, 3, ... , [n/i]) = n!.
B4. az⁴ + bz³ + cz² + dz + e has integer coefficients (with a ≠ 0) and roots r₁, r₂, r₃, r₄ with r₁+r₂ rational and r₃+r₄ ≠ r₁+r₂. Show that r₁r₂ is rational.
B5. ABC is an equilateral triangle with circumcenter O. P is a point inside the circumcircle. Show that there is a triangle with side lengths \|PA\|, \|PB\|, \|PC\| and that its area depends only on \|PO\|.
B6. Show that ∫₀¹ ∫₀¹ \|f(x) + f(y)\| dx dy ≥ ∫₀¹ \|f(x)\| dx for any continuous real-valued function on [0,1].