11th Iberoamerican Mathematical Olympiad Problems 1996

A1.  Find the smallest positive integer n so that a cube with side n can be divided into 1996 cubes each with side a positive integer.

A2.  M is the midpoint of the median AD of the triangle ABC. The ray BM meets AC at N. Show that AB is tangent to the circumcircle of NBC iff BM/MN = (BC/BN)².

A3.  n = k² - k + 1, where k is a prime plus one. Show that we can color some squares of an n x n board black so that each row and column has exactly k black squares, but there is no rectangle with sides parallel to the sides of the board which has its four corner squares black.

B1.  n > 2 is an integer. Consider the pairs (a, b) of relatively prime positive integers, such that a < b ≤ n and a + b > n. Show that the sum of 1/ab taken over all such pairs is 1/2.

B2.  An equilateral triangle of side n is divided into n² equilateral triangles of side 1 by lines parallel to the sides. Initially, all the sides of all the small triangles are painted blue. Three coins A, B, C are placed at vertices of the small triangles. Each coin in turn is moved a distance 1 along a blue side to an adjacent vertex. The side it moves along is painted red, so once a coin has moved along a side, the side cannot be used again. More than one coin is allowed to occupy the same vertex. The coins are moved repeatedly in the order A, B, C, A, B, C, ... . Show that it is possible to paint all the sides red in this way.

B3.  A₁, A₂, ... , A_n are points in the plane. A non-zero real number k_i is assigned to each point, so that the square of the distance between A_i and A_j (for i ≠ j) is k_i + k_j. Show that n is at most 4 and that if n = 4, then 1/k₁ + 1/k₂ + 1/k₃ + 1/k₄ = 0.

Solutions

Problem A1

Find the smallest positive integer n so that a cube with side n can be divided into 1996 cubes each with side a positive integer.

Solution

Answer: 13.

Divide all the cubes into unit cubes. Then the 1996 cubes must each contain at least one unit cube, so the large cube contains at least 1996 unit cubes. But 12³ = 1728 < 1996 < 2197 = 13³, so it is certainly not possible for n < 13.

It can be achieved with 13 by 1.5³ + 11.2³ + 1984.1³ = 13³ (actually packing the cubes together to form a 13 x 13 x 13 cube is trivial since there are so many unit cubes).

Problem 2

M is the midpoint of the median AD of the triangle ABC. The ray BM meets AC at N. Show that AB is tangent to the circumcircle of NBC iff BM/BN = (BC/BN)².

Solution

Applying Menelaus to the triangle ADC, we have (AM/MD)(BD/DC)(CN/NA) = 1, so (CN/NA) = 2. Hence AN/AC = 1/3. Applying Menelaus to the triangle BNC, we have (BM/MN)(AN/AC)(CD/DB) = 1, so BM/MN = 3. That is true irrespective of whether AB is tangent to the circle NBC.

If AB is tangent, then AB² = AN.AC = 1/3 AC². Also angle ABN = angle BCN, so triangles ANB and ABC are similar. Hence BC/BN = AC/AB. Hence (BC/BN)² = 3 = BM/BN.

Conversely, if (BC/BN)² = BM/BN, then (BC/BN)² = 3.

Now applying the cosine formula to AMN and AMB and using cos AMN + cos AMB = 0, we have (3AN² - 3AM² - 3MN²) + (AB² - AM² - BM²) = 0, so AB² + AC²/3 = AD² + 3/4 BN². Similarly from triangles ADC and ADB we get AB² + AC² = 2AD² + BC²/2. So using BN² = BC²/3 we get 2AB² + 2/3 AC² = AB² + AC² and hence (AC/AB)² = 3 = (BC/BN)². So AC/AB = BC/BN. Note that is not enough to conclude that triangles ABC and BNC are similar, because the common angle C is not between AC and AB. However, we have AN/AB = (1/3) AC/AB = AB/AC, so AB² = AN.AC, so AB is tangent to the circle NBC.

Problem A3

n = k² - k + 1, where k is a prime plus one. Show that we can color some squares of an n x n board black so that each row and column has exactly k black squares, but there is no rectangle with sides parallel to the sides of the board which has its four corner squares black.

Solution

We can regard the rows as lines and the columns as points. Black squares denote incidence. So line 3 contains point 4 iff square (3, 4) is black. The condition about rectangles then means that there is at most one line through two distinct points.

Suppose we take the points to be (a, b, c), where a, b, c are residues mod p, not all zero, and the coordinates are homogeneous, so that we regard (a, b, c), (2a, 2b, 2c), ... , ( (p-1)a, (p-1)b, (p-1)c ) as the same point. That gives (p³ - 1)/(p-1) = p² + p + 1 points, which is the correct number.

We can take lines to be lx + my + nz = 0, where the point is (x, y, z). In other words, the lines are also triples (l, m, n), with l, m, n residues mod p, not all zero and (l, m, n), (2l, 2m, 2n), ... , ( (p-1)l, (p-1)m, (p-1)n ) representing the same line.

One way of writing the points is p² of the form (a, b, 1), p of the form (a, 1, 0) and lastly (1, 0, 0). Similarly for the lines. We must show that (1) each point is on p+1 lines (so each column has p+1 black squares), (2) each line has p+1 points (so each row has p+1 black squares, (3) two lines meet in just one point (so no rectangles).

(1): Consider the point P (a, b, 1) with a non-zero. Then for any m, there is a unique l such that la + mb + 1.1 = 0, so there are p lines of the form (l, m, 1) which contain P. Similarly, there is a unique l such that la + 1b + 0.1 = 0, so one line of the form (l, 1, 0) contains P. The line (1, 0, 0) does not contain P. So P lies on just p+1 lines. Similarly for (a, b, 1) with b non-zero. The point (0, 0, 1) does not lie on any lines (l, m,, 1), but lies on (l, 1, 0) and (1, 0, 0), so again it lies on p+1 lines.

Consider the point Q (a, 1, 0) with a non-zero. For any m, there is a unique l such that Q lies on (l, m, 0). There is also a unique l such that Q lies on (l, 1, 0). Q does not lie on (1, 0, 0), so it lies on just p+1 lines. Similarly, the point (0, 1, 0) lies on the p lines (l, 0, 0) and on (1, 0, 0), but no others.

Finally, the point (1, 0, 0) lies on the p lines (0, m, 1), the line (0, 1, 0) and no others. Thus in all cases a point lies on just p+1 lines. The proof of (2) is identical.

(3). Suppose the lines are (l, m, n) and (L, M, N). If l and L are non-zero, then we can take the lines as (1, m', n') and (1, M', N'). So any point (x, y, z) on both satisfies x + m'y + n'z = 0 (*) and x + M'y + N'z = 0. Subtracting, (m' - M')y + (n' - N')z = 0. The coefficients cannot both be zero, since the lines are distinct. So the ratio y : z is fixed. Then (*) gives the ratio x : y. So the point is uniquely determined. If just one of l, L is non-zero, then we can take the lines as (0, m', n'), (1, M', N'). We cannot have both m' and n' zero, so the ratio y : z is determined, then the other line determines the ratio x : y. So again the point is uniquely determined. Finally, suppose l and L are both zero. Then since the lines are distinct y and z must both be zero. So the unique point on both lines is (1, 0, 0).

Comment. This is a poor question. If you have not met finite projective geometries before, then you are in real difficulties. If you have, the proof is just tiresome verification.

Problem B1

n > 2 is an integer. Consider the pairs (a, b) of relatively prime positive integers, such that a < b ≤ n and a + b > n. Show that the sum of 1/ab taken over all such pairs is 1/2.

Solution

Induction on n. It is obvious for n = 3, because the only pairs are (1, 3) and (2, 3), and 1/3 + 1/6 = 1/2. Now suppose it is true for n. As we move to n+1, we introduce the new pairs (a, n+1) with a relatively prime to n+1 and we lose the pairs (a, n+1-a) with a relatively prime to n+1-a and hence to n+1. So for each a relatively prime to n+1 and < (n+1)/2 we gain (a, n+1) and (n+1-a, n+1) and lose (a, n+1-a). But 1/a(n+1) + 1/( (n+1-a)(n+1) ) = ( n+1-a + a)/( a(n+1-a)(n+1) ) = 1/( a(n+1-a) ).

Problem B2

An equilateral triangle of side n is divided into n² equilateral triangles of side 1 by lines parallel to the sides. Initially, all the sides of all the small triangles are painted blue. Three coins A, B, C are placed at vertices of the small triangles. Each coin in turn is moved a distance 1 along a blue side to an adjacent vertex. The side it moves along is painted red, so once a coin has moved along a side, the side cannot be used again. More than one coin is allowed to occupy the same vertex. The coins are moved repeatedly in the order A, B, C, A, B, C, ... . Show that it is possible to paint all the sides red in this way.

Solution

We use induction. It is obvious for n = 1 and 2 - see diagram above. Note that A, B, C start and end at vertices of the large triangle.

Now assume that for n we can find a solution with A, B, C starting and ending at the vertices of the large triangle. Take n+1. We start with the paths shown which bring A, B, C to A', B', C' at the vertices of a triangle side n-1. Now by induction we can continue the paths so that we bring A, B, C, back to the vertices of that triangle after tracing out all its edges. Finally, note that for each of the points A', B', C' there is a path length 2 over untraced segments to a vertex of the large triangle. So we get a solution for n+1 and hence for all n.

Problem B3

A₁, A₂, ... , A_n are points in the plane. A non-zero real number k_i is assigned to each point, so that the square of the distance between A_i and A_j (for i ≠ j) is k_i + k_j. Show that n is at most 4 and that if n = 4, then 1/k₁ + 1/k₂ + 1/k₃ + 1/k₄ = 0.

Solution

Suppose we have four points A, B, C, D with associated numbers a, b, c, d. Then AB² = a + b, AC² = a + c, so AB² - AC² = b - c. Similarly, DB² - DC² = b - c, so AB² - AC² = DB² - DC². Let X be the foot of the perpendicular from A to BC, and Y the foot of the perpendicular from D to BC. Then AB² - AC² = (AX² + XB²) - (AX² + XC²) = XB² - XC². Similarly for D, so XB² - XC² = YB² - YC². Hence X = Y, so AD is perpendicular to BC. Similarly, BD is perpendicular to AC, and CD is perpendicular to AB. Hence D is the (unique) orthocenter of ABC. So n <= 4.

Suppose n = 4, so we have four points A, B, C, D with associated numbers a, b, c, d. We have AB² + AC² - BC² = (a + b) + (a + c) - (b + c) = 2a. But by the cosine formula it is also 2 AB AC cos BAC. Hence a = AB AC cos BAC. Similarly for A, B, D etc. Hence ab/cd = (AB AC cos BAC)(BA BD cos ABD)/( (CA.CD cos ACD)(DB DC cos BDC) ) = (AB²/CD²) (cos BAC/cos BDC) (cos ABD/cos ACD).

Take ABC to be acute with D inside. Then angle ABD = angle ACD ( = 90^o - angle BAC), and angle BDC = 90^o + angle ACD = 180^o - angle BAC. So cos BAC/cos BDC = -1. Thus ab/cd = - AB²/CD² = - (a + b)/(c + d). Hence ab(c + d) + cd(a + b) = 0, so 1/a + 1/b + 1/c + 1/d = 0.