17th Mexican Mathematical Olympiad Problems 2003
A1. Find all positive integers with two or more digits such that if we insert a 0 between the units and tens digits we get a multiple of the original number.
A2. A, B, C are collinear with B betweeen A and C. K1 is the circle with diameter AB, and K2 is the circle with diameter BC. Another circle touches AC at B and meets K1 again at P and K2 again at Q. The line PQ meets K1 again at R and K2 again at S. Show that the lines AR and CS meet on the perpendicular to AC at B.
A3. At a party there are n women and n men. Each woman likes r of the men, and each man likes r of then women. For which r and s must there be a man and a woman who like each other?
B1. The quadrilateral ABCD has AB parallel to CD. P is on the side AB and Q on the side CD such that AP/PB = DQ/CQ. M is the intersection of AQ and DP, and N is the intersection of PC and QB. Find MN in terms of AB and CD.
B2. Some cards each have a pair of numbers written on them. There is just one card for each pair (a,b) with 1 ≤ a < b ≤ 2003. Two players play the following game. Each removes a card in turn and writes the product ab of its numbers on the blackboard. The first player who causes the greatest common divisor of the numbers on the blackboard to fall to 1 loses. Which player has a winning strategy?
B3. Given a positive integer n, an allowed move is to form 2n+1 or 3n+2. The set Sn is the set of all numbers that can be obtained by a sequence of allowed moves starting with n. For example, we can form 5 → 11 → 35 so 5, 11 and 35 belong to S5. We call m and n compatible if Sm ∩ Sn is non-empty. Which members of {1, 2, 3, ... , 2002} are compatible with 2003?
Solutions
Problem A1
Find all positive integers with two or more digits such that if we insert a 0 between the units and tens digits we get a multiple of the original number.
Answer
15, 18, 45, or any muliple of 10
Solution
Let the number be n. Let n' be the number obtained by inserting the 0. n must also divide 10n and hence 10n - n'. If the last digit of n is d, then 10n - n' = 9d. So n must divide 9d. In particular, n must be a 2 digit number. For example if d = 9, we need a two digit number ending in 9 that divides 81. There are none. Similarly, we check d = 8 giving n = 18, d = 7 no solutions, d = 6, no solutions, d = 5 giving n = 15 or 45, d = 4 so solutions, d = 3 no solutions, d = 2 no solutions, d = 1 no solutions. Finally if d = 0, then any number works.
Thanks to Marco Avila Ponce de Leon for pointing out the multiple of 10, which I managed to overlook!
Problem A2
A, B, C are collinear with B betweeen A and C. K1 is the circle with diameter AB, and K2 is the circle with diameter BC. Another circle touches AC at B and meets K1 again at P and K2 again at Q. The line PQ meets K1 again at R and K2 again at S. Show that the lines AR and CS meet on the perpendicular to AC at B.
Solution
We show that ARSC is cyclic. We have ∠PRA = ∠PBA (circle diameter AB) = ∠PQB (circle PBQ) = ∠SQB (same angle) = ∠SCB. Hence ∠ARS + ∠SCA = 180o, so ARSC is cyclic. Let K3 be the circle ARSC. Then AR is the radical axis of K3 and K1, CS is the radical axis of K3 and K2, and the perpendicular to AC at B is the radical axis of K1 and K2, and the three radical axes concur.
Thanks to Julio Brau Avila.
Problem A3
At a party there are n women and n men. Each woman likes r of the men, and each man likes r of then women. For which r and s must there be a man and a woman who like each other?
Answer
r + s > n
Solution
Consider the number of pairs (W,M), where W is a woman and M a man. If no pair like each other, then the nr pairs (W,M) where W likes M and the ns pairs (W,M), where M likes W must all be distinct. But the total number of available pairs is n2, so we must have nr + ns ≤ n2 and hence r + s ≤ n.
Conversely, suppose r + s ≤ n. Label the women W1, W2, ... , Wn and the men M1, M2, ... , Mn. Let woman Wi like men Mi+k for k = 0, 1, 2, ... , r-1, and let man Mi like women Wi+k for k = 1, 2, ... , s (we use the cyclic subscript convention, so Wn+1 means W1 etc). Then it is clear that no woman and man like each other.
Problem B1
The quadrilateral ABCD has AB parallel to CD. P is on the side AB and Q on the side CD such that AP/PB = DQ/CQ. M is the intersection of AQ and DP, and N is the intersection of PC and QB. Find MN in terms of AB and CD.
Answer
MN = AB·CD/(AB+CD)
Solution
AMP and QMD are similar, so AM/MQ = AP/DQ. PNB and CNQ are similar, so PN/NC = PB/CQ. But AP/DQ = PB/CQ (given), so AM/MQ = PN/NC and hence MN is parallel to AB.
Also MN/CD = PM/(PM+MD) = AP/(AP+DQ). Similarly, MN/AB = QM/(QM+MA) = DQ/(AP+DQ). Hence MN/CD + MN/AB = 1.
Problem B2
Some cards each have a pair of numbers written on them. There is just one card for each pair (a,b) with 1 ≤ a < b ≤ 2003. Two players play the following game. Each removes a card in turn and writes the product ab of its numbers on the blackboard. The first player who causes the greatest common divisor of the numbers on the blackboard to fall to 1 loses. Which player has a winning strategy?
Answer
first
Solution
Consider the numbers on the board before the losing move. They must have gcd d > 1. If d is not a prime, then it has some proper factor k, so the card (1,k) can still be played. Contradiction. So d must be prime, and every pair (a,b) with d dividing ab must have been played. There are 2002 pairs (a,d), because a can be any of 1, 2, 3, ... , 2003 except d. Similarly, there are 2002 pairs (a,2d), provided that 2d ≤ 2003. However, this double-counts the pair (d,2d). So if d is chosen so that 2d < 2003 < 3d, then there will be 4003 possible pairs. The first player can bring this about by playing (1,997). Then the possible plays are (k,997) for k = 2, 3, ... , 996, 998, 999, ... , 2003 (2001 possibilities), and (k,1994) for k = 1, 2, ... , 996, 998, 999, ... , 1993, 1995, 1996, ... , 2003 (2001 possibilities). So there are an even number of moves available and the first player will win (the only way the second player can reduce the number of moves available is by losing).
Problem B3
Given a positive integer n, an allowed move is to form 2n+1 or 3n+2. The set Sn is the set of all numbers that can be obtained by a sequence of allowed moves starting with n. For example, we can form 5 → 11 → 35 so 5, 11 and 35 belong to S5. We call m and n compatible if Sm ∩ Sn is non-empty. Which members of {1, 2, 3, ... , 2002} are compatible with 2003?
Answer
166, 333, 500, 667, 1001, 1335, 1502
Solution
Let D be the operation a → 2a+1, and T the operation a → 3a+2. Note first that D and T commute, and they are obviously injective. Now we claim that if a = Dmb = Tnc, then we can find d such that b = Tnd and c = Dmd. We use induction on m.
Consider first m = 1. Note that k is odd iff Tk is odd. Now a = Db, so a is odd. But a = Tnc, so c is odd. Hence we can find d such that c = Dd. Then Db = DTnd, so b = Tnd, and the result is true for m = 1.
Suppose it is true for m and that a = Dm+1b = Tnc. Then Tnc is odd, so c is odd, so c = De. Hence Dmb = Tne. So, by induction, we can find d such that b = Tnd, e = Dmd. Then c = Dm+1d, b = Tnd, as required. So the result is true for m+1 and hence for all m.
It follows that if a = DrTsb = DmTnc, then b and c can both be obtained from some d. (wlog r ≥ m, so Dr-mTsb = Tnc. If s ≥ n, then we are home since c = Dr-mTs-nb, if not then Dr-mb = Tn-sc and we use the result just proved.)
Thus if we take m to be the smallest number which can lead to n, then we have n = DrTsm for some r,s and so the numbers which can lead to n are just DaTbm for 0 ≤ a ≤ r, and 0 ≤ b ≤ s. (For if k leads to n, then we can find d which leads to m and k, but d cannot be smaller than m, so d = m.)
Thus if k ∈ S2003 ∩ Sn, then 2003 and n can both be obtained from some d. Working backwards, we find that 2003 = D2T 166, where 166 is not odd and not 2 mod 3, so cannot be obtained from anything else. Hence the only numbers that lead to numbers derived from 2003 are those that derive from 166. We get 333 = D 166, 500 = T 166, 667 = D2166, 1001 = DT 166, 1335 = D3166, 1502 = T2166 (the others are all ≥ 2003).
Labels:
Mexican Mathematical Olympiad
Previous Article
