15th Iberoamerican Mathematical Olympiad Problems 2000
A1. Label the vertices of a regular n-gon from 1 to n > 3. Draw all the diagonals. Show that if n is odd then we can label each side and diagonal with a number from 1 to n different from the labels of its endpoints so that at each vertex the sides and diagonals all have different labels.
A2. Two circles C and C' have centers O and O' and meet at M and N. The common tangent closer to M touches C at A and C' at B. The line through B perpendicular to AM meets the line OO' at D. BO'B' is a diameter of C'. Show that M, D and B' are collinear.
A3. Find all solutions to (m + 1)a = mb + 1 in integers greater than 1.
B1. Some terms are deleted from an infinite arithmetic progression 1, x, y, ... of real numbers to leave an infinite geometric progression 1, a, b, ... . Find all possible values of a.
B2. Given a pile of 2000 stones, two players take turns in taking stones from the pile. Each player must remove 1, 2, 3, 4, or 5 stones from the pile at each turn, but may not take the same number as his opponent took on his last move. The player who takes the last stone wins. Does the first or second player have a winning strategy?
B3. A convex hexagon is called a unit if it has four diagonals of length 1, whose endpoints include all the vertices of the hexagon. Show that there is a unit of area k for any 0 < k ≤ 1. What is the largest possible area for a unit?
Solutions
Problem A1
Label the vertices of a regular n-gon from 1 to n > 3. Draw all the diagonals. Show that if n is odd then we can label each side and diagonal with a number from 1 to n different from the labels of its endpoints so that at each vertex the sides and diagonals all have different labels. Solution
Labeling the diagonal/side between i and j as i+j (reduced if necessary mod n) almost works. The labels for all the lines at a given vertex will be different. But the line between i and n will have label i, the same as one endpoint. However, we are not using the label 2i for the lines from vertex i. So for the line between i and n we use 2i instead of i+n. The only points that need checking are (1) whether a line from i to n has a label different from n, and (2) whether all the lines at n have different labels. Both points are ok because n is odd.
Problem A2
Two circles C and C' have centers O and O' and meet at M and N. The common tangent closer to M touches C at A and C' at B. The line through B perpendicular to AM meets the line OO' at D. BO'B' is a diameter of C'. Show that M, D and B' are collinear.
Solution
A neat coordinate solution by Massaki Yamamoto (a competitor) is as follows.
Take AB as the x-axis and the perpendicular line through M as the y-axis. Choose the unit of length so that M has coordinates (0, 1). Let A be (-m, 0) and B be (n, 0). Then considering the right-angled triangle O'MK, where K is (n, 1) we find that O' is (n, (n2+1)/2 ). Similarly, O is (-m, (m2+1)/2 ) ).
The gradient of the lie AM is 1/m, so the gradient of the line BD is -m and hence its equation is mx + y = mn. The gradient of the line OO' is (n-m)/2, so its equation is 2y - x(n-m) = mn+1. These intersect at ( (mn-1)/(m+n), (mn2+m)/(m+n) ). B' is (n, n2+1). It is now easy to check that the lines MB' and MD both have gradient n, so M, D, B' are collinear.
This looks easy, but choosing the right coordinate system is critical.
Problem A3
Find all solutions to (m + 1)a = mb + 1 in integers greater than 1.
Answer
(m, a, b) = (2, 2, 3).
Solution
Thanks to José Nelson Ramirez
Taking equation mod m+1 we get (-1)b = -1, so b is odd. Hence we can divide the rhs by m+1 to get mb-1 - mb-2 + ... - m + 1. This has an odd number of terms. If m is odd, then each term is odd and so the total is odd, but (m+1)a-1 is even (note that a > 1). Contradicton, so m is even.
We have mb = (m+1)a - 1. Expanding the rhs by the binomial theorem, and using b > 1, we see that m must divide a. So a is even also. Put a = 2A, m = 2M. We can factorise (m+1)a - 1 as ( (m+1)A + 1) ( (m+1)A - 1). The two factors have difference 2, so their gcd divides 2, but both factors are even, so their gcd is exactly 2.
If M = 1 or a power of 2, then the smaller factor 3A - 1 must be 2, so A = 1 and we have 3A + 1 = 4, so (2M)b = 8. Hence M = 1 and b = 3 and we have the solution (m, a, b) = (2, 2, 3).
If M is not a power of 2, then Mb > 2b, so we must have the larger factor 2·Mb and the smaller factor 2b-1. But the larger factor is now > 2b+1, so the difference between the factors is at least 3·2b-1 > 2. Contradiction.
Problem B1
Some terms are deleted from an infinite arithmetic progression 1, x, y, ... of real numbers to leave an infinite geometric progression 1, a, b, ... . Find all possible values of a.
Solution
Answer: the positive integers.
If a is negative, then the terms in the GP are alternately positive and negative, whereas either all terms in the AP from a certain point on are positive or all terms from a certain point on are negative. So a cannot be negative. If a is zero, then all terms in the GP except the first are zero, but at most one term of the AP is zero, so a cannot be zero. Thus a must be positive, so the AP must have infinitely many positive terms and hence x ≥ 1.
Let d = x - 1, so all terms of the AP have the form 1+nd for some positive integer n. Suppose a = 1 + md, a2 = 1 + nd, then (1 + md)2 = 1 + nd, so d = (n - 2m)/m2, which is rational. Hence a is rational. Suppose a = b/c, where b and c are relatively prime positive integers and c > 1. Then the denominator of the nth term of the GP is cn, which becomes arbitrarily large as n increases. But if d = h/k, then all terms of the AP have denominator at most k. So we cannot have c > 1. So a must be a positive integer.
On the other hand, it is easy to see that any positive integer works. Take x = 2, then the AP includes all positive integers and hence includes any GP with positive integer terms.
Problem B2
Given a pile of 2000 stones, two players take turns in taking stones from the pile. Each player must remove 1, 2, 3, 4, or 5 stones from the pile at each turn, but may not take the same number as his opponent took on his last move. The player who takes the last stone wins. Does the first or second player have a winning strategy?
Solution
The first player has a winning strategy. He takes 4 on his first move leaving 7 mod 13 (2000 = 153.13 + 7 + 4). Now we claim that the first player can always leave: (1) 0 mod 13, (2) 3 mod 13 by taking away 3, (3) 5 mod 13 by taking away 5, or (4) 7 mod 13, and that the second player can never leave 0 mod 13.
Let us look at each of these in turn. If the first player leaves 0 mod 13, then the second player can take 3 and leave 10. In that case the first player takes 5 (a type (3) move). If the second player takes 1, 2, 4 or 5, leaving 12, 11, 9 or 8 mod 13, then the first player takes 5, 4, 2, 1 (respectively) and leaves 7 mod 13 (a type (4) move).
If the first player leaves 3 mod 13 by taking away 3, then the second player cannot leave 0 mod 13, because he cannot take 3 stones. If he takes 1, 2 leaving 2, 1 mod 13 respectively, then the first player takes 2, 1 leaving 0 mod 13 (a type (1) move). If the second player takes 4, 5 leaving 12, 11 mod 13, then the first player takes 5, 4 leaving 7 mod 13 (a type (4) move).
If the first player leaves 5 mod 13 by taking 5, then the second player cannot leave 0 mod 13, because he cannot take 5 stones. If he takes 1, 2, 3, 4 stones, leaving 4, 3, 2, 1 mod 13, then the first player takes 4, 3, 2, 1 stones leaving 0 mod 13 (a type (1) move).
Finally, if the first player leaves 7 mod 13, and the second player takes 1 stone, then the first player takes 3 stones leaving 3 mod 13 (a type (2) move). If the second player takes 2, 3, 4, or 5 stones leaving 5, 4, 3, 2 mod 13, then the first player takes 5, 4, 3, 2 stones leaving 0 mod 13 (a type (1) move).
So the second player can never leave 0 mod 13 and hence, in particular, can never take the last stone. But we have shown that the first player can always make a move of one of the four types, so can always move and hence must win (since after less than 2000 moves there will be no stones left).
Problem B3
A convex hexagon is called a unit if it has four diagonals of length 1, whose endpoints include all the vertices of the hexagon. Show that there is a unit of area k for any 0 < k ≤ 1. What is the largest possible area for a unit?
Solution
Answer: We can get arbitrarily close to (but not achieve) (3√3)/4 (approx 1.3) by:
To prove the first part, consider the diagram below. Take AB = AC = 1 and angle BAC = 2θ. Take DE = DF = 1 and take the points of intersection X and Y such that AX = DX = AY = DY = 2/3. It is easy to check that the area of the hexagon is sin 2θ. So by taking θ in the interval (0, π/4] we can get any area 0 < k ≤ 1.
It is easy to check that there are six possible configurations for the unit diagonals, as shown in the diagram below.
Consider case 1.
The area of the hexagon is area AEDC + area AFE + area BAC. The part of the segment BF that lies inside AEDC is wasted. The rest goes to provide height for the triangles on bases AE and AC. So area AFE + area BAC can be maximised by taking F close to A and ∠BAC as close to a right angle as possible, so that the height of the triangle BAC (on the base AC) is as large as possible. We can then get arbitrarily close to the area of:
We obviously make AEB a straight line. Now area ADE + area ADC = area ACE + area CDE. So if we regard every point except D as fixed, then we maximise the area by taking ∠EAD = ∠CAD, so that D is the maximum distance from CE. Thus a maximal configuration must have ∠AED = ∠CAD. Similarly, it must have ∠CAD = ∠CAB, so all three angles must be equal. That disposes of case 1.
In cases 2 and 6 we find by a similar (but more tedious argument) the same maximum, although in one case we have to use the argument at the end for the final optimisation. In the other cases the maximum is smaller.
However, all these details would take an already long solution way over length. Does anyone have a better approach?
No. 6 (second case) can be made arbitrarily close to the figure below (with AB = AC = BD = 1). To optimise it, suppose ∠ACB = θ. Area ABDC = area ABC + area BCD. If we fix θ, then BC is fixed, so to maximise area BCD we must take ∠CBD = 90o. But θ cannot be optimal unless also ∠CAD = 90o. We have BA = BD and hence ∠BAD = ∠BDA = 45o - θ/2. Hence 90o = ∠CAD = ∠BAC - ∠BAD = (180o - 2θ) - (45o - θ/2). Hence θ = 30o. So ∠ACD = ∠BDC = 60o and ∠CAB = ∠ABD = 120o. It is easy to check that this has area (3√3)/4.
Labels:
Iberoamerican Mathematical Olympiad
Previous Article
