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 n² 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 = 90^o. M is the midpoint of AB and ∠CMD = 90^o. 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 = 90^o 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 2ⁿ x 2ⁿ 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 2ⁿ⁺¹ x 2ⁿ⁺¹ 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 n² 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 p^2a is the highest power of p dividing n². Let h be the number of divisors of n²/p^2a 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 n² 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 n² which are 1 mod 4 (namely p⁰, p², ... , p^2a) and a powers of p which are 3 mod 4 (namely p¹, p³, ... , p^2a-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).