[more...]
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. 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).
16th Mexican Mathematical Olympiad Problems 2002
16th Mexican Mathematical Olympiad Problems 2002
A1. The numbers 1 to 1024 are written one per square on a 32 x 32 board, so that the first row is 1, 2, ... , 32, the second row is 33, 34, ... , 64 and so on. Then the board is divided into four 16 x 16 boards and the position of these boards is moved round clockwise, so that
AB goes to DA
DC CB
then each of the 16 x 16 boards is divided into four equal 8 x 8 parts and each of these is moved around in the same way (within the 16 x 16 board). Then each of the 8 x 8 boards is divided into four 4 x 4 parts and these are moved around, then each 4 x 4 board is divided into 2 x 2 parts which are moved around, and finally the squares of each 2 x 2 part are moved around. What numbers end up on the main diagonal (from the top left to bottom right)?
A2. ABCD is a parallelogram. K is the circumcircle of ABD. The lines BC and CD meet K again at E and F. Show that the circumcenter of CEF lies on K.
A3. Does n2 have more divisors = 1 mod 4 or = 3 mod 4?
B1. A domino has two numbers (which may be equal) between 0 and 6, one at each end. The domino may be turned around. There is one domino of each type, so 28 in all. We want to form a chain in the usual way, so that adjacent dominos have the same number at the adjacent ends. Dominos can be added to the chain at either end. We want to form the chain so that after each domino has been added the total of all the numbers is odd. For example, we could place first the domino (3,4), total 3 + 4 = 7. Then (1,3), total 1 + 3 + 3 + 4 = 11, then (4,4), total 11 + 4 + 4 = 19. What is the largest number of dominos that can be placed in this way? How many maximum-length chains are there?
B2. A trio is a set of three distinct integers such that two of the numbers are divisors or multiples of the third. Which trio contained in {1, 2, ... , 2002} has the largest possible sum? Find all trios with the maximum sum.
B3. ABCD is a quadrilateral with ∠A = ∠B = 90o. M is the midpoint of AB and ∠CMD = 90o. K is the foot of the perpendicular from M to CD. AK meets BD at P, and BK meets AC at Q. Show that ∠AKB = 90o and KP/PA + KQ/QB = 1.
Solutions
Problem A1
The numbers 1 to 1024 are written one per square on a 32 x 32 board, so that the first row is 1, 2, ... , 32, the second row is 33, 34, ... , 64 and so on. Then the board is divided into four 16 x 16 boards and the position of these boards is moved round clockwise, so that
AB goes to DA
DC CB
then each of the 16 x 16 boards is divided into four equal 8 x 8 parts and each of these is moved around in the same way (within the 16 x 16 board). Then each of the 8 x 8 boards is divided into four 4 x 4 parts and these are moved around, then each 4 x 4 board is divided into 2 x 2 parts which are moved around, and finally the squares of each 2 x 2 part are moved around. What numbers end up on the main diagonal (from the top left to bottom right)? Answer
993, 962, ... , 63, 32 (originally the other main diagonal, from bottom to top)
Solution
We show by induction on n that for a 2n x 2n board we get the other main diagonal (OMD) from bottom to top. For n = 1 this is obvious. Suppose it is true for n. Now consider a 2n+1 x 2n+1 board. After the first move, the top left quadrant is the original bottom left quadrant which contains the bottom half of the OMD as its other main diagonal. Similarly, the bottom right quadrant is the original top right quadrant which contains the top half of the OMD as its other main diagonal. Hence, by induction, the subsequent moves give the OMD from bottom to top.
Problem A2
ABCD is a parallelogram. K is the circumcircle of ABD. The lines BC and CD meet K again at E and F. Show that the circumcenter of CEF lies on K.
Solution
Let O be the center of K. Let AO meet K again at G. We show that G is the circumcenter of CEF. Note that AD is parallel to BE, so AB = DE. Similarly, AB is parallel to DF, so AD = BF. Hence the arcs AE and AF are equal. Hence the arcs GE and GF are equal, so ∠AOE = 2∠AGE = ∠EGF. Hence triangles AOE and FGE are similar.
We have CD·CF = CB·CE, so CF/CE = CB/CD = DA/DE. Also ∠ADE = ∠DAB = ∠FCE. So triangles ADE and FCE are similar. Thus the figures ADEO and FCEG are similar. But O is the circumcenter of ADE, so G is the circumcenter of FCE.
Problem A3
Does n2 have more divisors = 1 mod 4 or = 3 mod 4?
Answer
= 1 mod 4
Solution
It is sufficient to prove the result for all odd n, because the odd divisors of n are the same as the odd divisors of n', where n' is the largest odd factor of n. So assume n odd. Induction on n. True for n = 1. Suppose p is a prime factor of n and that p2a is the highest power of p dividing n2. Let h be the number of divisors of n2/p2a which are 1 mod 4 and k the number which are 3 mod 4. By induction h > k. Let H be the number of divisors of n2 which are 1 mod 4 and K the number which are 3 mod 4. If p = 1 mod 4, then H = (2a+1)h, K = (2a+1)k, so H > K. If p = 3 mod 4, then there are a+1 powers of p dividing n2 which are 1 mod 4 (namely p0, p2, ... , p2a) and a powers of p which are 3 mod 4 (namely p1, p3, ... , p2a-1), so H = (a+1)h + ak = a(h+k) + h, K = ah + (a+1)k = a(h+k) + k, so H > K.
Thanks to Suat Namli
Problem B1
A domino has two numbers (which may be equal) between 0 and 6, one at each end. The domino may be turned around. There is one domino of each type, so 28 in all. We want to form a chain in the usual way, so that adjacent dominos have the same number at the adjacent ends. Dominos can be added to the chain at either end. We want to form the chain so that after each domino has been added the total of all the numbers is odd. For example, we could place first the domino (3,4), total 3 + 4 = 7. Then (1,3), total 1 + 3 + 3 + 4 = 11, then (4,4), total 11 + 4 + 4 = 19. What is the largest number of dominos that can be placed in this way? How many maximum-length chains are there?
Answer
16, 3456
Solution
The first domino put down must have an odd total, subsequent dominos must have an even total. One of the numbers of the first domino will be odd and the other even. So any domino put next to the odd number must be odd, odd. Similarly any domino put next to the even number must be even, even. There are 12 dominos with one odd and one even number, 6 with two odd numbers, and 10 with two even numbers. Thus there are 12 choices for the first domino.
Consider first the dominos added at the odd end. Suppose the odd number on the first domino is a. Let the other two odd numbers (in {1,3,5}) be b and c. We have two choices for the first non-double. It must be ab or ac. Ignoring doubles, the order is then determined. For example, after ab we must put bc, then ca. Now the aa can be put either in front of the ab or after the ca. There is only one position for each of the other two doubles. Thus we have 4 possible ways to add the 6 odd-odd dominos at the odd end.
Now consider the even end. Again we start by ignoring the doubles. There are 6 non-doubles: 02, 04, 06, 24, 26, 46. Each number not at one of the two ends of the subchain of even-even non-doubles must occur an even number of times. But we have four numbers each of which appears an odd number of times in the complete set of six. So we must exclude at least one even-even non-double. Suppose the even number on the odd-even domino is A and that the other even numbers are B, C, D. The first non-double in the even-even subchain can be AB, AC or AD. There are then two choices for the second. For example, if the first was AB, the second can be BC or BD. Suppose the second was BC. Then the remaining choices are AB, BC, CA, AD, DC or AB, BC, CA, AD, DB or AB, BC, CD, DA, AC. In each case we have two choices for AA (before AB or next to CA) and two choices for the other double which can go at an end, but only one choice for the other two doubles, so 4 ways of placing the doubles. Hence 3·2·3·4 = 72 possibilities in all for the even-even subchain.
Thus the maximum length is 1 + 6 + 9 = 16, and there are 12·4·72 = 3456 maximal length chains.
Problem B2
A trio is a set of three distinct integers such that two of the numbers are divisors or multiples of the third. Which trio contained in {1, 2, ... , 2002} has the largest possible sum? Find all trios with the maximum sum.
Answer
(a, 2002-a, 2002), where a = 1, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286.
Solution
Let the numbers be a < b < c. There are 3 possibilities: (1) a and b are divisors/multiples of c; (2) a and c are divisors/multiples of b, so a must divide b and b must divide c; (3) b and c are both divisors/multiples of a. In case (1) a and b must both divide c, so b ≤ c/2 and a ≤ c/3, so a + b + c ≤ 11c/6 < 4004. In case (2), a and b both divide c, so this is a special case of (1). In this case (3) b and c must both be multiples of a. Hence b ≤ c - a, so a + b + c ≤ 2c ≤ 4004.
We can achieve 4004 by, for example, (a,b,c) = (1,2001,2002). So 4004 is the maximum sum. Evidently it can only be achieved in case (3) and only by taking c = 2002, a + b = 2002, and a a divisor of 2002. There are 14 divisors of 2002 (apart from 2002 and 1001, which do not work, since a, b, c must be distinct), and each gives a solution. For example, (1,2001,2002), (2,2000,2002), (7,1995,2002).
15th Mexican Mathematical Olympiad Problems 2001
15th Mexican Mathematical Olympiad Problems 2001
A1. Find all 7-digit numbers which are multiples of 21 and which have each digit 3 or 7.
A2. Given some colored balls (at least three different colors) and at least three boxes. The balls are put into the boxes so that no box is empty and we cannot find three balls of different colors which are in three different boxes. Show that there is a box such that all the balls in all the other boxes have the same color.
A3. ABCD is a cyclic quadrilateral. M is the midpoint of CD. The diagonals meet at P. The circle through P which touches CD at M meets AC again at R and BD again at Q. The point S on BD is such that BS = DQ. The line through S parallel to AB meets AC at T. Show that AT = RC.
B1. For positive integers n, m define f(n,m) as follows. Write a list of 2001 numbers ai, where a1 = m, and ak+1 is the residue of ak2 mod n (for k = 1, 2, ... , 2000). Then put f(n,m) = a1 - a2 + a3 - a4 + a5 - ... + a2001. For which n ≥ 5 can we find m such that 2 ≤ m ≤ n/2 and f(m,n) > 0?
B2. ABC is a triangle with AB < AC and ∠A = 2 ∠C. D is the point on AC such that CD = AB. Let L be the line through B parallel to AC. Let L meet the external bisector of ∠A at M and the line through C parallel to AB at N. Show that MD = ND.
B3. A collector of rare coins has coins of denominations 1, 2, ... , n (several coins for each denomination). He wishes to put the coins into 5 boxes so that: (1) in each box there is at most one coin of each denomination; (2) each box has the same number of coins and the same denomination total; (3) any two boxes contain all the denominations; (4) no denomination is in all 5 boxes. For which n is this possible?
Solutions
Problem A1
Find all 7-digit numbers which are multiples of 21 and which have each digit 3 or 7.
Answer
3373377, 7373373, 7733733, 3733737, 7337337, 3777333
Solution
Considering the sum of the digits mod 3, we see that there must be seven 3s, four 3s and three 7s, or one 3 and six 7s. 7 does not divide 1111111, so the first case does not work.
The last case can be written as 7777777 - 4·10k for k = 0, 2, ... , 6. So if this is a multiple of 7, then so is 4·10k. But it obviously is not.
In the middle case we must have 10a + 10b + 10c + 10d = 0 mod 7 for some distinct a, b, c, d in {0, 1, 2, 3, 4, 5, 6}. We have 10a = 1, 3, 2, 6, 4, 5, 1 mod 7 for a = 0, 1, 2, 3, 4, 5, 6. So we have 14 = 6 + 5 + 2 + 1 = 6 + 4 + 3 + 1 = 5 + 4 + 3 + 2, 7 = 3 + 2 + 1 + 1, and hence the possible {a,b,c,d} are {2,3,5,6}, {0,2,3,5}, {0,1,3,4}, {1,3,4,6}, {1,2,4,5}, {0,1,2,6}.
Thanks to Suat Namli
Problem A3
ABCD is a cyclic quadrilateral. M is the midpoint of CD. The diagonals meet at P. The circle through P which touches CD at M meets AC again at R and BD again at Q. The point S on BD is such that BS = DQ. The line through S parallel to AB meets AC at T. Show that AT = RC.
Solution
CR·CP = CM2 = DM2 = DQ·DP = BS·DP, so CP/DP = BS/CR. But APB, CPC are similar, so CP/DP = BP/AP. Also ST is parallel to AB, so BP/AP = BS/AT. Hence AT = RC.
Problem B2
ABC is a triangle with AB < AC and ∠A = 2 ∠C. D is the point on AC such that CD = AB. Let L be the line through B parallel to AC. Let L meet the external bisector of ∠A at M and the line through C parallel to AB at N. Show that MD = ND.
Solution
∠BAM = ∠MAE = ∠AMB, so BM = AB. Hence MBCD is a parallelogram. So ∠BMD = α, where α = ∠C. ∠NBC = α, and ∠ABC = 180o-3α, so ∠ABN = 180o-2α. But ABNC is a parallelogram, so ∠DCN = 180o-2α. Now CN = AB = CD, so ∠CND = ∠CDN = α. But ABNC is a parallelogram, so ∠BNC = ∠BAC = 2α. Hence ∠DNM = α = ∠BMD. Hence DM = DN.
Problem B3
A collector of rare coins has coins of denominations 1, 2, ... , n (several coins for each denomination). He wishes to put the coins into 5 boxes so that: (1) in each box there is at most one coin of each denomination; (2) each box has the same number of coins and the same denomination total; (3) any two boxes contain all the denominations; (4) no denomination is in all 5 boxes. For which n is this possible?
Answer
n = 10, 15, 20, 25, ...
Solution
Suppose box A has n-k coins. Then all the boxes must have n-k coins, by (2). The sum of the k denominations not in box A must be the same as the corresponding sum for any other box, so k > 1. By (3), the k denominations not in box A must be in every other box. Similarly for the other boxes. So each box contains the 4k denominations that are excluded from one of the other boxes. So the total number of coins must be 5k. So n must be a multiple of 5 and at least 10. Now for n = 10k, we can take the first 2k columns below to give the coins excluded from each box.
A: 1, 10; 11, 20; 21, 30; 31, 40; ...Similarly, for n = 10k + 5, we can take the first 2k+1 columns below to give the coins excluded from each box.
B: 2, 9; 12, 19; 22, 29; 32, 39; ...
C: 3, 8; 13, 18; 23, 28; 33, 38; ...
D: 4, 7; 14, 17; 24, 27; 34, 37; ...
E: 5, 6; 15, 16; 25, 26; 35, 36; ...
A: 1, 8, 15; 16, 25; 26, 35; ...For example, for n = 15, we take
B: 2, 9, 13; 17, 24; 27, 34; ...
C: 3, 10, 11; 18, 23; 28, 33; ...
D: 4, 6, 14; 19, 22; 29, 32; ...
E: 5, 7, 12; 20, 21; 30, 31; ...
A = (2,3,4,5,6,7,9,10,11,12,13,14)
B = (1,3,4,5,6,7,8,10,11,12,14,15)
C = (1,2,4,5,6,7,8,9,12,13,14,15)
D = (1,2,3,5,7,8,9,10,11,12,13,15)
E = (1,2,3,4,6,8,9,10,11,13,14,15).
14th Mexican Mathematical Olympiad Problems 2000
14th Mexican Mathematical Olympiad Problems 2000
A1. A, B, C, D are circles such that A and B touch externally at P, B and C touch externally at Q, C and D touch externally at R, and D and A touch externally at S. A does not intersect C, and B does not intersect D. Show that PQRS is cyclic. If A and C have radius 2, B and D have radius 3, and the distance between the centers of A and C is 6, find area PQRS.
A2. A triangle is constructed like that below, but with 1, 2, 3, ... , 2000 as the first row. Each number is the sum of the two numbers immediately above. Find the number at the bottom of the triangle.
1 2 3 4 5
3 5 7 9
8 12 16
20 28
48
A3. If A is a set of positive integers, take the set A' to be all elements which can be written as ± a1 ± a2 ... ± an, where ai are distinct elements of A. Similarly, form A" from A'. What is the smallest set A such that A" contains all of 1, 2, 3, ... , 40?
B1. Given positive integers a, b (neither a multiple of 5) we construct a sequence as follows: a1 = 5, an+1 = a an + b. What is the largest number of primes that can be obtained before the first composite member of the sequence?
B2. Given an n x n board with squares colored alternately black and white like a chessboard. An allowed move is to take a rectangle of squares (with one side greater than one square, and both sides odd or both sides even) and change the color of each square in the rectangle. For which n is it possible to end up with all the squares the same color by a sequence of allowed moves?
B3. ABC is a triangle with ∠B > 90o. H is a point on the side AC such that AH = BH and BH is perpendicular to BC. D, E are the midpoints of AB, BC. The line through H parallel to AB meets DE at F. Show that ∠BCF = ∠ACD.
Solutions
Problem A2
A, B, C, D are circles such that A and B touch externally at P, B and C touch externally at Q, C and D touch externally at R, and D and A touch externally at S. A does not intersect C, and B does not intersect D. Show that PQRS is cyclic. If A and C have radius 2, B and D have radius 3, and the distance between the centers of A and C is 6, find area PQRS.
Answer 288/25
Solution
∠P = 180o - a - b, ∠Q = 180o - b - c, ∠R = 180o - c - d, ∠S = 180o - a - d. Hence ∠P + ∠R = ∠Q + ∠S. Hence ∠P + ∠R = 180o, so PQRS is cyclic.
We have EG = 6, EF = FG = GH = HE = 5. EP = EQ = GR = GS = 2. Hence area EPQ = area GRS = (4/25) area EFH = (2/25) area EFGH. Similarly, area FQR = area HPS = (9/25) area FEG = (9/50) area EFGH. Hence area PQRS = (12/25) area EFGH = (24/25) area EFG. If M is the midpoint of EG, then EMF is a 3,4,5 triangle, so MF = 4 and area EFG = 12. So area PQRS = 288/25.
Problem A2
A triangle is constructed like that below, but with 1, 2, 3, ... , 2000 as the first row. Each number is the sum of the two numbers immediately above. Find the number at the bottom of the triangle.
1 2 3 4 5
3 5 7 9
8 12 16
20 28
48
Answer
219982001
Solution
We claim that row n is 2n-2(n+1), 2n-2(n+1)+2n-1, 2n-2(n+1)+2·2n-1, 2n-2(n+1)+3·2n-1, ... . It is obvious for n = 2. Suppose it is true for n. Then row n+1 is 2n-1(n+2), 2n-1(n+2)+2n, 2n-1(n+2)+2·2n, 2n-1(n+2)+3·2n, ... and so it is true for n+1 and hence for all n.
In particular, row 2000 has first term (and only term if the first row has only 2000 terms) 219982001.
Thanks to Suat Namli
Problem A3
If A is a set of positive integers, take the set A' to be all elements which can be written as ± a1 ± a2 ... ± an, where ai are distinct elements of A. Similarly, form A" from A'. What is the smallest set A such that A" contains all of 1, 2, 3, ... , 40?
Answer
3 elements, eg {1,5,25}
Solution
A = {1,5,25} works. We get A' = {1,4,5,6,19,20,21,24,25,26,29,30,31}. Then A" includes all n ≤ 40.
Suppose A = {a,b} works with a < b. Then A' = {a,b-a,b,b+a}. Now A" has at most 81 elements - for each element x ∈ A' we can include +x, -x or 0 in the sum, a total of 81 possibilities. However, this includes the empty sum 0. Also for every positive k ∈ A", -k is also included (reversing each sign in the sum). So at best A" can include 40 positive elements. But a and b - (b-a) are the same, so A" must include less than 40 positive elements.
Problem B1
Given positive integers a, b (neither a multiple of 5) we construct a sequence as follows: a1 = 5, an+1 = a an + b. What is the largest number of primes that can be obtained before the first composite member of the sequence?
Answer
5
Solution
We find that the first few terms are a1 = 5, a2 = 5a+b, a3 = 5a2+ab+b, a4 = 5a3+a2b+ab+b, a5 = 5a4+a3b+a2b+ab+b = 5a4 + b(a4-1)/(a-1), a6 = 5a5+a4b+a3b+a2b+ab+b.
Now if a ≠ 1 mod 5, then a4 = 1 mod 5, so a5 = 0 mod 5. If a = 1 mod 5, then a6 = b(a4+a3+a2+a+1) = b(1+1+1+1+1) = 0 mod 5. So either a5 or a6 is a multiple of 5 (and obviously greater than 5, so composite). Thus we can get at most 5 initial primes.
We find that for a = 6, b = 7 we get 5, 37, 229, 1381, 8293, which are all prime (although checking the last two is a considerable slog, we have to test 8293 for prime divisors up to 89).
Problem B2
Given an n x n board with squares colored alternately black and white like a chessboard. An allowed move is to take a rectangle of squares (with one side greater than one square, and both sides odd or both sides even) and change the color of each square in the rectangle. For which n is it possible to end up with all the squares the same color by a sequence of allowed moves?
Answer
n ≠ 2
Solution
For n odd we can invert a 1 x n rectangle, so we invert alternate columns. That gives the first row black, the second white, the third black and so on. So by inverting alternate rows we get all squares the same color.
Now if we can do n, then we can do 2n, because we can divide the 2n x 2n board into 4 equal parts and do each part separately. We can do n = 4 by four 3 x 1 moves and two 2 x 2 moves as follows:
B W B W B W B B B W B B B B W W B B W W W W W W W W W W
W B W B W B W W W B W W W B W W B B W W W W W W W W W W
B W B W B W B B B W B B B W B B W W B B W W B B W W W W
W B W B W B W B B W B B B W B B W W B B W W B B W W W W
Hence we can do all n ≥ 3. n = 2 is obviously impossible. n = 1 is trivially possible (do nothing).
Problem B3
ABC is a triangle with ∠B > 90o. H is a point on the side AC such that AH = BH and BH is perpendicular to BC. D, E are the midpoints of AB, BC. The line through H parallel to AB meets DE at F. Show that ∠BCF = ∠ACD.
Solution 
Put ∠A = α. AD is parallel to HF, and DF is parallel to AH, so DFHA is a parallelogram. Hence FH = AD = DB, so FH is equal and parallel to BD, so BFHD is a parallelogram. Hence ∠FBD = ∠BDH = 90o (since HB = HA). Hence ∠FBC = ∠HBA = α.
BF = DH = AD tan α. We have ∠BHC = ∠HAB + ∠HBA = 2α, so BC/AC = BC/(AH+HC) = BC/(BH + HC) = HC sin 2α/(HC cos 2α + HC) = 2 sin α cos α/2 cos2α = tan α. So the triangles BFC and ADC are similar (∠FBC = ∠DAC and FB/BC = DA/AC). Hence ∠BCF = ∠ACD.
13th Mexican Mathematical Olympiad Problems 1999
13th Mexican Mathematical Olympiad Problems 1999
A1. 1999 cards are lying on a table. Each card has a red side and a black side and can be either side up. Two players play alternately. Each player can remove any number of cards showing the same color from the table or turn over any number of cards of the same color. The winner is the player who removes the last card. Does the first or second player have a winning strategy?
A2. Show that there is no arithmetic progression of 1999 distinct positive primes all less than 12345.
A3. P is a point inside the triangle ABC. D, E, F are the midpoints of AP, BP, CP. The lines BF, CE meet at L; the lines CD, AF meet at M; and the lines AE, BD meet at N. Show that area DNELFM = (1/3) area ABC. Show that DL, EM, FN are concurrent.
B1. 10 squares of a chessboard are chosen arbitrarily and the center of each chosen square is marked. The side of a square of the board is 1. Show that either two of the marked points are a distance ≤ √2 apart or that one of the marked points is a distance 1/2 from the edge of the board.
B2. ABCD has AB parallel to CD. The exterior bisectors of ∠B and ∠C meet at P, and the exterior bisectors of ∠A and ∠D meet at Q. Show that PQ is half the perimeter of ABCD.
B3. A polygon has each side integral and each pair of adjacent sides perpendicular (it is not necessarily convex). Show that if it can be covered by non-overlapping 2 x 1 dominos, then at least one of its sides has even length.
Solutions
Problem A1
1999 cards are lying on a table. Each card has a red side and a black side and can be either side up. Two players play alternately. Each player can remove any number of cards showing the same color from the table or turn over any number of cards of the same color. The winner is the player who removes the last card. Does the first or second player have a winning strategy?
Solution
We show that if an equal number of red and black cards are on the table, then the next player loses, and in all other cases the next player wins.
If there are an equal number, then whatever move the next player makes he must leave unequal numbers of red and black cards. In particular, he cannot immediately take the last card. On the other hand, if there are an unequal number, then the next player can take enough of the larger number to equalise. The game terminates because one player is always taking.
Since 1999 is odd, there must be unequal numbers, so the first player wins by always taking cards (not turning cards) and always leaving equal numbers of red and black cards.
Problem A2
Show that there is no arithmetic progression of 1999 distinct positive primes all less than 12345.
Solution
Let the progression be a, a+d, a+2d, ... , a+1998d. Note that a+ad is composite, so we must have a > 1998. 1999 + 6·1998 > 12345, so the difference d of the progression must be less than 6. It must be even (or alternate terms will be even). So d = 2 or 4. But a = 1 or 2 mod 3, so either a+4 or a+8 is a multiple of 3. Contradiction.
Problem A3
P is a point inside the triangle ABC. D, E, F are the midpoints of AP, BP, CP. The lines BF, CE meet at L; the lines CD, AF meet at M; and the lines AE, BD meet at N. Show that area DNELFM = (1/3) area ABC. Show that DL, EM, FN are concurrent.
Solution 
We use vectors. Take P to be the origin. Let the vectors PA, PB, PC be a, b, c. Then PD is a/2. L is the centroid of the triangle PBC, so PL is (2/3)(b+c)/2 = (b+c)/3. Take Q to be the point (a+b+c)/5. Then since (a+b+c)/5 = (2/5)a/2 + (3/5)(b+c)/3, Q lies on DL. Similarly, Q lies on EM and FN.
Note that area ANB = (1/3) area APB, area ADB = area BEA = (1/2) area APB. Hence area PDNE = (1 - 1/2 - 1/2 + 1/3) area APB = (1/3) area APB. Similarly for PELF and PFMD. Hence area DNELFM = (1/3) area ABC.
Problem B2
ABCD has AB parallel to CD. The exterior bisectors of ∠B and ∠C meet at P, and the exterior bisectors of ∠A and ∠D meet at Q. Show that PQ is half the perimeter of ABCD.
Solution
Let the internal bisectors at B and C meet at P'. Let PP' and BC meet at M. The exterior angle at B equals the interior angle at C, so BP is parallel to CP'. Similarly BP' is parallel to CP, so BPCP' is a parallelogram. But CP' and CP are perpendicular, and similarly BP and BP', so BPCP' is a rectangle. Hence M is the midpoint of BC and ∠DCP' = ∠MCP' = ∠MP'C, so MP is parallel to CD. Similarly, if N is the midpoint of AD, then QN is parallel to BC, and so P and Q both lie on MN.
But MN = (AB+CD)/2. Since ∠BPC = 90o and M is the midpoint of BC, M is the the circumcenter of BCP and so MP = BC/2. Similarly, NQ = AD/2. Hence PQ = perimeter/2.
12th Mexican Mathematical Olympiad Problems 1998
12th Mexican Mathematical Olympiad Problems 1998
A1. Given a positive integer we can take the sum of the squares of its digits. If repeating this operation a finite number of times gives 1 we call the number tame. Show that there are infinitely many pairs (n, n+1) of consecutive tame integers.
A2. The lines L and L' meet at A. P is a fixed point on L. A variable circle touches L at P and meets L' at Q and R. The bisector of ∠QPR meets the circle again at T. Find the locus of T as the circle varies.
A3. Each side and diagonal of an octagon is colored red or black. Show that there are at least 7 triangles whose vertices are vertices of the octagon and whose sides are the same color.
B1. Find all positive integers that can be written as 1/a1 + 2/a2 + ... + 9/a9, where ai are positive integers.
B2. AB, AC are the tangents from A to a circle. Q is a point on the segment AC. The line BQ meets the circle again at P. The line through Q parallel to AB meets BC at J. Show that PJ is parallel to AC iff BC2 = AC·QC.
B3. Given 5 points, no 4 in the same plane, how many planes can be equidistant from the points? (A plane is equidistant from the points if the perpendicular distance from each point to the plane is the same.)
Solutions
Problem A1
Given a positive integer we can take the sum of the squares of its digits. If repeating this operation a finite number of times gives 1 we call the number tame. Show that there are infinitely many pairs (n, n+1) of consecutive tame integers.
Solution
A little experimentation shows that we often get loops of numbers and chains leading into loops. There are some obvious tame numbers, such as 10, 13, and a few less obvious like 7, 10, 23. But the difficulty is finding any pair of consecutive tame integers. By brute force we can work up to 31 (→ 10 → 1) and 32 (→ 13 → 10 → 1). Now we get infinitely many by inserting arbitrarily many zeros between the 3 and the 1, to get the pairs 300...01, 300...02.
11th Mexican Mathematical Olympiad Problems 1997
11th Mexican Mathematical Olympiad Problems 1997
A1. Find all primes p such that 8p4 - 3003 is a (positive) prime.
A2. ABC is a triangle with centroid G. P, P' are points on the side BC, Q is a point on the side AC, R is a point on the side AB, such that AR/RB = BP/PC = CQ/QA = CP'/P'B. The lines AP' and QR meet at K. Show that P, G and K are collinear.
A3. Show that it is possible to place the numbers 1, 2, ... , 16 on the squares of a 4 x 4 board (one per square), so that the numbers on two squares which share a side differ by at most 4. Show that it is not possible to place them so that the difference is at most 3.
B1. 3 non-collinear points in space determine a unique plane, which contains the points. What is the smallest number of planes determined by 6 points in space if no three points are collinear and the points do not all lie in the same plane?
B2. ABC is a triangle. P, Q, R are points on the sides BC, CA, AB such that BQ, CR meet at A', CR, AP meet at B', AP, BQ meet at C' and we have AB' = B'C', BC' = C'A', CA' = A'B'. Find area PQR/area ABC.
B3. Show that we can represent 1 as 1/5 + 1/a1 + 1/a2 + ... + 1/an (for positive integers ai) in infinitely many different ways.
Solutions
Problem A1
Find all primes p such that 8p4 - 3003 is a (positive) prime.
Solution
p = 3 fails, p = 5 gives the prime 1997. If p > 5, then p4 = 1 mod 5, so 8p4 - 3003 = 0 mod 5 and is therefore composite.
Thanks to Suat Namli
Problem A3
Show that it is possible to place the numbers 1, 2, ... , 16 on the squares of a 4 x 4 board (one per square), so that the numbers on two squares which share a side differ by at most 4. Show that it is not possible to place them so that the difference is at most 3.
Solution
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
shows that a difference of ≤ 4 is possible. Now suppose a difference of ≤ 3 is possible. Let k be the smallest number of moves (each 1 square N, S, E or W) to get from 1 to 16. Evidently k must be at least 5 (because 1 + 4·3 < 16). But if k = 5, then every difference along the path from 1 to 16 must be exactly 3 and so the numbers along the path must be 1,4,7,10,13,16. However, there are at least two paths length k (we can go either way around the rectangle). Contradiction. So we must have k = 6 and hence 1 and 16 must be at opposite corners. Hence 2 cannot be 6 moves from 16. It must be at least 5 moves (2 + 4·3 < 16), so it must be adjacent to 1. Similarly, 3 must be adjacent to 1. Similarly 14 and 15 must be adjacent to 16. But now 2 and 15 are only 4 moves apart. Contradiction (2 + 4·3 < 15).
Problem B3
Show that we can represent 1 as 1/5 + 1/a1 + 1/a2 + ... + 1/an (for distinct positive integers ai) in infinitely many different ways.
Solution
We use 1/n by 1/n+1 + 1/(n2+n) repeatedly. We start with 1 = 1/2 + 1/3 + 1/6. Then 1/3 = 1/4 + 1/12 and 1/4 = 1/5 + 1/20, so we have 1 = 1/5 + 1/2 + 1/6 + 1/12 + 1/20. So we have found one representation of the required type. Now having found k, take the largest denominator N in any of the representations and replace 1/N by 1/(N+1) + 1/(N2+N). That gives another representation which must be different from any of the previous ones. Hence we can find infinitely many.
Thanks to Suat Namli
10th Mexican Mathematical Olympiad Problems 1996
10th Mexican Mathematical Olympiad Problems 1996
A1. ABCD is a quadrilateral. P and Q are points on the diagonal BD such that the points are in the order B, P, Q, D and BP = PQ = QD. The line AP meets BC at E, and the line Q meets CD at F. Show that ABCD is a parallelogram iff E and F are the midpoints of their sides.
A2. 64 tokens are numbered 1, 2, ... , 64. The tokens are arranged in a circle around 1996 lamps which are all turned off. Each minute the tokens are all moved. Token number n is moved n places clockwise. More than one token is allowed to occupy the same place. After each move we count the number of tokens which occupy the same place as token 1 and turn on that number of lamps. Where is token 1 when the last lamp is turned on?
A3. Show that it is not possible to cover a 6 x 6 board with 1 x 2 dominos so that each of the 10 lines of length 6 that form the board (but do not lie along its border) bisects at least one domino. But show that we can cover a 5 x 6 board with 1 x 2 dominos so that each of the 9 lines of length 5 or 6 that form the board (but do not lie along its border) bisects at least one domino.
B1. For which n can we arrange the numbers 1, 2, 3, ... , 16 in a 4 x 4 array so that the eight row and column sums are all distinct and all multiples of n?
B2. Arrange the numbers 1, 2, 3, ... , n2 in order in a n x n array (so that the first row is 1, 2, 3, ... , n, the second row is n+1, n+2, ... , 2n, and so on). For each path from 1 to n2 which consists entirely of steps to the right and steps downwards, find the sum of the numbers in the path. Let M be the largest such sum and m the smallest. Show that M - m is a cube and that we cannot get the sum 1996 for a square of any size.
B3. ABC is an acute-angled triangle with AB < BC < AC. The points A', B', C' are such that AA' is perpendicular to BC and has the same length. Similarly, BB' is perpendicular to AC and has the same length, and CC' is perpendicular to AB and has the same length. The orthocenter H of ABC and A' are on the same side of A. Similarly, H and B' are on the same side of B, and H and C' are on the same side of C. Also ∠AC'B = 90o. Show that A', B', C' are collinear.
Solutions
Problem A1
ABCD is a quadrilateral. P and Q are points on the diagonal BD such that the points are in the order B, P, Q, D and BP = PQ = QD. The line AP meets BC at E, and the line Q meets CD at F. Show that ABCD is a parallelogram iff E and F are the midpoints of their sides.
Solution
Let the diagonals meet at X. If ABCD is a parallelogram, then X is the midpoint of BD, and the midpoint of AC. Hence BX is a median of the triangle ABC and BP/PX = 2/3, so P is the centroid of ABC. Hence AE is also a median and so E is the midpoint of BC. Similarly, F is the midpoint of CD.
Now suppose E is the midpoint of BC, and F the midpoint of CD. Then EF is parallel to BC and half its length. Hence PQ = (2/3)EF, so the midpoint Y of PQ is the centroid of AEF. So if Z is the midpoint of EF, then A,Y,Z are collinear. Note that Y is also the midpoint of BD. But C,Z,Y are also collinear, so Y lies on AC. Now Y is the centroid of AEF, so AY = 2YZ. But EF=BD/2, so CZ = YZ. Hence AY = CY, so Y is also the midpoint of AC. Hence ABCD is a parallelogram.
Problem A2
64 tokens are numbered 1, 2, ... , 64. The tokens are arranged in a circle around 1996 lamps which are all turned off. Each minute the tokens are all moved. Token number n is moved n places clockwise. More than one token is allowed to occupy the same place. After each move we count the number of tokens which occupy the same place as token 1 and turn on that number of lamps. Where is token 1 when the last lamp is turned on?
Answer
32
Solution
Label the positions 1 to 64, so that initially token k is in position k. Token k gets to position m+1 after m moves iff (m+1)k = m+1 mod 64 or (k-1)(m+1) = 0 mod 64. So if k ≠ 1, then m+1 must be a power of 2. If 2n is the highest power of 2 dividing m+1, then k-1 must be divisible by 26-n.
So if m+1 = 2, 6, 10, 14, 18, ... , then only 33 shares a place with token 1. If m+1 = 4, 12, 20, 28, 36, ..., then 17, 33, 49 share a place with token 1. If m+1 = 8, 24, 40, 56, ..., then 9, 17, 25, 33, 41, 49, 57 share a place with token 1. If m+1 = 16, 48, 80, ..., then 15 numbers share a place with token 1. If m+1 = 32, 96, 160, ..., then 31 numbers share a place with token 1, and if m+1 = 64, 128, 192, ..., then 63 numbers (all of them) share a place with token 1.
So in the first 64 moves, 32·1 + 16·2 + 8·4 + 4·8 + 2·16 + 1·32 = 192 numbers share a place with 1. After 64 moves every token is back at its starting point. So after 10 such rounds 1920 bulbs are turned on and all the numbers are back at their starting points. Now when 1 reaches 31 on the next round we another 1+3+1+7+1+3+1+15+1+3+1+7+3+1 = 48 lights are turned on, for a total of 1968. When it moves to 32 the remaining 28 lights are turned on.
Problem A3
Show that it is not possible to cover a 6 x 6 board with 1 x 2 dominos so that each of the 10 lines of length 6 that form the board (but do not lie along its border) bisects at least one domino. But show that we can cover a 5 x 6 board with 1 x 2 dominos so that each of the 9 lines of length 5 or 6 that form the board (but do not lie along its border) bisects at least one domino.
Solution
Consider first the 6 x 6 board. Each of the 10 lines length 6 divides the board into two parts, each with an even number of squares. But if just one domino straddles a line, then there must be an odd number of squares each side of the line. Contradiction. So an even number of dominos must straddle each line. So if at least one domino straddles each line, then at least two do. But a domino can only straddle one line and there are < 2·10 dominos.
The diagram shows a possible solution for a 5 x 6 board.
Problem B1
For which n can we arrange the numbers 1, 2, 3, ... , 16 in a 4 x 4 array so that the eight row and column sums are all distinct and all multiples of n?
Answer
1,2,4
Solution
1+2+...+16 = 2317, so if the row sums are all multiples of n, then n must divide 2317. But if all the row and column sums are multiples of 17, then the largest is at least 8·17 and hence the numbers add up to more than 8·17. Contradiction. So n must be 1, 2, 4 or 8. If n = 8, then the largest row/column sum must be at least 64. But the largest possible row/column sum is 16+15+14+13 = 58 < 64. So n must be 1, 2 or 4. The example below shows that these are all possible.
1 8 3 4 16
5 6 7 2 20
9 10 11 14 44
13 16 15 12 56
28 40 36 32
Problem B2
Arrange the numbers 1, 2, 3, ... , n2 in order in a n x n array (so that the first row is 1, 2, 3, ... , n, the second row is n+1, n+2, ... , 2n, and so on). For each path from 1 to n2 which consists entirely of steps to the right and steps downwards, find the sum of the numbers in the path. Let M be the largest such sum and m the smallest. Show that M - m is a cube and that we cannot get the sum 1996 for a square of any size.
Solution
If we take any four numbers ABCD with A, B in the same row, C, D in the same row, A, D in the same column and B, C in the same column:
... A ... BThen B < D, so A + D + C > A + B + C. Hence the maximal path must be down the first column and then along the bottom row. Thus M = 1 + n+1 + 2n+1 + ... + n2-n+1 + n2-n+2 + ... + n2 = (3n3-4n2+5n-2)/2. Similarly, the minimal path must be along the first row and down the last column, so m = 1 + 2 +...+ n-1 + n(1 + 2 + ... + n) = (n3+2n2-n)/2. Hence M-m = (n-1)3.
...
... D ... C
We have m = 1905 for n = 15 and 2296 for n = 16, so for a path of length 1996 we must have n ≤ 15. Similarly M = 1781 for n = 11 and 2333 for n = 12, so for length 1996 we must have n ≥ 12. So we need n = 12, 13, 14 or 15.
It is easy to see that by a sequence of moves of the type:
A to ABwe can go from any path to the minimal path. But each move of this type reduces the total by n-1. So any path total must = (n3+2n2-n)/2 mod n-1. For n = 12 this gives 1002 mod 11 = 1 mod 11. But 1996 = 5 mod 11, so 12 does not work. For n = 13, it gives 1261 = 1 mod 12, but 1996 = 4 mod 12, so 13 does not work. For n = 14, it gives 1561 = 1 mod 13, but 1996 = 7 mod 13, so 14 does not work. For n = 15, it gives 1905 = 1 mod 14, but 1996 = 8 mod 14, so 15 does not work. Thus we cannot get a path length 1996.
BC C
9th Mexican Mathematical Olympiad Problems 1995
9th Mexican Mathematical Olympiad Problems 1995
A1. N students are seated at desks in an m x n array, where m, n ≥ 3. Each student shakes hands with the students who are adjacent horizontally, vertically or diagonally. If there are 1020 handshakes, what is N?
A2. 6 points in the plane have the property that 8 of the distances between them are 1. Show that three of the points form an equilateral triangle with side 1.
A3. A, B, C, D are consecutive vertices of a regular 7-gon. AL and AM are tangents to the circle center C radius CB. N is the point of intersection of AC and BD. Show that L, M, N are collinear.
B1. Find 26 elements of {1, 2, 3, ... , 40} such that the product of two of them is never a square. Show that one cannot find 27 such elements.
B2. ABCDE is a convex pentagon such that the triangles ABC, BCD, CDE, DEA and EAB have equal area. Show that (1/4) area ABCDE < area ABC < (1/3) area ABCDE.
B3. A 1 or 0 is placed on each square of a 4 x 4 board. One is allowed to change each symbol in a row, or change each symbol in a column, or change each symbol in a diagonal (there are 14 diagonals of lengths 1 to 4). For which arrangements can one make changes which end up with all 0s?
Solutions
Problem A1
N students are seated at desks in an m x n array, where m, n ≥ 3. Each student shakes hands with the students who are adjacent horizontally, vertically or diagonally. If there are 1020 handshakes, what is N?
Answer
280
Solution
Students in the corner shake hands 3 times, those on the sides 5 times and those in the middle 8 times. So the total number of handshakes is (4·3 + (2m-4+2n-4)5 + (m-2)(n-2)8)/2 = (12 + 10m + 10n - 40 + 8mn - 16m - 16n + 32)/2 = (16mn - 12m - 12n + 8)/4 = (4m - 3)(4n - 3)/4 - 1/4 = 1020, so (4m-3)(4n-3) = 4081 = 7·11·53. Now 7 = 3 mod 4, 11 = 3 mod 4 and 53 = 1 mod 4, so we must have 4m-3 = 77, 4n-3 = 53 (or vice versa) and hence N = mn = 20·14 = 280.
Problem A2
6 points in the plane have the property that 8 of the distances between them are 1. Show that three of the points form an equilateral triangle with side 1.
Solution
Suppose not. Call two points related if they are a distance 1 apart. If any point is related to 5 others, then none of the others can be related, so we only have 5 distances of 1. Contradiction.
Now if X and Y are any two points, then at most two points can be related to X and Y (for there are two isosceles triangles with base XY and equal sides 1, one on each side of XY). So if a point X is related to 4 others, then none of the 4 can be related to each other and the last point Y (not related to X) can be related to at most 2 of the points related to X. So we have at most 6 distances of 1. Contradiction.
Now if we have at most one point related to 3 others, then we have at most (1·3 + 5·2)/2 < 8 distances of 1. So there must be two points X and Y, each related to 3 others. Since there are only 6 points in all, X must be related to Y. So we have A and B related to X, and C and D related to Y (giving a total of 5 distances of 1 so far). Now A and B cannot be related (or ABX is equilateral with side 1), and similarly C and D cannot be related. X is related to A and Y, and C and D are related to Y, so at most one of C, D is related to A (otherwise we would have three points related to A and Y). Similarly, at most one of C, D is related to B. So we have at most 7 distances of 1. Contradiction.
Problem B1
Find 26 elements of {1, 2, 3, ... , 40} such that the product of two of them is never a square. Show that one cannot find 27 such elements.
Solution
We can include at most one of 1,22,32,42,52,62, at most one of 2,2·22, 2·32, 2·42, at most one of 3, 3·22, 3·32, and at most one of each of the pairs (5,20), (6,24), (7,28), (10,40). Thus we must exclude at least 5+3+2+4 = 14 numbers, so we cannot find 27 numbers.
On the other hand the set of 26 numbers 1, 11, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 33, 34, 35, 37, 38, 39, 40 works.
Problem B2
ABCDE is a convex pentagon such that the triangles ABC, BCD, CDE, DEA and EAB have equal area. Show that (1/4) area ABCDE < area ABC < (1/3) area ABCDE.
Solution
This is a watered down version of -->
Problem B3
A 1 or 0 is placed on each square of a 4 x 4 board. One is allowed to change each symbol in a row, or change each symbol in a column, or change each symbol in a diagonal (there are 14 diagonals of lengths 1 to 4). For which arrangements can one make changes which end up with all 0s?
Answer
any arrangement which has an even number of Xs equal to 0
Solution
Any change switches an even number of the 8 Xs. So if we start with an odd number of Xs as 0, we can never get them all 0. But suppose we start with an even number 0. For each of the 4 central squares, there is a diagonal that contains that central square and no others. So we can always get all the central squares 0. By a combination of border rows/columns and diagonals of length 2, we can then change each X to a 0 in turn except one (without affecting the four central squares). But the last X will not need changing, since there must always be an even number equal to 0. Finally, we can use diagonals length one to change the four corners to 0.
8th Mexican Mathematical Olympiad Problems 1994
8th Mexican Mathematical Olympiad Problems 1994
A1. The sequence 1, 2, 4, 5, 7, 9 ,10, 12, 14, 16, 17, ... is formed as follows. First we take one odd number, then two even numbers, then three odd numbers, then four even numbers, and so on. Find the number in the sequence which is closest to 1994.
A2. The 12 numbers on a clock face are rearranged. Show that we can still find three adjacent numbers whose sum is 21 or more.
A3. ABCD is a parallelogram. Take E on the line AB so that BE = BC and B lies between A and E. Let the line through C perpendicular to BD and the line through E perpendicular to AB meet at F. Show that ∠DAF = ∠BAF.
B1. A capricious mathematician writes a book with pages numbered from 2 to 400. The pages are to be read in the following order. Take the last unread page (400), then read (in the usual order) all pages which are not relatively prime to it and which have not been read before. Repeat until all pages are read. So, the order would be 2, 4, 5, ... , 400, 3, 7, 9, ... , 399, ... . What is the last page to be read?
B2. ABCD is a convex quadrilateral. Take the 12 points which are the feet of the altitudes in the triangles ABC, BCD, CDA, DAB. Show that at least one of these points must lie on the sides of ABCD.
B3. Show that we cannot tile a 10 x 10 board with 25 pieces of type A, or with 25 pieces of type B, or with 25 pieces of type C.
Solutions
Problem A1
The sequence 1, 2, 4, 5, 7, 9 ,10, 12, 14, 16, 17, ... is formed as follows. First we take one odd number, then two even numbers, then three odd numbers, then four even numbers, and so on. Find the number in the sequence which is closest to 1994.
Answer 1993 and 1995
Solution
In the first 1 + 2 + ... + (n+1) numbers we have n gaps of 1, the other gaps are all 2. Now 1 + 2 + ... + 44 = 990, so in the first 990 numbers we have 43 gaps of 1, so the 990th number is 1 + 2·989 - 43 = 1936. The next number is 1937 and we then have 44 more odd numbers which takes us past 1994. So we get 1993 and 1995 but not 1994.
Problem A2
The 12 numbers on a clock face are rearranged. Show that we can still find three adjacent numbers whose sum is 21 or more.
Solution
Suppose it is possible to arrange them so that each three adjacent numbers have sum ≤ 20. If ABCD are adjacent numbers and A + B + C = 20, then we cannot have B + C + D = 20, because A ≠ D. There are 12 sets of three adjacent numbers. The total of all 12 sets is just 3(1 + 2 + ... + 12). But at most 6 can have sum 20, and the other 6 can have sum at most 19. So the sum of all 12 sets is at most 6·39 = 3(1 + 2 +... + 12). Thus 6 sets must have sum 20 and 6 sets must have sum 19. So suppose we have ABCDEFG ... with A + B + C = 20. Then B + C + D = D + E + F = 19, and C + D + E = E + F + G = 20. So D = A - 1, and G = D + 1 = A. Contradiction.
Problem B1
A capricious mathematician writes a book with pages numbered from 2 to 400. The pages are to be read in the following order. Take the last unread page (400), then read (in the usual order) all pages which are not relatively prime to it and which have not been read before. Repeat until all pages are read. So, the order would be 2, 4, 5, ... , 400, 3, 7, 9, ... , 399, ... . What is the last page to be read?
Answer
37
Solution
First read multiples of 2 and 5 (up to 400). Then since 399 = 3·7·19, read remaining multiples of 3, 7 and 19 up to 399. Then read 397 (a prime). Then read remaining multiples of 17 and 23 up to 391 (=17·23). Now all primes up to 23 have been covered except 11 and 13. Now the largest non-prime number not yet read must be divisible by 11 or 13 (since all multiples of smaller primes have already been read and 292 > 400), so the candidates are 377 = 13·29 and 341 = 11·31. So we keep reading primes until we get down to 377 and then read all remaining multiples of 13. We then read primes until we get down to 341, and then read all remaining multiples of 11. At this point the only remaining numbers are primes > 31. So we read them in reverse order, the last being 37.
Problem B2
ABCD is a convex quadrilateral. Take the 12 points which are the feet of the altitudes in the triangles ABC, BCD, CDA, DAB. Show that at least one of these points must lie on the sides of ABCD.
Solution
One of the feet of the altitudes of ABC lies on AB or BC unless ∠B is obtuse. Similarly for the other triangles. But the angles add to 360o, so they cannot all be obtuse.
Problem B3
Show that we cannot tile a 10 x 10 board with 25 pieces of type A, or with 25 pieces of type B, or with 25 pieces of type C.
Solution
Consider type A. The yellow piece must go into a corner. But then the only way to cover A is with the blue piece. Now the only way to cover B is with a translate of the blue piece, and so on. We can never round off at the next corner.
Color the board alternately black and white like a chessboard. Then type B pieces cover either 1 or 3 black squares. Suppose there are k type B pieces covering 1 black square, then there are 25-k covering 3 black squares, so we must have k + 75 - 3k = 50, or k = 25/2 which does not work.
Color the squares with four colors A, B, C, D in the usual pattern:
A B C D A B C D A B
B C D A B C D A B C
C D A B C D A B C D
D A B C D A B C D A
...
A B C D A B C D A B
B C D A B C D A B C
Now any type C piece must cover equal numbers of A, B, C, D. But the 10 x 10 square has 25 A, 26 B, 25 C and 24 D, so the tiling is impossible.
7th Mexican Mathematical Olympiad Problems 1993
7th Mexican Mathematical Olympiad Problems 1993
A1. ABC is a triangle with ∠A = 90o. Take E such that the triangle AEC is outside ABC and AE = CE and ∠AEC = 90o. Similarly, take D so that ADB is outside ABC and similar to AEC. O is the midpoint of BC. Let the lines OD and EC meet at D', and the lines OE and BD meet at E'. Find area DED'E' in terms of the sides of ABC.
A2. Find all numbers between 100 and 999 which equal the sum of the cubes of their digits.
A3. Given a pentagon of area 1993 and 995 points inside the pentagon, let S be the set containing the vertices of the pentagon and the 995 points. Show that we can find three points of S which form a triangle of area ≤ 1.
B1. f(n,k) is defined by (1) f(n,0) = f(n,n) = 1 and (2) f(n,k) = f(n-1,k-1) + f(n-1,k) for 0 < k < n. How many times do we need to use (2) to find f(3991,1993)?
B2. OA, OB, OC are three chords of a circle. The circles with diameters OA, OB meet again at Z, the circles with diameters OB, OC meet again at X, and the circles with diameters OC, OA meet again at Y. Show that X, Y, Z are collinear.
B3. p is an odd prime. Show that p divides n(n+1)(n+2)(n+3) + 1 for some integer n iff p divides m2 - 5 for some integer m.
Solutions
Problem A2
Find all numbers between 100 and 999 which equal the sum of the cubes of their digits.
Answer
153, 407,
Solution
This seems to require one to look at a large number of cases. There are two basic approaches: to deal with each value of a in turn (for example a = 9, so 171 < b3+c3 < 271, so one of b,c is 5 or 6. If one is 5 etc); or to deal with each value of c in turn. The latter requires more cases but less thought:
The idea is that if we fix c and one other digit, then the last digit is fixed by the requirement that a3+b3+c3 = c mod 10. Thus, if c = 0 or 1, then the other two digits must be 1,9 giving 73x, or 2,8 giving 52x, or 3,7 giving 40x, or 4,6 giving 28x, or 5,5 giving 25x, none of which work.
If c = 2, then the other two digits must be 0,4 giving 72, or 1,7 giving 353, or 2,6 giving 232, or 3,3 giving 62, or 5,9 giving 862, or 8,8 giving 1032, none of which work.
If c = 3, then the other two digits must be 0,6 giving 243, or 1,5 giving 153, or 2,2 giving 43, or 3,9 giving 783, or 4,8 giving 603, or 7,7 giving 713. Only 153 works.
If c = 4, then 1,9 →794, 2,8 →584, 3,7 →464, 4,6 →344, 5,5 →314, none of which work.
If c = 5, then 1,9 →855, 2,8 → 645, 3,7 → 525, 4,6 → 405, 5,5 →375, none of which work.
If c = 6, then 1,9 → 946, 2,8 → 736, 3,7 → 616, 4,6 →496, 5,5 → 466, none of which work.
If c = 7, then 1,7 → 687, 2,6 → 567, 3,3 → 397, 4,0 → 407, 5,9 → 1197, 8,8 → 1367, and only 407 works.
If c = 8, then 0,6 → 728, 1,5 → 638, 2,2 → 528, 3,9 → 1268, 4,8 → 1088, 7,7 → 1198, none of which work.
If c = 9, then 1,9 and 2,8, and 3,7, and 4,6 give results which are too big and 5,5 → 979, which does not work.
Problem A3
Given a pentagon of area 1993 and 995 points inside the pentagon, let S be the set containing the vertices of the pentagon and the 995 points. Show that we can find three points of S which form a triangle of area ≤ 1.
Solution
If any three points are collinear, then we have a triangle of area nil. So assume no three points are collinear. We show that there are 1993 non-overlapping triangles. By drawing two diagonals we divide the pentagon into 3 non-overlapping triangles. Now take each of the inside points in turn. Each point P must lie inside one of the existing triangles ABC. So we can join P to A, B, C, thus increasing the number of triangles by 2. Repeating for each of the inside points gives a total of 3 + 2·995 = 1993 non-overlapping triangles. Hence at least one of these triangles must have area ≤ 1993/1993 = 1.
Thanks to Vikram Nayak
Problem B2
OA, OB, OC are three chords of a circle. The circles with diameters OA, OB meet again at Z, the circles with diameters OB, OC meet again at X, and the circles with diameters OC, OA meet again at Y. Show that X, Y, Z are collinear.
Solution
This is just the Simson line.
Note that X, Y, Z are the feet of the perpendiculars from O to BC, CA, AB (because ∠OXC = ∠OBX = 90o etc). Now OXCY is cyclic, so ∠OYX = ∠OCX. Similarly, OYZA is cyclic, so ∠OYZ = 180o - ∠OAB. But OABC is cyclic, so ∠OAB = ∠OCX. Hence ∠OYX + ∠OYZ = 180o, and so X,Y,Z are collinear.
The Simson line result is that the feet of the perpendiculars from K to the three sides of a triangle are collinear iff K lies on the circumcircle.
Problem B3
p is an odd prime. Show that p divides n(n+1)(n+2)(n+3) + 1 for some integer n iff p divides m2 - 5 for some integer m.
Solution
n(n+1)(n+2)(n+3) + 1 = (n2+3n+1)2, so if p divides n(n+1)(n+2)(n+3) + 1 then it must divide n2+3n+1 and hence 4(n2+3n+1) = (2n+3)2 - 5.
Conversely, suppose an odd prime p divides m2 - 5. Note that m cannot be 1, 2, 3. If m = 0, then we can take n = 1 (because p must be 5 which divides 4! + 1). Now if m is odd and ≥ 5, then we can write m = 2n+3 with n ≥ 1 and hence p divides n(n+1)(n+2)(n+3) + 1. If m is even, then p must also divide k2 - 5, where k = |p-m|, which is odd.
Thanks to Suat Namli
Previous Article
Subscribe to:
Posts (Atom)
