9th Asian Pacific Mathematics Olympiad 1997 Problems

9th Asian Pacific Mathematics Olympiad 1997 Problems

A1.  Let T_n = 1 + 2 + ... + n = n(n+1)/2. Let S_n= 1/T₁ + 1/T₂ + ... + 1/T_n. Prove that 1/S₁ + 1/S₂ + ... + 1/S₁₉₉₆ > 1001.

A2.  Find an n in the range 100, 101, ... , 1997 such that n divides 2ⁿ + 2.

A3.  ABC is a triangle. The bisector of A meets the segment BC at X and the circumcircle at Y. Let r_A = AX/AY. Define r_B and r_C similarly. Prove that r_A/sin²A + r_B/sin²B + r_C/sin²C ≥ 3 with equality iff the triangle is equilateral.

A4.  P₁ and P₃ are fixed points. P₂ lies on the line perpendicular to P₁P₃ through P₃. The sequence P₄, P₅, P₆, ... is defined inductively as follows: P_n+1 is the foot of the perpendicular from P_n to P_n-1P_n-2. Show that the sequence converges to a point P (whose position depends on P₂). What is the locus of P as P₂ varies?

A5.  n people are seated in a circle. A total of nk coins are distributed amongst the people, but not necessarily equally. A move is the transfer of a single coin between two adjacent people. Find an algorithm for making the minimum number of moves which result in everyone ending up with the same number of coins?

Let T_n = 1 + 2 + ... + n = n(n+1)/2. Let S_n= 1/T₁ + 1/T₂ + ... + 1/T_n. Prove that 1/S₁ + 1/S₂ + ... + 1/S₁₉₉₆ > 1001.

Solution

1/T_m = 2(1/m - 1/(m+1) ). Hence S_n/2 = 1 - 1/(n+1). So 1/S_n = (1 + 1/n)/2. Hence 1/S₁ + 1/S₂ + ... + 1/S_n = 1996/2 + (1+ 1/2 + 1/3 + ... + 1/1996)/2.

Now 1 + 1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + (1/9 + ... + 1/16) + (1/17 + ... + 1/32) + (1/33 + ... + 1/64) + (1/65 + ... + 1/128) + (1/129 + ... + 1/256) + (1/257 + ... + 1/512) + (1/513 + ... + 1/1024) > 1 + 1/2 + 1/2 + ... + 1/2 = 6. So 1/S₁ + 1/S₂ + ... + 1/S_n = 1996/2 + 6/2 = 998 + 3 = 1001. 

Find an n in the range 100, 101, ... , 1997 such that n divides 2ⁿ + 2.

Solution

Answer: the only such number is 946.

We have 2^p-1 = 1 mod p for any prime p, so if we can find h in {1, 2, ... , p-2} for which 2^h = -2 mod p, then 2^k= -2 mod p for any h = k mod p. Thus we find that 2^k = -2 mod 5 for k = 3 mod 4, and 2^k = -2 mod 11 for k = 6 mod 10. So we might then hope that 5·11 = 3 mod 4 and = 6 mod 10. Unfortunately, it does not! But we try searching for more examples.

The simplest would be to look at pq. Suppose first that p and q are both odd, so that pq is odd. If k = h mod p-1, then we need h to be odd (otherwise pq would have to be even). So the first step is to get a list of primes p with 2^h = -2 mod p for some odd h < p. We always have 2^p-1 = 1 mod p, so we sometimes have 2^(p-1)/2 = -1 mod p and hence 2^(p+1)/2 = -2 mod p. If (p+1)/2 is to be odd then p =1 mod 4. So searching such primes we find 3 mod 5, 7 mod 13, 15 mod 29, 19 mod 37, 27 mod 53, 31 mod 61. We require pq to lie in the range 100-1997, so we check 5·29 (not = 3 mod 4), 5·37 (not = 3 mod 4), 5·53 (not = 3 mod 4), 5·61 (not = 3 mod 4), 13·29 (not = 7 mod 12), 13·37 (not = 7 mod 12), 13.53 (not = 7 mod 12), 13·61 (not = 7 mod 12), 29·37 (not = 15 mod 28), 29·53 (not = 15 mod 28), 29·61 (not = 15 mod 28), 37·53 (not = 19 mod 36). So that does not advance matters much!

2p will not work (at least with h = (p+1)/2) because we cannot have 2p = (p+1)/2 mod p-1. So we try looking at 2pq. This requires that p and q = 3 mod 4. So searching for suitable p we find 6 mod 11, 10 mod 19, 22 mod 43, 30 mod 59, 34 mod 67, 42 mod 83. So we look at 2·11·43 = 946, which works.

Proving that it is unique is harder. The easiest way is to use a computer to search (approx 5 min to write a Maple program or similar and a few seconds to run it). 

ABC is a triangle. The bisector of A meets the segment BC at X and the circumcircle at Y. Let r_A = AX/AY. Define r_B and r_C similarly. Prove that r_A/sin²A + r_B/sin²B + r_C/sin²C >= 3 with equality iff the triangle is equilateral.

Solution

AX/AB = sin B/sin AXB = sin B/sin(180 - B - A/2) =sin B/sin(B + A/2). Similarly, AB/AY = sin AYB/sin ABY = sin C/sin(B + CBY) = sin C/sin(B + A/2). So AX/AY = sin B sin C/sin²(B + A/2). Hence r_A/sin²A = s_A/sin²(B + A/2), where s_A = sin B sin C/sin²A. Similarly for r_B and r_C. Now s_As_Bs_C = 1, so the arithmetic/geometric mean result gives s_A + s_B + s_C ≥ 3. But 1/sin k ≥ 1 for any k, so r_A/sin²A + r_B/sin²B + r_C/sin²C ≥ 3.

A necessary condition for equality is that sin²(B + A/2) = sin²(B + A/2) = sin²(B + A/2) = 1 and hence A = B = C. But it is easily checked that this is also sufficient.

P₁ and P₃ are fixed points. P₂ lies on the line perpendicular to P₁P₃ through P₃. The sequence P₄, P₅, P₆, ... is defined inductively as follows: P_n+1 is the foot of the perpendicular from P_n to P_n-1P_n-2. Show that the sequence converges to a point P (whose position depends on P₂). What is the locus of P as P₂ varies?

Solution

P_nP_n+1P_n+2 lies inside P_n-1P_nP_n+1. So we have sequence of nested triangles whose size shrinks to zero. Each triangle is a closed set, so there is just one point P in the intersection of all the triangles and it is clear that the sequence P_n converges to it.

Obviously all the triangles P_nP_n+1P_n+2 are similar (but not necessarily with the vertices in that order). So P must lie in the same position relative to each triangle and we must be able to obtain one triangle from another by rotation and expansion about P. In particular, P₅P₄P₆ is similar (with the vertices in that order) to P₁P₂P₃, and P₄P₅ is parallel to P₁P₂, so the rotation to get one from the other must be through π and P must lie on P₁P₅. Similarly P₃P₄P₅ must be obtained from P₁P₂P₃ by rotation about P through π/2 and expansion. But this takes P₁P₅ into a perpendicular line through P₃. Hence P₁P is perpendicular to P₃P. Hence P lies on the circle diameter P₁P₃.

However, not all points on this circle are points of the locus. P₃P₅ = P₃P₄ cos P₁ = P₃P₁ sin P₁ cos P₂ = 1/2 P₃P₁ sin 2P₁, so we can obtain all values of P₃P₅ up to P₁P₃/2. [Of course, P₂, and hence P₅, can be on either side of P₃.]. Thus the locus is an arc XP₃Y of the circle with XP₃ = YP₃ and ∠XP₁Y = 2 tan^-11/2. If O is the midpoint of P₁P₃, then O is the center of the circle and ∠XOY = 4 tan^-11/2 (about 106^o).

n people are seated in a circle. A total of nk coins are distributed amongst the people, but not necessarily equally. A move is the transfer of a single coin between two adjacent people. Find an algorithm for making the minimum number of moves which result in everyone ending up with the same number of coins?

Solution

Label the people from 1 to n, with person i next to person i+1, and person n next to person 1. Let person i initially hold c_i coins. Let d_i = c_i - k.

It is not obvious how many moves are needed. Clearly at least 1/2 ∑ |d_i| are needed. But one may need more. For example, suppose the starting values of d_i are 0, 1, 0, -1, 0. Then one needs at least 2 moves, not 1.

Obviously ∑ d_i = 0, so not all d_i can be negative. Relabel if necessary so that d₁ ≥= 0. Now consider X = |d₁| + |d₁ + d₂| + |d₁ + d₂ + d₃| + ... + |d₁ + d₂ + ... + d_n-1|. Note first that X is zero iff all d_i are zero. Any move between i and i+1, except one between n and 1, changes X by 1, because only the term |d₁ + d₂ + ... + d_i| is affected. Thus if we do not make any moves between n and 1, then we need at least X moves to reach the desired final position (with all d_i zero).

Assume X > 1. We show how to find a move which reduces X by 1. This requires a little care to avoid specifying a move which might require a person with no coins to transfer one. We are assuming that d₁ ≥ 0. Take the first i for which d_i+1 < 0. There must be such an i, otherwise all d_i would be non-negative, but they sum to 0, so they would all have to be zero, contradicting X > 0. If d₁ + ... + d_i > 0, then we take the move to be a transfer from i to i+1. This will reduce |d₁ + ... + d_i| by 1 and leave the other terms in X unchanged, so it will reduce X by 1. If d₁ + ... + d_i is not strictly positive, then by the minimality of i we must have d₁ = d₂ = ... = d_i = 0. We know that d_i+1 < 0. Now find the first j > i+1 such that d_j ≥ 0. There must be such a j, otherwise we would have ∑ d_m < 0. We have d₁ + ... + d_j-1 < 0, so a transfer from j to j-1 will reduce |d₁ + ... + d_j-1| and hence reduce X. Finally note that the move we have chosen leaves d₁ ≥ 0. Thus we can repeat the process and reduce X to zero in X moves.

We have proved that this procedure minimises the number of moves if we accept the restriction that we do not make any transfers between 1 and n. Thus the full algorithm is: calculate the effect of the transfers from 1 to n and from n to 1 on X. If either of these transfers reduces X by more than 1, then take the move with the larger reduction; otherwise, find a move as above which reduces X by 1; repeat.

[more...]

8th Asian Pacific Mathematics Olympiad 1996 Problems

8th Asian Pacific Mathematics Olympiad 1996 Problems

A1.  ABCD is a fixed rhombus. P lies on AB and Q on BC, so that PQ is perpendicular to BD. Similarly P' lies on AD and Q' on CD, so that P'Q' is perpendicular to BD. The distance between PQ and P'Q' is more than BD/2. Show that the perimeter of the hexagon APQCQ'P' depends only on the distance between PQ and P'Q'.

A2.  Prove that (n+1)^mn^m ≥ (n+m)!/(n-m)! ≥ 2^mm! for all positive integers n, m with n ≥ m.

A3.  Given four concyclic points. For each subset of three points take the incenter. Show that the four incenters from a rectangle.

A4.  For which n in the range 1 to 1996 is it possible to divide n married couples into exactly 17 single sex groups, so that the size of any two groups differs by at most one.

A5.  A triangle has side lengths a, b, c. Prove that √(a + b - c) + √(b + c - a) + √(c + a - b) ≤ √a + √b + √c. When do you have equality?

ABCD is a fixed rhombus. P lies on AB and Q on BC, so that PQ is perpendicular to BD. Similarly P' lies on AD and Q' on CD, so that P'Q' is perpendicular to BD. The distance between PQ and P'Q' is more than BD/2. Show that the perimeter of the hexagon APQCQ'P' depends only on the distance between PQ and P'Q'.

Solution

BPQ and DQ'P' are similar. Let PQ meet BD at X and P'Q' meet BD at Y. XY is fixed, so BX + DY is fixed. Hence also, BP + DQ' and BQ + DP' and PQ + P'Q' are fixed. So PQ + P'Q' - BP - BQ - DP' - DQ' is fixed, so PQ + P'Q' + (AB - BP) + (BC - BQ) + (CD - DP') + (DA - DQ') is fixed, and that is the perimeter of the hexagon.

Prove that (n+1)^mn^m ≥ (n+m)!/(n-m)! ≥ 2^mm! for all positive integers n, m with n ≥ m.

Solution

For any integer k ≥ 1, we have (n + k)(n - k + 1) = n² + n - k² + k ≤ n(n + 1). Taking the product from k = 1 to m we get (n + m)!/(n - m)! ≤ (n + 1)^mn^m.

For k = 1, 2, ... , m, we have n ≥ k and hence n + k ≥ 2k. Taking the product from k = 1 to m, we get (n + m)!/(n - m)! ≥ 2^mm! .

Given four concyclic points. For each subset of three points take the incenter. Show that the four incenters from a rectangle.

Solution

Take the points as A, B, C, D in that order. Let I be the incenter of ABC. The ray CI bisects the angle ACB, so it passes through M, the midpoint of the arc AB. Now ∠MBI = ∠MBA + ∠IBA = ∠MCA + ∠IBA = (∠ACB + ∠ABC)/2 = 90^o - (∠CAB) /2 = 90^o - ∠CMB/2 = 90^o - ∠IMB/2. So the bisector of ∠IMB is perpendicular to IB. Hence MB = MI. Let J be the incenter of ABD. Then similarly MA = MJ. But MA = MB, so the four points A, B, I, J are concyclic (they lie on the circle center M). Hence ∠BIJ = 180^o - ∠BAJ = 180^o - ∠BAD/2.

Similarly, if K is the incenter of ADC, then ∠BJK = 180^o - ∠BDC/2. Hence ∠IJK = 360^o - ∠BIJ - ∠BJK = (180^o - ∠BIJ) + (180^o - ∠BJK) = (∠BAD + ∠BDC)/2 = 90^o. Similarly, the other angles of the incenter quadrilateral are 90^o, so it is a rectangle.

For which n in the range 1 to 1996 is it possible to divide n married couples into exactly 17 single sex groups, so that the size of any two groups differs by at most one.

Solution

Answer: 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 27, 28, 29, 30, 31, 32, 36, 37, 38, 39, 40, 45, 46, 47, 48, 54, 55, 56, 63, 64, 72.

If n = 17k, then the group size must be 2k. Hence no arrangement is possible, because one sex has at most 8 groups and 8.2k < n.

If 2n = 17k+h with 0 < h < 17, then the group size must be k or k+1. One sex has at most 8 groups, so 8(k+1) ≥ n. Hence 16k + 16 ≥ 17k + h, so 16 - h ≥ k (*). We also require that 9k ≤ n. Hence 18k < 2n = 17k + h, so k ≤ h (**). With (*) this implies that k ≤ 8. So n ≤ 75.

Each group has at least one person, so we certainly require n ≥ 9 and hence k ≥ 1. It is now easiest to enumerate. For k = 1, we can have h = 1, 3, ... 15, giving n = 9-16. For k = 2, we can have h = 2, 4, ... 14, giving n = 18-24. For k = 3, we can have h = 3, 5, ... 13, giving n = 27-32. For k = 4, we can have h = 4, 6, ... 12, giving n = 36-40. For k = 5 we can have h = 5, 7, 9, 11, giving n = 45-48. For k = 6, we can have h = 6, 8, 10, giving n = 54, 55, 56. For k = 7, we can have h = 7, 9, giving n = 63, 64. For k = 8, we can have h = 8, giving n = 72.

A triangle has side lengths a, b, c. Prove that √(a + b - c) + √(b + c - a) + √(c + a - b) ≤ √a + √b + √c. When do you have equality?

Solution

Let A² = b + c - a, B² = c + a - b, C² = a + b - c. Then A² + B² = 2c. Also A = B iff a = b. We have (A - B)² ≥ 0, with equality iff A = B. Hence A² + B² ≥ 2AB and so 2(A² + B²) ≥ (A + B)² or 4c ≥ (A + B)² or 2√c ≥ A + B, with equality iff A = B. Adding the two similar relations we get the desired inequality, with equality iff the triangle is equilateral.

[more...]

Notes for Fractions and Decimals

Notes for Fractions and Decimals

Decimals 

·        Addition & Subtraction:  Line up the decimal points, then do the calculation.

Example:   57.4 - 4.23           Solution:     57.40     (don't forget to add the extra zero!)

                                                                   -  4.23

                                                                      53.17

·        Multiplication:  First do the calculation ignoring the decimals.  Add up the number of decimal places in the original problem, and move over the answer's decimal point by that many places.

Example:   12.34 · 7.042

Solution:   1234 · 7042 is 8,689,828.  We move the decimal 5 places to get   86.89828

·        Division:  Make the divisor (the outside number) easier by moving the decimal place.

Example:   With 360 ÷ 0.009  we change the problem to 360,000÷9   (ans: 40,000)

Example:   With 5400 ÷ 6000  we change the problem to 5.4 ÷ 6   (ans: 0.9)

Read more:

• http://www.violympic.org/download/Fractions-Decimals-Notes-for-students.doc

[more...]

7th Asian Pacific Mathematics Olympiad 1995 Problems

7th Asian Pacific Mathematics Olympiad 1995 Problems

A1.  Find all real sequences x₁, x₂, ... , x₁₉₉₅ which satisfy 2√(x_n - n + 1) ≥ x_n+1 - n + 1 for n = 1, 2, ... , 1994, and 2√(x₁₉₉₅ - 1994) ≥ x₁ + 1.

A2.  Find the smallest n such that any sequence a₁, a₂, ... , a_n whose values are relatively prime square-free integers between 2 and 1995 must contain a prime. [An integer is square-free if it is not divisible by any square except 1.]

A3.  ABCD is a fixed cyclic quadrilateral with AB not parallel to CD. Find the locus of points P for which we can find circles through AB and CD touching at P.

A4.  Take a fixed point P inside a fixed circle. Take a pair of perpendicular chords AC, BD through P. Take Q to be one of the four points such that AQBP, BQCP, CQDP or DQAP is a rectangle. Find the locus of all possible Q for all possible such chords.

A5.  f is a function from the integers to {1, 2, 3, ... , n} such that f(A) and f(B) are unequal whenever A and B differ by 5, 7 or 12. What is the smallest possible n? 

Solution

A1. Find all real sequences x₁, x₂, ... , x₁₉₉₅ which satisfy 2√(x_n - n + 1) ≥ x_n+1 - n + 1 for n = 1, 2, ... , 1994, and 2√(x₁₉₉₅ - 1994) ≥ x₁ + 1.

Solution

Answer: the only such sequence is 1, 2, 3, ... , 1995.

Put x₁₉₉₅ = 1995 + k. We show by induction (moving downwards from 1995) that x_n ≥ n + k. For suppose x_n+1 ≥ n + k + 1, then 4(x_n - n + 1) ≥ (x_n+1- n + 1)² ≥ (k+2)² ≥ 4k + 4, so x_n ≥ n + k. So the result is true for all n ≥ 1. In particular, x₁ ≥ 1 + k. Hence 4(x₁₉₉₅ - 1994) = 4(1 + k) ≥ (2 + k)² = 4 + 4k + k², so k² ≤ 0, so k = 0.

Hence also x_n ≥ n for n = 1, 2, ... , 1994. But now if x_n = n + k, with k > 0, for some n < 1995, then the same argument shows that x₁ ≥ 1 + k and hence 4 = 4(x₁₉₉₅ - 1994) ≥ (x₁ + 1)² ≥ (2 + k)² = 4 + 4k + k² > 4. Contradiction. Hence x_n = n for all n ≤ 1995.

Find the smallest n such that any sequence a₁, a₂, ... , a_n whose values are relatively prime square-free integers between 2 and 1995 must contain a prime. [An integer is square-free if it is not divisible by any square except 1.]

Solution

Answer: n = 14.

We can exhibit a sequence with 13 terms which does not contain a prime: 2·101 = 202, 3·97 = 291, 5·89 = 445, 7·83 = 581, 11·79 = 869, 13·73 = 949, 17·71 = 1207, 19·67 = 1273, 23·61 = 1403, 29·59 = 1711, 31·53 = 1643, 37·47 = 1739, 41·43 = 1763. So certainly n ≥ 14.

If there is a sequence with n ≥ 14 not containing any primes, then since there are only 13 primes not exceeding 41, at least one member of the sequence must have at least two prime factors exceeding 41. Hence it must be at least 43·47 = 2021 which exceeds 1995. So n =14 is impossible.

ABCD is a fixed cyclic quadrilateral with AB not parallel to CD. Find the locus of points P for which we can find circles through AB and CD touching at P.

Solution

Answer: Let the lines AB and CD meet at X. Let R be the length of a tangent from X to the circle ABCD. The locus is the circle center X radius R. [Strictly you must exclude four points unless you allow the degenerate straight line circles.]

Let X be the intersection of the lines AB and CD. Let R be the length of a tangent from X to the circle ABCD. Let C₀ be the circle center X radius R. Take any point P on C₀. Then considering the original circle ABCD, we have that R² = XA·XB = XC·XD, and hence XP² = XA·XB = XC·XD.

If C₁ is the circle through C, D and P, then XC.XD = XP², so XP is tangent to the circle C₁. Similarly, the circle C₂ through A, B and P is tangent to XP. Hence C₁ and C₂ are tangent to each other at P. Note that if P is one of the 4 points on AB or CD and C₀, then this construction does not work unless we allow the degenerate straight line circles AB and CD.

So we have established that all (or all but 4) points of C₀ lie on the locus. But for any given circle through C, D, there are only two circles through A, B which touch it (this is clear if you consider how the circle through A, B changes as its center moves along the perpendicular bisector of AB), so there are at most 2 points on the locus lying on a given circle through C, D. But these are just the two points of intersection of the circle with C₀. So there are no points on the locus not on C₀. 

Take a fixed point P inside a fixed circle. Take a pair of perpendicular chords AC, BD through P. Take Q to be one of the four points such that ASCQ, ASDQ, BSCQ or BSDQ is a rectangle. Find the locus of all possible Q for all possible such chords.

Solution

Let O be the center of the fixed circle and let X be the center of the rectangle ASCQ. By the cosine rule we have OQ² = OX² + XQ² - 2·OX·XQ cos θ and OP² = OX² + XP² - 2·OX·XP cos(θ+π), where θ is the angle OXQ. But cos(θ+π) = -cos θ, so OQ² + OP²= 2OX² + 2XQ². But since X is the center of the rectangle XQ = XC and since X is the midpoint of AC, OX is perpendicular to AC and hence XO² + XC² = OC². So OQ² = 2OC² - OP². But this quantity is fixed, so Q must lie on the circle center O radius √(2R² - OP²), where R is the radius of the circle.

Conversely, it is easy to see that all points on this circle can be reached. For given a point Q on the circle radius √(2R² - OP²) let X be the midpoint of PQ. Then take the chord AC to have X as its midpoint.

f is a function from the integers to {1, 2, 3, ... , n} such that f(A) and f(B) are unequal whenever A and B differ by 5, 7 or 12. What is the smallest possible n?

Solution

Answer: n = 4.

Each pair of 0, 5, 12 differ by 5, 7 or 12, so f(0), f(5), f(12) must all be different, so n ≥ 3.

We can exhibit an f with n = 4. Define f(m) = 1 for m = 1, 3, 5, 7, 9, 11 (mod 24), f(m) = 2 for m = 2, 4, 6, 8, 10, 12 (mod 24), f(m) = 3 for m = 13, 15, 17, 19, 21, 23 (mod 24), f(m) = 4 for m = 14, 16, 18, 20, 22, 0 (mod 24).

[more...]

6th Asian Pacific Mathematics Olympiad 1994 Problems

6th Asian Pacific Mathematics Olympiad 1994 Problems

A1.  Find all real-valued functions f on the reals such that (1) f(1) = 1, (2) f(-1) = -1, (3) f(x) ≤ f(0) for 0 < x < 1, (4) f(x + y) ≥ f(x) + f(y) for all x, y, (5) f(x + y) ≤ f(x) + f(y) + 1 for all x, y.

A2.  ABC is a triangle and A, B, C are not collinear. Prove that the distance between the orthocenter and the circumcenter is less than three times the circumradius.

A3.  Find all positive integers n such that n = a² + b², where a and b are relatively prime positive integers, and every prime not exceeding √n divides ab.

A4.  Can you find infinitely many points in the plane such that the distance between any two is rational and no three are collinear?

A5.  Prove that for any n > 1 there is either a power of 10 with n digits in base 2 or a power of 10 with n digits in base 5, but not both.

Find all real-valued functions f on the reals such that (1) f(1) = 1, (2) f(-1) = -1, (3) f(x) ≤ f(0) for 0 < x < 1, (4) f(x + y) ≥ f(x) + f(y) for all x, y, (5) f(x + y) ≤ f(x) + f(y) + 1 for all x, y.

Solution

Answer: f(x) = [x].

f(x+1) >= f(x) + f(1) = f(x) + 1 by (4) and (1). But f(x) ≥ f(x+1) + f(-1) = f(x+1) - 1 by (4) and (2). Hence f(x+1) = f(x) + 1.

In particular, 1 = f(1) = f(0+1) = f(0) + 1, so f(0) = 0. Hence, by (3), f(x) ≤ 0 for 0 < x < 1. But, by (5), 1 = f(1) = f(x + 1-x) ≤ f(x) + f(1-x) + 1, so f(x) + f(1-x) ≥ 0. But if 0 < x < 1, then also 0 < 1-x < 1, so f(x) = f(1-x) = 0.

Thus we have established that f(x) = 0 for 0 ≤ x < 1, and f(x+1) = f(x) + 1. It follows that f(x) = [x] for all x.

ABC is a triangle and A, B, C are not collinear. Prove that the distance between the orthocenter and the circumcenter is less than three times the circumradius.

Solution

We use vectors. It is well-known that the circumcenter O, the centroid G and the orthocenter H lie on the Euler line and that OH = 3 OG. Hence taking vectors with origin O, OH = 3 OG = OA + OB + OC. Hence |OH| ≤ |OA| + |OB| + |OC| = 3 x circumradius. We could have equality only if ABC were collinear, but that is impossible, because ABC would not then be a triangle.

Find all positive integers n such that n = a² + b², where a and b are relatively prime positive integers, and every prime not exceeding √n divides ab.

Solution

Answer: 2 = 1² + 1², 5 = 1² + 2², 13 = 2² + 3².

The key is to use the fact that a and b are relatively prime. We show in fact that they must differ by 1 (or 0). Suppose first that a = b. Then since they are relatively prime they must both be 1. That gives the first answer above. So we may take a > b. Then (a - b)² < a² + b² = n, so if a - b is not 1, it must have a prime factor which divides ab. But then it must divide a or b and hence both. Contradiction. So a = b + 1.

Now (b - 1)² < b² < n, so any prime factor p of b - 1 must divide ab = b(b + 1). It cannot divide b (or it would divide b and b - 1 and hence 1), so it must divide b + 1 and hence must be 2. But if 4 divides b - 1, then 4 does not divide b(b - 1), so b - 1 must be 0, 1 or 2. But it is now easy to check the cases a, b = (4, 3), (3, 2), (2, 1).

Can you find infinitely many points in the plane such that the distance between any two is rational and no three are collinear?

Solution

Answer: yes.

Let θ = cos^-13/5. Take a circle center O radius 1 and a point X on the circle. Take P_n on the circle such that angle XOP_n = 2nθ. We establish (A) that the P_n are all distinct and (B) that the distances P_mP_n are all rational.

We establish first that we can express 2 cos nx as a polynomial of degree n in (2 cos x) with integer coefficients and leading coefficient 1. For example, 2 cos 2x = (2 cos x)² - 1, 2 cos 3x = (2 cos x)³ - 3 (2 cos x). We proceed by induction. Let the polynomial be p_n(2 cos x). We have that p₁(y) = y and p₂(y) = y² - 1. Suppose we have found p_m for m ≤ n. Now cos(n+1)x = cos nx cos x - sin nx sin x, and cos(n-1)x = cos nx cos x + sin nx sin x, so cos(n+1)x = 2 cos x cos nx - cos(n-1)x. Hence p_n+1(y) = y p_n(y) - p_n-1(y). Hence the result is also true for n+1.

It follows that (1) if cos x is rational, then so is cos nx, and (2) if cos x is rational, then x/π is irrational. To see (2), suppose that x/π = m/n, with m and n integers. Then nx is a multiple of π and hence cos nx = 0, so p_n(2 cos x) = 0. Now we may write p_n(y) = yⁿ + a^n-1y^n-1 + ... + a₀. Now if also cos x = r/s, with r and s relatively prime integers, then we have, p_n(2 cos x) = rⁿ + a_n-1s r^n-1 + ... + a₀sⁿ = 0. But now s divides all terms except the first. Contradiction.

Thus we cannot have cos mθ = cos nθ for any distinct integers m, n, for then θ/π would be rational as well as cos θ. So we have established (A).

We have also established that all cos nθ are rational. But since sin(n+1)x = sin nx cos x + cos nx sin x and sin θ = 4/5, it is a trivial induction that all sin nθ are also rational. Now P_mP_n = 2 |sin(m - n)θ|, so all the distances P_mP_n are rational, thus establishing (B).

Prove that for any n > 1 there is either a power of 10 with n digits in base 2 or a power of 10 with n digits in base 5, but not both.

Solution

10^k has n digits in base 5 iff 5^n-1 < 10^k < 5ⁿ. Similarly, 10^h has n digits in base 2 iff 2^n-1 < 10^h < 2ⁿ. So if we can find both 10^k with n digits in base 5 and 10^h with n digits in base 2, then, multiplying the two inequalities, we have 10^n-1 < 10^h+k < 10ⁿ, which is clearly impossible. This establishes the "but not both" part.

Let S be the set of all positive powers of 2 or 5. Order the members of S in the usual way and let a_n be the n-1th member of the set. We claim that if a_n = 2^k, then 10^k has n digits in base 5, and if a_n = 5^h, then 10^h has n digits in base 2. We use induction on n.

a₂ = 2¹, a₃ = 2², a₄ = 5¹, a₅ = 2³, ... . Thus the claim is certainly true for n = 2. Suppose it is true for n.

Note that 10^k has n digits in base 5 iff 5^n-k-1 < 2^k < 5^n-k. Similarly, 10^h has n digits in base 2 iff 2^n-h-1 < 5^h < 2^n-h. There are 3 cases. Case (1). a_n = 2^k and a_n+1 = 2^k+1. Hence 10^k+1 has n+1 digits in base 5. Case (2). a_n = 2^k and a_n+1 is a power of 5. Hence a_n+1 must be 5^n-k. Hence 2^k < 5^n-k < 2^k+1. Hence 2ⁿ < 10^n-k < 2ⁿ⁺¹. So 10^n-k has n+1 digits in base 2. Case (3). a_n = 5^h. Since there is always a power of 2 between two powers of 5, a_n+1 must be a power of 2. Hence it must be 2^n-h. So we have 5^h < 2^n-h < 5^h+1. So 5ⁿ < 10^n-h < 5ⁿ⁺¹ and hence 10^n-h has n+1 digits in base 5.

Jacob Tsimerman pointed out that the second part can be done in a similar way to the first - which is neater than the above:

If no power of 10 has n digits in base 2 or 5, then for some h, k: 10^h < 2^n-1 < 2ⁿ < 10^h+1 and 10^k < 5^n-1 < 5ⁿ < 10^k+1. Hence 10^h+k < 10^n-1 < 10ⁿ < 10^h+k+2. But there is only one power of 10 between h+k and h+k+2.

[more...]

5th Asian Pacific Mathematics Olympiad 1993 Problems

5th Asian Pacific Mathematics Olympiad 1993 Problems

A1.  A, B, C is a triangle. X, Y, Z lie on the sides BC, CA, AB respectively, so that AYZ and XYZ are equilateral. BY and CZ meet at K. Prove that YZ² = YK.YB.

A2.  How many different values are taken by the expression [x] + [2x] + [5x/3] + [3x]+ [4x] for real x in the range 0 ≤ x ≤ 100?

A3.  p(x) = (x + a) q(x) is a real polynomial of degree n. The largest absolute value of the coefficients of p(x) is h and the largest absolute value of the coefficients of q(x) is k. Prove that k ≤ hn.

A4.  Find all positive integers n for which xⁿ + (x+2)ⁿ + (2-x)ⁿ = 0 has an integral solution.

A5.  C is a 1993-gon of lattice points in the plane (not necessarily convex). Each side of C has no lattice points except the two vertices. Prove that at least one side contains a point (x, y) with 2x and 2y both odd integers.

A, B, C is a triangle. X, Y, Z lie on the sides BC, CA, AB respectively, so that AYZ and XYZ are equilateral. BY and CZ meet at K. Prove that YZ² = YK·YB.

Solution

Use vectors. Take A as the origin. Let AZ = b, AY = c. We may take the equilateral triangles to have side 1, so b² = c² = 1 and b.c = 1/2. Take AB to be k b. AX is b + c, so AC must be k/(k-1) c (then AX = 1/k (k b) + (1 - 1/k) ( k/(k-1) c), which shows that X lies on BC).

Hence AK = k/(k² - k + 1) (b + (k-1) c). Writing this as (k²-k)/(k²-k+1) c + 1/(k²-k+1) (k b) shows that it lies on BY and writing it as k/(k²-k+1) b + (k²-2k+1) ( k/(k-1) c) shows that it lies on CZ. Hence YK.YB = YK.YB= ( k/(k²-k+1) b - 1/(k²-k+1) c) . ( k b - c) = (k b - c)²/(k²-k+1) = 1 = YZ².

Thank to Achilleas Porfyriadis for the following geometric proof

 

BZX and XYC are similar (sides parallel), so BZ/ZX = XY/YC. But XYZ is equilateral, so BZ/ZY = ZY/YC. Also ∠BZY = ∠ZYC = 120^o, so BZY and ZYC are similar. Hence ∠ZBY = ∠YZC. Hence YZ is tangent to the circle ZBK. Hence YZ² = YK·YB

How many different values are taken by the expression [x] + [2x] + [5x/3] + [3x]+ [4x] for real x in the range 0 ≤ x ≤ 100?

Solution

Answer: 734.

Let f(x) = [x] + [2x] + [3x] + [4x] and g(x) = f(x) + [5x/3]. Since [y+n] = n + [y] for any integer n and real y, we have that f(x+1) = f(x) + 10. So for f it is sufficient to look at the half-open interval [0, 1). f is obviously monotonic increasing and its value jumps at x = 0, 1/4, 1/3, 1/2, 2/3, 3/4. Thus f(x) takes 6 different values on [0, 1).

g(x+3) = g(x), so for g we need to look at the half-open interval [0, 3). g jumps at the points at which f jumps plus 4 additional points: 3/5, 1 1/5, 1 4/5, 2 2/5. So on [0, 3), g(x) takes 3 x 6 + 4 = 22 different values. Hence on [0, 99), g(x) takes 33 x 22 = 726 different values. Then on [99, 100] it takes a further 6 + 1 + 1 (namely g(99), g(99 1/4), g(99 1/3), g(99 1/2), g(99 3/5), g(99 2/3), g(99 3/4), g(100) ). Thus in total g takes 726 + 8 = 734 different values. 

p(x) = (x + a) q(x) is a real polynomial of degree n. The largest absolute value of the coefficients of p(x) is h and the largest absolute value of the coefficients of q(x) is k. Prove that k ≤ hn.

Solution

Let p(x) = p₀ + p₁x + ... + p_nxⁿ, q(x) = q₀ + q₁x + ... + q_n-1x^n-1, so h = max |p_i|, k = max |q_i|.

If a = 0, then the result is trivial. So assume a is non-zero. We have p_n = q_n-1, p_n-1 = q_n-2 + aq_n-1, p_n-2 = q_n-3 + aq_n-2, ... , p₁ = q₀ + aq₁, p₀ = aq₀.

We consider two cases. Suppose first that |a| ≥ 1. Then we show by induction that |q_i| ≤ (i+1) h. We have q₀ = p₀/a, so |q₀| ≤ h, which establishes the result for i = 0. Suppose it is true for i. We have q_i+1 = (p_i+1 - q_i)/a, so |q_i+1| ≤ |p_i+1| + |q_i| ≤ h + (i+1)h = (i+2)h, so it is true for i+1. Hence it is true for all i < n. So k ≤ max(h, 2h, ... , nh) = nh.

The remaining possibility is 0 < |a| < 1. In this case we show by induction that |q_n-i| ≤ ih. We have q_n-1 = p_n, so |q_n-1| ≤ |p_n| ≤ h, which establishes the result for i = 1. Suppose it is true for i. We have q_n-i-1 = p_n-i - aq_n-i, so |q_{n-i-1n-i| + |qn-i| ≤ h + ih = (i+1)h, so it is true for i+1. Hence it is true for all 1 ≤ i ≤ n. Hence k ≤ max(h, 2h, ... , nh) = nh.}

Find all positive integers n for which xⁿ + (x+2)ⁿ + (2-x)ⁿ = 0 has an integral solution.

Solution

Answer: n = 1.

There are obviously no solutions for even n, because then all terms are non-negative and at least one is positive. x = -4 is a solution for n = 1. So suppose n is odd n and > 3.

If x is positive, then xⁿ + (x+2)ⁿ > (x+2)ⁿ > (x-2)ⁿ, so xⁿ + (x+2)ⁿ + (2-x)ⁿ > 0. Hence any solution x must be negative. Put x = -y. Clearly x = -1 is not a solution for any n, so if x = -y is a solution then (x+2) = -(y-2) ≤ 0 we have (y+2)ⁿ = yⁿ + (y-2)ⁿ. Now 4 = ( (y+2) - (y-2) ) divides (y+2)ⁿ - (y-2)ⁿ. Hence 2 divides y. Put y = 2z, then we have (z+1)ⁿ = zⁿ + (z-1)ⁿ. Now 2 divides (z+1)ⁿ - (z-1)ⁿ so 2 divides z, so z+1 and z-1 are both odd. But aⁿ - bⁿ = (a - b)(a^n-1n-2b + a^n-3b² + ... + b^n-1). If a and b are both odd, then each term in (a^n-1n-2b + a^n-3b² + ... + b^n-1) is odd and since n is odd there are an odd number of terms, so (a^n-1n-2b + a^n-3b² + ... + b^n-1) is odd. Hence, putting a=z+1, b=z-1, we see that (z+1)ⁿ - (z-1)ⁿ = 2(a^n-1n-2b + a^n-3b² + ... + b^n-1) is not divisible by 4. But it equals zⁿ with z even. Hence n must be 1.

C is a 1993-gon of lattice points in the plane (not necessarily convex). Each side of C has no lattice points except the two vertices. Prove that at least one side contains a point (x, y) with 2x and 2y both odd integers.

Solution

 

We consider the midpoint of each side. We say that a vertex (x, y) is pure if x and y have the same parity and impure if x and y have opposite parity. Since the total number of vertices is odd, there must be two adjacent pure vertices P and Q or two adjacent impure vertices P and Q. But in either case the midpoint of P and Q either has both coordinates integers, which we are told does not happen, or as both coordinates of the form an integer plus half, which therefore must occur.

[more...]

4th Asian Pacific Mathematics Olympiad 1992 Problems

4th Asian Pacific Mathematics Olympiad 1992 Problems

A1.  A triangle has sides a, b, c. Construct another triangle sides (-a + b + c)/2, (a - b + c)/2, (a + b - c)/2. For which triangles can this process be repeated arbitrarily many times?

A2.  Given a circle C centre O. A circle C' has centre X inside C and touches C at A. Another circle has centre Y inside C and touches C at B and touches C' at Z. Prove that the lines XB, YA and OZ are concurrent.

A3.  Given three positive integers a, b, c, we can derive 8 numbers using one addition and one multiplication and using each number just once: a+b+c, a+bc, b+ac, c+ab, (a+b)c, (b+c)a, (c+a)b, abc. Show that if a, b, c are distinct positive integers such that n/2 < a, b, c, ≤ n, then the 8 derived numbers are all different. Show that if p is prime and n ≥ p², then there are just d(p-1) ways of choosing two distinct numbers b, c from {p+1, p+2, ... , n} so that the 8 numbers derived from p, b, c are not all distinct, where d(p-1) is the number of positive divisors of p-1.

A4.  Find all possible pairs of positive integers (m, n) so that if you draw n lines which intersect in n(n-1)/2 distinct points and m parallel lines which meet the n lines in a further mn points (distinct from each other and from the first n(n-1)/2) points, then you form exactly 1992 regions.

A5.  a₁, a₂, a₃, ... a_n is a sequence of non-zero integers such that the sum of any 7 consecutive terms is positive and the sum of any 11 consecutive terms is negative. What is the largest possible value for n?

Solutions

A triangle has sides a, b, c. Construct another triangle sides (-a + b + c)/2, (a - b + c)/2, (a + b - c)/2. For which triangles can this process be repeated arbitrarily many times?

Solution

Answer: equilateral.

We may ignore the factor 1/2, since clearly a triangle with sides x, y, z can be constructed iff a triangle with sides 2x, 2y, 2z can be constructed.

The advantage of considering the process as generating (-a + b + c), (a - b + c), (a + b - c) from a, b, c is that the sum of the sides remains unchanged at a + b + c, so we can focus on just one of the three sides. Thus we are looking at the sequence a, (a + b + c) - 2a, a + b + c - 2(-a + b + c), ... . Let d = 2a - b - c. We show that the process generates the sequence a, a - d, a + d, a - 3d, a + 5d, a - 11d, a + 21d, ... . Let the nth term be a + (-1)ⁿa_nd. We claim that a_n+1 = 2a_n + (-1)_n. This is an easy induction, for we have a + (-1)ⁿ⁺¹a_n+1d = a + b + c - 2(a + (-1)ⁿa_nd) and hence (-1)ⁿ⁺¹a_n+1d = -d - 2(-1)ⁿa_nd, and hence a_n+1 = 2a_n + (-1)ⁿ. But this shows that a_n is unbounded. Hence if d is non-zero then the process ultimately generates a negative number. Thus a necessary condition for the process to generate triangles indefinitely is that 2a = b + c. Similarly, 2b = c + a is a necessary condition. But these two equations imply (subtracting) a = b and hence a = c. So a necessary condition is that the triangle is equilateral. But this is obviously also sufficient. 

Given a circle C centre O. A circle C' has centre X inside C and touches C at A. Another circle has centre Y inside C and touches C at B and touches C' at Z. Prove that the lines XB, YA and OZ are concurrent.

Solution

We need Ceva's theorem, which states that given points D, E, F on the lines BC, CA, AB, the lines AD, BE, CF are concurrent iff (BD/DC) (CE/EA) (AF/FB) = 1 (where we pay attention to the signs of BD etc, so that BD is negative if D lies on the opposite side of B to C). Here we look at the triangle OXY, and the points A on OX, B on OY and Z on XY (it is obvious that Z does lie on XY). We need to consider (OA/AX) (XZ/ZY) (YB/BO). AX and BY are negative and the other distances positive, so the sign is plus. Also OA = OB, AX = XZ, and ZY = YB (ignoring signs), so the expression is 1. Hence AY, XB and OZ are concurrent as required. 

Given three positive integers a, b, c, we can derive 8 numbers using one addition and one multiplication and using each number just once: a+b+c, a+bc, b+ac, c+ab, (a+b)c, (b+c)a, (c+a)b, abc. Show that if a, b, c are distinct positive integers such that n/2 < a, b, c, <= n, then the 8 derived numbers are all different. Show that if p is prime and n ≥ p², then there are just d(p-1) ways of choosing two distinct numbers b, c from {p+1, p+2, ... , n} so that the 8 numbers derived from p, b, c are not all distinct, where d(p-1) is the number of positive divisors of p-1.

Solution

If 1 < a < b < c, we have a + b + c < ab + c < b + ac < a + bc and (b+c)a < (a+c)b < (a+b)c < abc. We also have b + ac < (a+c)b. So we just have to consider whether a + bc = (b+c)a. But if a > c/2, which is certainly the case if n/2 < a, b, c ≤ n, then a(b + c - 1) > c/2 (b + b) = bc, so a + bc < a(b + c) and all 8 numbers are different.

The numbers are not all distinct iff p + bc = (b + c)p. Put b = p + d. Then c = p(p-1)/d + p. Now we are assuming that b < c, so p + d < p(p-1)/d + p, hence d² < p(p-1), so d < p. But p is prime so d cannot divide p, so it must divide p-1. So we get exactly d(p-1) solutions provided that all the c ≤ n. The largest c is that corresponding to d = 1 and is p(p-1) + p = p² ≤ n.

Find all possible pairs of positive integers (m, n) so that if you draw n lines which intersect in n(n-1)/2 distinct points and m parallel lines which meet the n lines in a further mn points (distinct from each other and from the first n(n-1)/2) points, then you form exactly 1992 regions.

Solution

Answer: (1, 995), (10, 176), (21, 80).

n lines in general position divide the plane into n(n+1)/2 + 1 regions and each of the m parallel lines adds a further n+1 regions. So we require n(n+1)/2 + 1 + m(n+1) = 1992 or (n+1)(2m+n) = 3982 = 2·11·181. So n+1 must divide 3982, also (n+1)n < 3982, so n ≤ 62. We are also told that n is positive Thus n = 0 is disallowed. The remaining possibilities are n+1 = 2, 11, 2·11. These give the three solutions shown above.

a₁, a₂, a₃, ... a_n is a sequence of non-zero integers such that the sum of any 7 consecutive terms is positive and the sum of any 11 consecutive terms is negative. What is the largest possible value for n?

Solution

Answer: 16.

We cannot have 17 terms, because then:

a₁ + a₂ + ... + a₁₁ < 0
a₂ + a₃ + ... + a₁₂ < 0
a₃ + a₄ + ... + a₁₃ < 0
...

a7 + a8 + ... + a17 < 0

So if we add the inequalities we get that an expression is negative. But notice that each column is positive. Contradiction. On the other hand, a valid sequence of 16 terms is: -5, -5, 13, -5, -5, -5, 13, -5, -5, 13, -5, -5, -5, 13, -5, -5. Any run of 7 terms has two 13s and five -5s, so sums to 1. Any run of 11 terms has three 13s and eight -5s, so sums to -1.

[more...]

3rd Asian Pacific Mathematics Olympiad 1991 Problems

3rd Asian Pacific Mathematics Olympiad 1991 Problems

A1.  ABC is a triangle. G is the centroid. The line parallel to BC through G meets AB at B' and AC at C'. Let A'' be the midpoint of BC, C'' the intersection of B'C and BG, and B'' the intersection of C'B and CG. Prove that A''B''C'' is similar to ABC.

A2.  There are 997 points in the plane. Show that they have at least 1991 distinct midpoints. Is it possible to have exactly 1991 midpoints?

A3.  x_i and y_i are positive reals with ∑₁ⁿ x_i = ∑₁ⁿ y_i. Show that ∑₁ⁿ x_i²/(x_i + y_i) ≥ (∑₁ⁿ x_i)/2.

A4.  A sequence of values in the range 0, 1, 2, ... , k-1 is defined as follows: a₁ = 1, a_n = a_n-1 + n (mod k). For which k does the sequence assume all k possible values?

A5.  Circles C and C' both touch the line AB at B. Show how to construct all possible circles which touch C and C' and pass through A.

Solutions

ABC is a triangle. G is the centroid. The line parallel to BC through G meets AB at B' and AC at C'. Let A'' be the midpoint of BC, C'' the intersection of B'C and BG, and B'' the intersection of C'B and CG. Prove that A''B''C'' is similar to ABC.

Solution

Let M be the midpoint of AB and N the midpoint of AC. Let A''M meet BG at X. Then X must be the midpoint of A''M (an expansion by a factor 2 center B takes A''M to CA and X to N). Also BX/BN = 1/2 and BG/BN = 2/3, so XG = BX/3. Let the ray CX meet AB at Z. Then ZX = CX/3. (There must be a neat geometric argument for this, but if we take vectors origin B, then BX = BN/2 = BA/4 + BC/4, so BZ = BA/3 and so XZ = 1/3 (BA/4 - 3BC/4) = CX/3.) So now triangles BXC and ZXG are similar, so ZG is parallel to BC, so Z is B' and X is C''. But A''X is parallel to AC and 1/4 its length, so A''C'' is parallel to AC and 1/4 its length. Similarly A''B'' is parallel to AB and 1/4 its length. Hence A''B''C'' is similar to ABC. 

There are 997 points in the plane. Show that they have at least 1991 distinct midpoints. Is it possible to have exactly 1991 midpoints?

Solution

Answer: yes. Take the 997 points collinear at coordinates x = 1, 3, ... , 1993. The midpoints are 2, 3, 4, ... , 1992.

Take two points A and B which are the maximum distance apart. Now consider the following midpoints: M, the midpoint of AB, the midpoint of each AX for any other X in the set (not A or B), and the midpoint of each BX. We claim that all these are distinct. Suppose X and Y are two other points (apart from A and B). Clearly the midpoints of AX and AY must be distinct (otherwise X and Y would coincide). Similarly the midpoints of BX and BY must be distinct. Equally, the midpoint of AX cannot be M (or X would coincide with B), nor can the midpoint of BX be M. Suppose, finally, that N is the midpoint of AX and BY. Then AYXB is a parallelogram and either AX or BY must exceed AB, contradicting the maximality of AB. So we have found 1991 distinct midpoints. The example above shows that there can be exactly 1991 midpoints. 

x_i and y_i are positive reals with ∑₁ⁿ x_i = ∑₁ⁿ y_i. Show that ∑₁ⁿ x_i²/(x_i + y_i) ≥ (∑₁ⁿ x_i)/2.

Solution

We use Cauchy-Schwartz: ∑ (x/√(x+y) )² ∑ (√(x+y) )² ≥ (∑ x )². So ∑ x²/(x+y) >= (∑ x)²/(∑(x+y) = 1/2 ∑ x.

A sequence of values in the range 0, 1, 2, ... , k-1 is defined as follows: a₁ = 1, a_n = a_n-1 + n (mod k). For which k does the sequence assume all k possible values?

Solution

Let f(n) = n(n+1)/2, so a_n = f(n) mod k. If k is odd, then f(n+k) = f(n) mod k, so the sequence can only assume all possible values if a₁, ... , a_k are all distinct. But f(k-n) = f(n) mod k, so there are at most (k+1)/2 distinct values. Thus k odd does not work.

If k is even, then f(n+2k) = f(n) mod k, so we need only look at the first 2k values. But f((2k-1-n) = f(n) mod k and f(2k-1) = 0 mod k, so the sequence assumes all values iff a₁, a₂, ... , a_k-1 assume all the values 1, 2, ... , k-1.

Checking the first few, we find k = 2, 4, 8, 16 work and k = 6, 10, 12, 14 do not. So this suggests that k must be a power of 2. Suppose k is a power of 2. If f(r) = f(s) mod k for some 0 < r, s < k, then (r - s)(r + s + 1) = 0 mod k. But each factor is < k, so neither can be divisible by k. Hence both must be even. But that is impossible (because their sum is 2r+1 which is odd), so each of f(1), f(2), ... , f(k-1) must be distinct residues mod k. Obviously none can be 0 mod k (since 2k cannot divide r(r+1) for 0 < r < k and so k cannot divide f(r) ). Thus they must include all the residues 1, 2, ... k-1. So k a power of 2 does work.

Now suppose h divides k and k works. If f(n) = a mod k, then f(n) = a mod h, so h must also work. Since odd numbers do not work, that implies that k cannot have any odd factors. So if k works it must be a power of 2. 

Circles C and C' both touch the line AB at B. Show how to construct all possible circles which touch C and C' and pass through A.

Solution

Take a common tangent touching C' at Q' and C at Q. Let the line from Q to A meet C again at P. Let the line from Q' to A meet C' again at P'. Let the C have center O and C' have center O'. Let the lines OP and O'P' meet at X. Take X as the center of the required circle. There are two common tangents, so this gives two circles, one enclosing C and C' and one not.

To see that this construction works, invert wrt the circle on center A through B. C and C' go to themselves under the inversion. The common tangent goes to a circle through A touching C and C'. Hence the point at which it touches C must be P and the point at which it touches C' must be P'.

[more...]

2nd Asian Pacific Mathematics Olympiad 1990 Problems

2nd Asian Pacific Mathematics Olympiad 1990 Problems

A1.  Given θ in the range (0, π) how many (incongruent) triangles ABC have angle A = θ, BC = 1, and the following four points concyclic: A, the centroid, the midpoint of AB and the midpoint of AC?

A2.  x₁, ... , x_n are positive reals. s_k is the sum of all products of k of the x_i (for example, if n = 3, s₁ = x₁ + x₂ + x₃, s₂ = x₁x₂ + x₂x₃ + x₃x₁, s₃ = x₁x₂x₃). Show that s_ks_n-k ≥ (nCk)² s_n for 0 < k < n.

A3.  A triangle ABC has base AB = 1 and the altitude from C length h. What is the maximum possible product of the three altitudes? For which triangles is it achieved?

A4.  A graph with n > 1 points satisfies the following conditions: (1) no point has edges to all the other points, (2) there are no triangles, (3) given any two points A, B such that there is no edge AB, there is exactly one point C such that there are edges AC and BC. Prove that each point has the same number of edges. Find the smallest possible n.

A5.  Show that for any n ≥ 6 we can find a convex hexagon which can be divided into n congruent triangles.

Solution

Given θ in the range (0, π) how many (incongruent) triangles ABC have angle A = θ, BC = 1, and the following four points concyclic: A, the centroid, the midpoint of AB and the midpoint of AC?

Solution

Answer: 1 for θ ≤ 60 deg. Otherwise none.

Let O be the circumcenter of ABC and R the circumradius, let M be the midpoint of BC, and let G be the centroid. We may regard A as free to move on the circumcircle, whilst O, B and C remain fixed. Let X be the point on MO such that MX/MO = 1/3. An expansion by a factor 3, center M, takes G to A and X to O, so G must lie on the circle center X radius R/3.

The circle on diameter OA contains the midpoints of AB and AC (since if Z is one of the midpoints OZ is perpendicular to the corresponding side). So if G also lies on this circle then angle OGA = 90 deg and hence angle MGO = 90 deg, so G must also lie on the circle diameter OM. Clearly the two circles for G either do not intersect in which case no triangle is possible which satisfies the condition or they intersect in one or two points. But if they intersect in two points, then corresponding triangles are obviously congruent (they just interchange B and C). So we have to find when the two circle intersect.

Let the circle center X meet the line OXM at P and Q with P on the same side of X as M. Now OM = R cos θ, so XM = 1/3 R cos θ < 1/3 R = XP, so M always lies inside PQ. Now XO = 2/3 OM = 1/3 R (2 cos θ), so XQ = 1/3 R > XO iff 2 cos θ < 1 or θ > π/3. Thus if θ > π/3, then XQ > XO and so the circle diameter OM lies entirely inside the circle center X radius R/3 and so they cannot intersect. If θ = π/3, then the circles touch at O, giving the equilateral triangle as a solution. If θ < π/3, then the circles intersect giving one incongruent triangle satisfying the condition.

x₁, ... , x_n are positive reals. s_k is the sum of all products of k of the x_i (for example, if n = 3, s₁ = x₁ + x₂ + x₃, s₂ = x₁x₂ + x₂x₃ + x₃x₁, s₃ = x₁x₂x₃). Show that s_ks_n-k ≥ (nCk)² s_n for 0 < k < n.

Solution

Each of s_k and s_n-khave nCk terms. So we may multiply out the product s_ks_n-k to get a sum of (nCk)² terms. We now apply the arithmetic/geometric mean result. The product of all the terms must be a power of s_n by symmetry and hence must be s_n to the power of (nCk)². So the geometric mean of the terms is just s_n. Hence result. 

A triangle ABC has base AB = 1 and the altitude from C length h. What is the maximum possible product of the three altitudes? For which triangles is it achieved?

Solution

Answer: for h ≤ 1/2, maximum product is h², achieved by a triangle with right-angle at C; for h > 1/2, the maximum product is h³/(h² + 1/4), achieved by the isosceles triangle (AC = BC).

Solution by David Krumm

Let AC = b, BC = a, let the altitude from A have length x and the altitude from B have length y. Then ax = by = h, so hxy = h³/ab. But h = a sin B and b/sin B = 1/sin C, so h = ab sin C and the product hxy = h² sin C.

The locus of possible positions for C is the line parallel to AB and a distance h from it. [Or strictly the pair of such lines.] If h ≤ 1/2, then there is a point on that line with angle ACB = 90 deg, so in this case we can obtain hxy = h² by taking angle ACB = 90 deg and that is clearly the best possible.

If h > 1/2, then there is no point on the line with angle ACB = 90 deg. Let L be the perpendicular bisector of AB and let L meet the locus at C. Then C is the point on the locus with the angle C a maximum. For if D is any other point of the line then the circumcircle of ABD also passes through the corresponding point D' on the other side of C and hence C lies inside the circumcircle. If L meets the circumcircle at C', then angle ADB = angle AC'B > angle ACB. Evidently sin C = 2 sin C/2 cos C/2 = h/(h² + 1/4), so the maximum value of hxy is h³/(h² + 1/4).

My original, less elegant, solution is as follows.

Take AP perpendicular to AB and length h. Take Q to be on the line parallel to AB through P so that BQ is perpendicular to AB. Then C must lie on the line PQ (or on the corresponding line on the other side of AB). Let a(A) be the length of the altitude from A to BC and a(B) the length of the altitude from B to AC. If C maximises the product h a(A) a(B), then it must lie on the segment PQ, for if angle ABC is obtuse, then both a(A) and a(B) are shorter than for ABQ. Similarly if BAC is obtuse. So suppose PC = x with 0 ≤ x ≤ 1. Then AC = √(x² + h²), so a(B) = h/√(x² + h²). Similarly, a(A) = h/√( (1-x)² + h²). So we wish to minimise f(x) = (x² + h²)( (1-x)² + h²) = x⁴ - 2x³ + (2h² + 1)x² - 2h²x + h⁴ + h². We have f '(x) = 2(2x-1)(x² - x + h²), which has roots x = 1/2, 1/2 ± √(1/4 - h²).

Thus for h >= 1/2, the minimum is at x = 1/2, in which case CA = CB. For h < 1/2, the minimum is at x = 1/2 ± √(1/4 - h²). But if M is the midpoint of AB and D is the point on AB with AD = 1/2 ± √(1/4 - h²), then DM = √(1/4 - h²). But DC = h, and angle CDM = 90, so MC = 1/2 and hence angle ACB = 90.

A graph with n points satisfies the following conditions: (1) no point has edges to all the other points, (2) there are no triangles, (3) given any two points A, B such that there is no edge AB, there is exactly one point C such that there are edges AC and BC. Prove that each point has the same number of edges. Find the smallest possible n.

Solution

Answer: 5.

We say A and B are joined if there is an edge AB. For any point X we write deg X for the number of points joined to X. Take any point A. Suppose deg A = m. So there are m points B₁, B₂, ... , B_m joined to A. No B_i, B_j can be joined for i ≠ j, by (2), and a point C ≠ A cannot be joined to B_i and B_j for i ≠ j, by (3). Hence there are deg B_i - 1 points C_ij joined to B_i and all the C_ij are distinct.

Now the only points that can be joined to C_ij, apart from B_i, are other C_hk, for by (3) any point of the graph is connected to A by a path of length 1 or 2. But C_ij cannot be joined to C_ik, by (2), and it cannot be joined to two distinct points C_kh and C_kh' by (3), so it is joined to at most one point C_kh for each k ≠ i. But by (3) there must be a point X joined to both B_k and C_ij (for k ≠ i), and the only points joined to B_k are A and C_kh. Hence C_ij must be joined to at least one point C_kh for each k ≠ i. Hence deg C_ij = m.

But now if we started with B_i instead of A and repeated the whole argument we would establish that deg B_i is the same as the deg C_hk, where C_hk is one of the points joined to C_i1. Thus all the points have the same degree.

Suppose the degree of each point is m. Then with the notation above there is 1 point A, m points B_i and m(m-1) points C_jk or m² + 1 in all. So n = m² + 1. The smallest possible m is 1, but that does not yield a valid graph because if does not satisfy (1). The next smallest possibility is m = 2, giving 5 points. It is easy to check that the pentagon satisfies all the conditions. 

Show that for any n ≥ 6 we can find a convex hexagon which can be divided into n congruent triangles.

Solution

We use an isosceles trianglea as the unit. The diagram shows n = 4 and n = 5. We can get any n ≥ 4 by adding additional rhombi in the middle.

[more...]

1st Asian Pacific Mathematics Olympiad 1989 Problems

1st Asian Pacific Mathematics Olympiad 1989 Problems

A1.  a_i are positive reals. s = a₁ + ... + a_n. Prove that for any integer n > 1 we have

(1 + a₁) ... (1 + a_n) < 1 + s + s²/2! + ... + sⁿ/n! .

A2.  Prove that 5n² = 36a² + 18b² + 6c² has no integer solutions except a = b = c = n = 0.

A3.  ABC is a triangle. X lies on the segment AB so that AX/AB = 1/4. CX intersects the median from A at A' and the median from B at B''. Points B', C', A'', C'' are defined similarly. Find the area of the triangle A''B''C'' divided by the area of the triangle A'B'C'.

A4.  Show that a graph with n vertices and k edges has at least k(4k - n²)/3n triangles.

A5.  f is a strictly increasing real-valued function on the reals. It has inverse f^-1. Find all possible f such that f(x) + f^-1(x) = 2x for all x.

Solutions

a_i are positive reals. s = a₁ + ... + a_n. Prove that for any integer n > 1 we have (1 + a₁) ... (1 + a_n) < 1 + s + s²/2! + ... + sⁿ/n! .
Solution
We use induction on n. For n = 2 the rhs is 1 + a₁ + a₂ + a₁a₂ + (a₁² + a₂²)/2 > lhs. Assume the result is true for n. We note that, by the binomial theorem, for s and t positive we have s^m+1 + (m+1) t s^m < (s + t)^m+1, and hence s^m+1/(m+1)! + t s^m/m! < (s + t)^m+1/(m+1)! . Summing from m = 1 to n+1 we get (s + t) + (s²/2! + t s/1!) + (s³/3! + t s²/2!) + ... + (sⁿ⁺¹/(n+1)! + t sⁿ/n!) < (s + t) + (s + t)²/2! + ... + (s + t)ⁿ⁺¹/(n+1)! . Adding 1 to each side gives that (1 + t)(1 + s + s²/2! + ... + sⁿ/n!) < (1 + (s+t) + ... + (s+t)ⁿ⁺¹/(n+1)! . Finally putting t = a_n+1 and using the the result for n gives the result for n+1.

Prove that 5n² = 36a² + 18b² + 6c² has no integer solutions except a = b = c = n = 0.
Solution
The rhs is divisible by 3, so 3 must divide n. So 5n² - 36a² - 18b² is divisible by 9, so 3 must divide c. We can now divide out the factor 9 to get: 5m² = 4a² + 2b² + 6d². Now take m, a, b, d to be the solution with the smallest m, and consider residues mod 16. Squares = 0, 1, 4, or 9 mod 16. Clearly m is even so 5m² = 0 or 4 mod 16. Similarly, 4a² = 0 or 4 mod 16. Hence 2b² + 6d² = 0, 4 or 12 mod 16. But 2b² = 0, 2 or 8 mod 16 and 6d² = 0, 6 or 8 mod 16. Hence 2b² + 6d² = 0, 2, 6, 8, 10 or 14 mod 16. So it must be 0. So b and d are both even. So a cannot be even, otherwise m/2, a/2, b/2, d/2 would be a solution with smaller m/2 < m.
So we can divide out the factor 4 and get: 5k² = a² + 2e² + 6f² with a odd. Hence k is also odd. So 5k² - a² = 4 or 12 mod 16. But we have just seen that 2e² + 6 f² cannot be 4 or 12 mod 16. So there are no solutions.

ABC is a triangle. X lies on the segment AB so that AX/AB = 1/4. CX intersects the median from A at A' and the median from B at B''. Points B', C', A'', C'' are defined similarly. Find the area of the triangle A''B''C'' divided by the area of the triangle A'B'C'.
Solution
Answer: 25/49.
Let M be the midpoint of AB. We use vectors center G. Take GA = A, GB = B, GC = C. Then GM = A/2 + B/2 and GX = 3/4 A + 1/4 C. Hence GA' = 2/5 A (showing it lies on GA) = 4/5 (3/4 A + 1/4 B) + 1/5 C, since A + B + C = 0 (which shows it lies on CX). Similarly, GB'' = 4/7 (1/2 A + 1/2 C) (showing it lies on the median through B) = 2/7 A + 2/7 C = 5/7 (2/5 A) + 2/7 C (showing it lies on CA' and hence on CX). Hence GB'' = -2/7 B. So we have shown that GB'' is parallel to GB' and 5/7 the length. The same applies to the distances from the centroid to the other vertices. Hence triangle A''B''C'' is similar to triangle A'B'C' and its area is 25/49 times the area of A'B'C'.

Show that a graph with n vertices and k edges has at least k(4k - n²)/3n triangles.
Solution
Label the points 1, 2, ... , n and let point i have degree d_i (no. of edges). Then if i and j are joined they have at least d_i + d_j - 2 other edges between them, and these edges join them to n - 2 other points. So there must be at least d_i + d_j - n triangles which have i and j as two vertices. Hence the total number of triangles must be at least ∑_{edges ij} (d_i + d_j - n)/3. But ∑_{edges ij} (d_i + d_j) = ∑ d_i², because each point i occurs in just d_i terms. Thus the total number of triangles is at least (∑ d_i²)/3 - nk/3. But ∑ d_i² ≥ (∑ d_i) ²/n (a special case of Chebyshev's inequality) = 4k²/n. Hence result.

f is a strictly increasing real-valued function on the reals. It has inverse f^-1. Find all possible f such that f(x) + f^-1(x) = 2x for all x.
Solution
Answer: f(x) = x + b for some fixed real b.
Suppose for some a we have f(a) ≠ a. Then for some b ≠ 0 we have f(a) = a + b. Hence f(a + b) = a + 2b (because f( f(a) ) + f^-1( f(a) ) = 2 f(a), so f(a + b) + a = 2a + 2b ) and by two easy inductions, f(a + nb) = a + (n+1)b for all integers n (positive or negative).
Now take any x between a and a + b. Suppose f(x) = x + c. The same argument shows that f(x + nc) = x + (n+1)c. Since f is strictly increasing x + c must lie between f(a) = a + b and f(a+b) = a + 2b. So by a simple induction x + nc must lie between a + nb and a + (n+1)b. So c lies between b + (x-a)/n and b + (a+b-x)/n or all n. Hence c = b. Hence f(x) = x + b for all x.
If there is no a for which f(a) ≠ a, then we have f(x) = x for all x.

[more...]