17th Mexican Mathematical Olympiad Problems 2003

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. K₁ is the circle with diameter AB, and K₂ is the circle with diameter BC. Another circle touches AC at B and meets K₁ again at P and K₂ again at Q. The line PQ meets K₁ again at R and K₂ 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 S_n 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 S₅. We call m and n compatible if S_m ∩ S_n 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. K₁ is the circle with diameter AB, and K₂ is the circle with diameter BC. Another circle touches AC at B and meets K₁ again at P and K₂ again at Q. The line PQ meets K₁ again at R and K₂ 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 = 180^o, so ARSC is cyclic. Let K₃ be the circle ARSC. Then AR is the radical axis of K₃ and K₁, CS is the radical axis of K₃ and K₂, and the perpendicular to AC at B is the radical axis of K₁ and K₂, 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 n², so we must have nr + ns ≤ n² and hence r + s ≤ n.

Conversely, suppose r + s ≤ n. Label the women W₁, W₂, ... , W_n and the men M₁, M₂, ... , M_n. Let woman W_i like men M_i+k for k = 0, 1, 2, ... , r-1, and let man M_i like women W_i+k for k = 1, 2, ... , s (we use the cyclic subscript convention, so W_n+1 means W₁ 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 S_n 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 S₅. We call m and n compatible if S_m ∩ S_n 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 = D^mb = Tⁿc, then we can find d such that b = Tⁿd and c = D^md. 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 = Tⁿc, so c is odd. Hence we can find d such that c = Dd. Then Db = DTⁿd, so b = Tⁿd, and the result is true for m = 1.

Suppose it is true for m and that a = D^m+1b = Tⁿc. Then Tⁿc is odd, so c is odd, so c = De. Hence D^mb = Tⁿe. So, by induction, we can find d such that b = Tⁿd, e = D^md. Then c = D^m+1d, b = Tⁿd, as required. So the result is true for m+1 and hence for all m.

It follows that if a = D^rT^sb = D^mTⁿc, then b and c can both be obtained from some d. (wlog r ≥ m, so D^r-mT^sb = Tⁿc. If s ≥ n, then we are home since c = D^r-mT^s-nb, if not then D^r-mb = T^n-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 = D^rT^sm for some r,s and so the numbers which can lead to n are just D^aT^bm 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 ∈ S₂₀₀₃ ∩ S_n, then 2003 and n can both be obtained from some d. Working backwards, we find that 2003 = D²T 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 = D²166, 1001 = DT 166, 1335 = D³166, 1502 = T²166 (the others are all ≥ 2003).