A1. ABC is an acute-angled triangle with AB and AC unequal, incenter I and orthocenter H. BB1 and CC1 are medians. The line IB1 meets the line AB at B2, and the line IC1 meets the line CA at C2. The line B2C2 meets the line BC at K. The circumcenter of BHC is O'. Show that A, I and O' are collinear iff area BKB2 = area CKC2.
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 x1, x2, ... , xn all satisfy 0 < xi < π/2. Also tan x1 tan x2 ... tan xn = 2n/2. Find the smallest L such that cos x1 + cos x2 + ... + cos xn ≤ L for all such xi.
B1. Find all positive integer triples (d, m, n) with d > 1, m> 1 such that dm + 1 divides dn + 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 a1, a2, ... , a10.
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 ni be the number of permutations a1, ... , a10 which result in applicant i getting the job. Show that n1 > n2 > ... > n8 = n9 = n10.
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 (x1, y1), (x2, y2), (x3, y3), (x4, y4) lie on the circle x2 + y2 = 1. Show that (ay1 + by2 + cy3 + dy4)2 + (ax4 + bx3 + cx2 + dx1)2 ≤ 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. BB1 and CC1 are medians. The line IB1 meets the line AB at B2, and the line IC1 meets the line CA at C2. The line B2C2 meets the line BC at K. The circumcenter of BHC is O'. Show that A, I and O' are collinear iff area BKB2 = area CKC2.
Solution
Thanks to Allen Zhang
We show that A, I and O' are collinear iff angle BAC = 60o.
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 = 90o-∠C, ∠HCB = 90o-∠B, so ∠BHC = ∠B + ∠C. So if P = O', then ∠BPC = 2 x ∠ at circumference = 2(180o - ∠B - ∠C) = 2∠A. But BACP is cyclic, so ∠A + 2∠A = 180o. Hence ∠A = 60o.
Conversely, if ∠A = 60o, then ∠BO'C = 2(180o - ∠BHC) = 2∠A = 120o, so BACO' is cyclic, so O' = P.
Note that area BKB2 = area CKC2 iff area ABC = area AB2C2. But area ABC = AB·AC sin A, area AB2C2 = AB2·AC2 sin A, so area BKB2 = area CKC2 iff AB·AC = AB2·AC2.
We have area AIB2 = rAB2/2, area AIB1 = ½ area AIC = br/4, area AB1B2 = AB2 x height/2 = AB2 (ht C from AB)/4 = AB2 r(a+b+c)/4c. Hence 2c AB2 + bc = AB2(a+b+c), so AB2 = bc/(a+b-c). Similarly, AC2 = bc/(a-b+c).
Thus AB·AC = AB2·AC2 is equivalent to bc = (a+b-c)(a-b+c) = a2-b2+2bc-c2, or (b2+c2-a2)/2bc = 1/2. But by the cosine rule, lhs = cos A. So AB·AC = AB2·AC2 iff A = 60o.
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.
(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 x1, x2, ... , xn all satisfy 0 < xi < π/2. Also tan x1 tan x2 ... tan xn = 2n/2. Find the smallest Ln such that cos x1 + cos x2 + ... + cos xn ≤ Ln for all such xi.
Answer
L1 = 1/√3, L2 = 2/√3, Ln = n-1 for n > 2.
Solution
Thanks to Li Yi
The case n = 1 is trivial, because x1 is fixed.
For n = 2 we wish to prove that if tan x1 tan x2 = 2, then cos x1 + cos x2 ≤ 2/√3. That is equivalent to cos2x1 + cos2x2 + 2 cos x1 cos x2 ≤ 4/3, or 1/(1 + tan2x1) + 1/(1 + tan2x2) + 2/√((1 + tan2x1)(1 + tan2x2)) ≤ 4/3. Put k = √((1 + tan2x1)(1 + tan2x2)) = √(5 + tan2x1 + tan2x2). Then we wish to show that (k2 - 3)/k2 + 2/k ≤ 4/3 or 2/k - 3/k2 ≤ 1/3 or (k-3)2 ≥ 0, which is obviously true. Moreover, if we take x1 = x2 = tan-1√2, then tan x1 tan x2 = 2, and cos x1 = cos x2 = 1/√3, so cos x1 + cos x2 = 2/√3. Hence 2/√3 is best possible.
Now take n = 3. We show that if tan x1 tan x2 tan x3 = 2√2, then cos x1 + cos x2 + cos x3 < 2. Take x1 ≥ x2 ≥ x3. If tan2x2 + tan2x3 ≥ 7, then tan2x1 ≥ tan2x2 ≥ 7/2, so cos x1 and cos x2 ≤ (√2)/3 and hence cos x1 + cos x2 + cos x3 ≤ (2√2)/3 + 1 < 2. So assume tan2x2 + tan2x3 < 7.
We have cos x2 ≤ (1 + cos2x2)/2 = 1 - ½sin2x2. Similarly for x3, so cos x2 + cos x3 ≤ 2 - (sin2x2 + sin2x3)/2 ≤ 2 - sin x2 sin x3. Also cos x1 = 1/√(1+tan2x1) = 1/√(1+8/(tan2x2 tan2x3)) = sin x2 sin x3/√(8 cos2x2 cos2x3 + sin2x2 sin2x3). So cos x1 + cos x2 + cos x3 ≤ 2 - sin x2 sin x3 (1 - 1/√(8 cos2x2 cos2x3 + sin2x2 sin2x3). So we have to show that 8 cos2x2 cos2x3 + sin2x2 sin2x3 > 1, or 8 + tan2x2 tan2x3 > sec2x2 sec2x3 (= (1 + tan2x2)(1 + tan2x3) ), or tan2x2 + tan2x3 < 7.
Finally, if we take x1 and x2 close to zero, so that cos x1 and cos x2 > 1 - ε/2, then we can take x3 so that tan x1 tan x2 tan x3 = 2√2. We have cos x3 > 0, so cos x1 + cos x2 + cos x3 > 2 - ε. Thus 2 is the best possible limit.
For n > 3, take x1, x2, x3 to be the three largest xi. Then we must have tan x1 tan x2 tan x3 ≥ 2√2. Take y1 ≤ x1 so that tan y1 tan x2 tan x3 = 2√2. Then cos x1 + cos x2 + cos x3 ≤ cos y1 + cos x2 + cos x3 < 2. But cos xi < 1 for i > 3, so cos x1 + cos x2 + ... + cos xn < 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/√(c2-1).
Put 1/w2 = (1 + tan2x)(1 + tan2y) = sec2x sec2y, so 2 cos x cos y = 2w and cos2x + cos2y = (sec2x + sec2y)/(sec2x sec2y) = w2(2 + tan2x + tan2y) = w2(1/w2 + 1 - c2). So (cos x + cos y)2 = 1 + 2w - w2(c2 - 1) = c2/(c2-1) - (c2-1)(w - 1/(c2-1) )2 ≤ c2/(c2-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 - tan2x). We wish to show that this is < 2. Squaring, that is equivalent to 8 ≤ (8 - tan2x)(4 - 4 cos x + cos2x). Expanding and putting k = cos x, we get 0 ≤ 23 - 32k + 9k2 - 4(1-k2)/k2 + 4(1-k2)/k, or 9k4 - 36k3 + 27k2 + 4k - 4 > 0. Factorising, (k-1)(9k3 - 27k2 + 4) > 0 (*). But tan x ≤ √2, so k ≥ 1/√3 and hence 9k3 - 27k2 + 4 = 9k2(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 dm + 1 divides dn + 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
(d2m - 1) = (dm - 1)(dm + 1) is a factor of (d2mk - 1) and hence also of (dn+2mk - dn) for any positive integer k. Hence dm + 1 divides dn + 203 iff it divides dn+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 dm + 1 divides dm + 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 dm + 1 divides d2m + 203 and d2m - 1 and hence 204 = 223·17. The only possibility is dm = 16, giving (4,2,4) and (2,4,8).
Case 3. 1 ≤ n ≤ m-1. Then d(d-1) ≤ dm - dm-1 ≤ dm - dn ≤ 202 (since we must have dn + 203 ≥ dm + 1). Hence d ≤ 14. We now use dm-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 2m+1 = 5, 9, 17, 33, 65, 129, 257 for m=2,...,8, and 2n+203 = 205=5·41, 207=9·23, 211, 219=3·73, 235=5·47, 267=3·89, 331. So the only cases where 2m+1 divides 2n+203 and n ≤ m-1 are: (d,m,n) = (2,3,2), (2,2,1). For d=3, we have 3n+203 = 206=2·103, 212=4·53, 230=2·5·23 or 284=4·71 and 3m+1 = 10, 28, 82 or 244, which gives no solutions. For d=4, we have 4n+203 = 207=9·23, 219=3·73 or 267=3·89 and 4m+1 = 17, 65, 257, which gives no solutions. For d=5, we have 5n+203 = 208=16·13 or 228=4·3·19 and 5m+1 = 26 or 126, which gives the solution (d,m,n) = (5,2,1). For d=6, we have 6n+203 = 209=11·19 or 239, and 6m+1 = 37 or 217, which gives no solutions. For d=7, we must have 72+1=50 divide 71+203=210, which fails. Similarly, 82+1=65 does not divide 8+203=211, 92+1=82 does not divide 212, 102+1 does not divide 213, 112+1=122 does not divide 214, 122+1=145 does not divide 215, 132+1=170 does not divide 216, and 142+1=197 does not divide 217.
Case 4. m+1 ≤ n ≤ 2m-1. We have dn + 203 = a(dm + 1), so a = dn - adm + 203 = 203 mod dm. So put a = bdm + 203. If b > 0, then a ≥ dm + 203, so a(dm + 1) > d2m + 203 > dn + 1. Contradiction, so b ≤ 0.
We have dn + 203 = a(dm + 1) = bd2m + 203dm + bdm + 203, so dn-m = 203 + bdm + b. Hence dn-m divides b+203. Put c = (b+203)/dn-m. Then dn-m + 203dm = bdm + 203 + b + 203dm = (b + 203)(dm + 1) = cdn-m(dm+1), so c(dm+1) = 203d2m-n + 1. Hence dm+1 ≤ 203d2m-n + 1, so dm ≤ 203d2m-n, so dn-m ≤ 203 (*).
Suppose n=m+1. Then dm+1 divides dm+1+203 and d(dm+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 dm + 1 ≤ 203 - d, so dm
+ 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 dn-m = 203 + b(dm+1). If b = 0, then a = 203, so dn = 203dm, giving d = 203 and n = m+1. But we are assuming n-m > 1, so we must have b ≠ 0. Hence dm + 1 divides 203 - dn-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 - dn-m which is 1 more than a power of 2. For dn-m = 4, 199 is prime and 198 not a power of 2. For dn-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 dn-m = 16, 187 = 11·17, the only factor of the required form is 17, but that gives n=2m. For dn-m = 32, 171 = 9·19 has no factors of the required form. For dn-m = 64, 139 is prime and 138 is not a power of 2. For dn-m = 128, 75 has no factors of the required form. That exhausts d = 2.
Take d = 3. 203 - 32 = 194 = 2·97 has no factors of the form 3k+1. Similarly, 203 - 33 = 176 = 16·11 has no factors of the required form. Similarly, 203 - 34 = 122 = 2·61 has no factors of the required form.
Take d = 4. 203 - 42 = 187. The only factor of the required form is 17, but then n>2m. 203 - 43 = 139, which has no factors of the required form.
Take d = 5. 203 - 52 = 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 63+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 a1, a2, ... , a10.
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 ni be the number of permutations a1, ... , a10 which result in applicant i getting the job. Show that n1 > n2 > ... > n8 = n9 = n10.
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!, ai = A(i,j) for i > j (and i = 2, 3, ... , 8). So we have:
n1 = a2 + a3 + ... + a8
n2 = k + a3 + ... + a8
n3 = k + a4 + ... + a8
...
n7 = k + a8
n8 = n9 = n10 = k
n2 = k + a3 + ... + a8
n3 = k + a4 + ... + a8
...
n7 = k + a8
n8 = n9 = n10 = k
It is now immediate that n2 > n3 > ... > n7 > n8 = n9 = n10 and (n8 + n9 + n10)/10! = 1/10. Moreover a2 = 3·7·8! > k, so n1 > n2.
Finally, we find n1 = 3·7!·3349/35, n2 = 3·7!·1669/35, n3 = 3·7!·934/35, and hence (n1 + n2 + n3)/10! = 124/175 > 70%.
Problem B3
a, b, c d are positive reals satisfying ab + cd = 1 and the four points (x1, y1), (x2, y2), (x3, y3), (x4, y4) lie on the circle x2 + y2 = 1. Show that (ay1 + by2 + cy3 + dy4)2 + (ax4 + bx3 + cx2 + dx1)2 ≤ 2(a/b + b/a + c/d + d/c).
Solution
Thanks to Li Yi
We have (ay1 + by2)2 ≤ (ay1 + by2)2 + (ax1 - bx2)2 = a2 + b2 + 2ab(y1y2 - x1x2). Similarly, (cx2 + dx1)2 ≤ c2 + d2 + 2cd(x1x2 - y1y2).
Hence (ay1 + by2)2/ab + (cx2 + dx1)2/cd ≤ (a2 + b2)/ab + (c2 + d2)/cd = (a/b + b/a + c/d + d/c). The same argument shows that (ax4 + bx3)2/ab + (cy3 + dy4)2/cd ≤ (a/b + b/a + c/d + d/c).
But now Cauchy-Schwartz gives ( (ay1 + by2) + (cy3 + dy4) )2 = ( √(ab) (ay1 + by2)/√(ab) + √(cd) (cy3 + dy4)/√(cd) )2 ≤ (ab + cd)( (ay1 + by2)2/ab + (cy3 + dy4)2/cd ) = (ay1 + by2)2/ab + (cy3 + dy4)2/cd. Similarly ( (ax4 + bx3) + (cx2 + dx1) )2 ≤ (ax4 + bx3)2/ab + (cx2 + dx1)2/cd. So, adding, (ay1 + by2 + cy3 + dy4)2 + (ax4 + bx3 + cx2 + dx1)2 ≤ 2(a/b + b/a + c/d + d/c)WEBSITE ORIGINAL SOURCE
http://www.kidsmathbooks.com/2011/01/18th-chinese-mathematical-olympiad-2003.html
