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 a_i, where a₁ = m, and a_k+1 is the residue of a_k² mod n (for k = 1, 2, ... , 2000). Then put f(n,m) = a₁ - a₂ + a₃ - a₄ + a₅ - ... + a₂₀₀₁. 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·10^k for k = 0, 2, ... , 6. So if this is a multiple of 7, then so is 4·10^k. But it obviously is not.

In the middle case we must have 10^a + 10^b + 10^c + 10^d = 0 mod 7 for some distinct a, b, c, d in {0, 1, 2, 3, 4, 5, 6}. We have 10^a = 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 = CM² = DM² = 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 = 180^o-3α, so ∠ABN = 180^o-2α. But ABNC is a parallelogram, so ∠DCN = 180^o-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; ...
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; ...

Similarly, for n = 10k + 5, we can take the first 2k+1 columns below to give the coins excluded from each box.

A: 1,  8, 15; 16, 25; 26, 35; ...
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; ...

For example, for n = 15, we take
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).