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