4th Austrian-Polish Mathematics Competition 1981 Problems

4th Austrian-Polish Mathematics Competition 1981 Problems

1.  Find the smallest n for which we can find 15 distinct elements a₁, a₂, ... , a₁₅ of {16, 17, ... , n} such that a_k is a multiple of k.

Read more »

Posted in: APMC

3rd Austrian-Polish Mathematics Competition 1980 Problems

3rd Austrian-Polish Mathematics Competition 1980 Problems

1.  A, B, C are infinite arithmetic progressions of integers. {1, 2, 3, 4, 5, 6, 7, 8} is a subset of their union. Show that 1980 also belongs to their union.

Read more »

Posted in: APMC

2nd Austrian-Polish Mathematics Competition 1979 Problems

2nd Austrian-Polish Mathematics Competition 1979 Problems

1.  ABCD is a square. E is any point on AB. F is the point on BC such that BF = BE. The perpendicular from B meets EF at G. Show that ∠DGF = 90^o.

Read more »

Posted in: APMC

1st Austrian-Polish Mathematics Competition 1978 Problems

1st Austrian-Polish Mathematics Competition 1978 Problems

1.  Find all real-valued functions f on the positive reals which satisfy f(x + y) = f(x² + y²) for all positive x, y.

2.  A parallelogram has its vertices on the boundary of a regular hexagon and its center at the center of the hexagon. Show that its area is at most 2/3 the area of the hexagon.

Read more »

Posted in: APMC

15th Asian Pacific Mathematics Olympiad 2003 Problems

15th Asian Pacific Mathematics Olympiad 2003 Problems

1.  The polynomial a₈x⁸ +a₇x⁷ + ... + a₀ has a₈ = 1, a₇ = -4, a₆ = 7 and all its roots positive and real. Find the possible values for a₀.

Read more »

Posted in: APMO

14th Asian Pacific Mathematics Olympiad 2002 Problems

14th Asian Pacific Mathematics Olympiad 2002 Problems

A1.  x_i are non-negative integers. Prove that x₁! x₂! ... x_n! ≥ ( [(x₁ + ... + x_n)/n] ! )ⁿ (where [y] denotes the largest integer not exceeding y). When do you have equality?

Read more »

Posted in: APMO

13th Asian Pacific Mathematics Olympiad 2001 Problems

13th Asian Pacific Mathematics Olympiad 2001 Problems

A1.  If n is a positive integer, let d be the number of digits in n (in base 10) and s be the sum of the digits. Let n(k) be the number formed by deleting the last k digits of n. Prove that n = s + 9 n(1) + 9 n(2) + ... + 9 n(d).

A2.  Find the largest n so that the number of integers less than or equal to n and divisible by 3 equals the number divisible by 5 or 7 (or both).

A3.  Two equal-sized regular n-gons intersect to form a 2n-gon C. Prove that the sum of the sides of C which form part of one n-gon equals half the perimeter of C.

A4.  Find all real polynomials p(x) such that x is rational iff p(x) is rational.

A5.  What is the largest n for which we can find n + 4 points in the plane, A, B, C, D, X₁, ... , X_n, so that AB is not equal to CD, but for each i the two triangles ABX_i and CDX_i are congruent? 

Solutions

13th APMO 2001 Problem 1

If n is a positive integer, let d+1 be the number of digits in n (in base 10) and s be the sum of the digits. Let n(k) be the number formed by deleting the last k digits of n. Prove that n = s + 9 n(1) + 9 n(2) + ... + 9 n(d).

Solution

Let the digits of n be a_d, a_d-1, ... , a₀, so that n = a_d 10^d + ... + a₀. Then n(k) = a_d 10^d-k + a^d-1 10^d-k-1 + ... + a_k. Obviously s = a_d + ... + a₀. Hence s + 9 n(1) + ... + 9 n(d) = a_d(9.10^d-1 + 9.10^d-2 + ... + 9 + 1) + a_d-1(9.10^d-2 + ... + 9 + 1) + ... + a_d-k(9.10^d-k-1 + ... + 9 + 1) + a₁(9 + 1) + a₀ = a_d 10^d + ... + a₀ = n. 

13th APMO 2001 Problem2

Find the largest n so that the number of integers less than or equal to n and divisible by 3 equals the number divisible by 5 or 7 (or both).

Solution

Answer: 65.

Let f(n) = [n/3] - [n/5] - [n/7] + [n/35]. We are looking for the largest n with f(n) = 0. Now [n/5] + [n/7} <= [n/5 + n/7] = [12n/35] = [n/3 + n/105]. So for [n/5] + [n/7] to exceed [n/3] we certainly require n/105 ≥ 1/3 or n ≥ 35. Hence f(n) ≥ 0 for n ≤ 35. But f(n+35) = [n/3 + 11 + 2/3] - [n/5 + 7] - [n/7 + 5] + [n/35 + 1] = [n/3 + 2/3] - [n/5] - [n/7] + [n/35] ≥ f(n) (*). Hence f(n) ≥ 0 for all n. But f(n+105) = [n/3 + 35] - [n/5 + 21] - [n/7 + 15] + [n/35 + 3] = f(n) + 2. Hence f(n) ≥ 2 for all n ≥ 105.

Referring back to (*) we see that f(n+35) > f(n), and hence f(n+35) > 0, unless n is a multiple of 3. But if n is a multiple of 3, then n + 35 is not and hence f(n+70) > f(n+35) > 0. So f(n) > 0 for all n ≥ 70.

f(70) = 1. So f(69) = 2 (we have lost 70, a multiple of 7). So f(68) = f(67) = f(66) = 1 (we have lost 69, a multiple of 3). Hence f(65) = 0 (we have lost 66, a multiple of 3). 

13th APMO 2001 Problem3

Two equal-sized regular n-gons intersect to form a 2n-gon C. Prove that the sum of the sides of C which form part of one n-gon equals half the perimeter of C.

Solution

Let one regular n-gon have vertices P₁, P₂, ... , P_n and the other have vertices Q₁, Q₂, ... , Q_n. Each side of the 2n-gon forms a triangle with one of the P_i or Q_i. Note that P_i and Q_j must alternate as we go around the 2n-gon. For convenience assume that the order is P₁, Q₁, P₂, Q₂, ... , P_n, Q_n. Let the length of the side which forms a triangle with P_i be p_i, and the length of the side which forms a triangle with Q_i be q_i. Each of these triangles has one angle (180^o - 360^o/n). Adjacent triangles have one of their other angles equal (alternate angles), so all the triangles are similar. If the sides of the triangle vertex P_i have lengths a_i, b_i, p_i, then the side P_iP_i+1 is b_i + q_i + a_i+1, and a_i/a_i+1 = b_i/b_i+1 = p_i/p_i+1. Similarly, if the sides of the triangle vertex Q_i have lengths c_i, d_i, q_i, then the side Q_iQ_i+1 is d_i + p_i+1 + c_i+1 and c_i/c_i+1 = d_i/d_i+1 = q_i/q_i+1. But a_i/b_i = d_i/c_i (not c_i/d_i), because the triangles alternate in orientation.

Put a_i/p_i = h, b_i/p_i = k. Note that a_i + b_i > p_i, so h + k - 1 > 0. We have also c_i/q_i = k, d_i/q_i = h. Adding the expressions for P_iP_i+1 we get perimeter P_i = ∑(b_i + q_i + a_i+1) = k ∑ p_i + ∑ q_i + h ∑ p_i. Similarly, perimeter Q_i = (h + k) ∑ q_i + ∑ p_i. The two n-gons are equal, so (h + k - 1) ∑ p_i = (h + k - 1) ∑ q_i. Hence ∑ p_i = ∑ q_i, which is the required result.

13th APMO 2001 Problem4

Find all real polynomials p(x) such that x is rational iff p(x) is rational.

Solution

It is necessary for all the coefficients of x to be rational. This is an easy induction on the number of coefficients. For p(0) must be rational, hence ( p(x) - p(0) )/x must be rational for all rational x and so on.

Clearly this condition is also sufficient for polynomials of degree 0 or 1.

There are obviously no quadratics, for if p(x) = ax² + bx + c, with a, b, c rational, then p(√2 - b/2a) = 2a - b²/4a + c, which is rational.

We prove that if there are also no higher degree polynomials. The idea is to show that there is a rational value k which must be taken for some real x, but which cannot be taken by any rational x.

Suppose p(x) has degree n > 1. Multiplying through by the lcm of the denominators of the coefficients, we get p(x) = (a xⁿ + b x^n-1 + ... + u x + v)/w, where a, b, ... , w are all integers. Put x = r/s, where r and s are coprime integers, then p(r/s) = (a rⁿ + b r^n-1s + ... + u r s^n-1 + v sⁿ)/( w sⁿ). Let q be any prime which does not divide a or w. Consider first a > 0. p(x) must assume all sufficiently large positive values. So it must in particular take the value k = m + 1/q, where m is a sufficiently large integer. So k = (mq + 1)/q. The denominator is divisible by q, but not q² and the numerator is not divisible by q. Suppose p(r/s) = k for some integers r, s. The denominator of p(r/s) is w sⁿ. We know that w is not divisible by q, so q must divide s. But n > 1, so q² divides w sⁿ. The numerator of p(r/s) has the form a rⁿ + h s. Neither a nor r is divisible by q, so the numerator is not divisible by q. Thus no cancellation is possible and we cannot have p(r/s) = k. Thus there must be some irrational x such that p(x) = k.

If a < 0, then the same argument works except that we take k = m + 1/q, where m is a sufficiently large negative integer.

13th APMO 2001 Problem 5

What is the largest n for which we can find n + 4 points in the plane, A, B, C, D, X₁, ... , X_n, so that AB is not equal to CD, but for each i the two triangles ABX_i and CDX_i are congruent?

Answer 4

Solution

Many thanks to Allen Zhang for completing the proof

Assume AB = a, CD = b with a > b. If ABX and CDX are congruent, then either AX or BX = CD = b, so X lies either on the circle S_A center A radius b, or on the circle S_Bcenter B radius b. Similarly, CX or DX = AB = a, so X lies either on the circle S_C center C radius a, or on the circle S_D center D radius a. Thus we have four pairs of circles, (S_A, S_C), (S_A, S_D), (S_B, S_C), (S_B, S_D) each with at most 2 points of intersection. X must be one of these 8 points.

However, we show that if two points of intersection of (S_A, S_C) are included, then no points of (S_B, S_D) can be included. The same applies to each pair of circles, so at most 4 points X are possible. Finally, we will give an example of n = 4, showing that the maximum of 4 is achieved.

So suppose (S_A, S_C) intersect at X and Y. We must have BX = DX and BY = DY, so X and Y both lie on the perpendicular bisector of BD. In other words, XY is the perpendicular bisector of BD, so D is the reflection of B in the line XY. There is no loss of generality in taking B (and D) to be on the same side of AC as X. Let A' be the reflection of A in the line XY. Since B lies on the circle center A radius a, D must lie on the circle center A' radius A. Thus the triangles A'XC and CDA' are congruent.

(Note that A and C can be on the same side of XY or opposite sides.) Hence D is the same height above AC as X, so DX is perpendicular to XY. Hence X is the midpoint of BD. Also ∠A'CD = ∠CA'X = 180^o - ∠CAX, so AX and CD are parallel. They are also equal, so ACDX is a parallelogram and hence AC = DX = BD/2. In the second configuration above, both A and C are on the same side of XY as D, so the midpoint M of AC lies on the same side of XY as D. In the first configuration, since AX = b < a = CX, M lies to the right of XY.

Now suppose there is a solution for the configuration (S_B, S_D). Thus there is a point Z such that ABZ and ZDC are congruent. Then AZ = CZ, so Z lies on the perpendicular bisector of AC and hence on the same side of XY as D. But it is also a distance a from D and a distance b from B, and a > b, so it must lie on the same side of XY as B. Contradiction. So there are no solutions for the configuration (S_B, S_D), as required. That completes the proof that n ≤ 4.

For an example with n = 4, take a regular hexagon ACDBX₃X₂. Extend the side X₂X₃ to X₁X₄, with X₁, X₂, X₃, X₄ equally spaced in that order, so that X₁AX₂ and X₃BX₄ are equilateral. Then ABX₁ and CX₁D are congruent, ABX₂ and DX₂C are congruent, ABX₃ and X₃CD are congruent, and ABX₄ and X₄DC are congruent.

Read more »

Posted in: APMO

Arithmetic Facts Flashcards

Arithmetic Facts Flashcards

Guidelines:

The Three Stacks.  Initially, some (if not all) of the new flashcards are divided into a weekly stack and a daily stack.  After several weeks of daily work, a finished stack is created. 

Getting Started.  Individual flashcards are initially created by cutting the flashcard sheets along the lines.  Answers should be written lightly in pencil on the back.  On the first day, go through a large stack of new flashcards (perhaps more than 100 cards), by dividing it into two stacks: the weekly stack, which are those cards the child knows very well and quickly (e.g. as quickly as one ought to know 2+3=5), and the daily stack, which are those cards the child either doesn’t know, or should be recalled more quickly.

<  The child then needs to practice the daily stack every day for the rest of the week.  Then, on the determined day of the week, shuffle together the weekly stack and the daily stack, and go through it all in order to create a new daily stack and weekly stack.  Once the weekly stack becomes smaller you can add more new flashcards to it.  The daily stack should never be so big that it takes too much time to get through; it should be between 10 and 50 cards, and take just a few minutes to get through.  The drive to school can be an ideal time to do the daily stack.  Once a card has been in the weekly stack for about two months and there seems to be no chance that it will ever be forgotten, then it can be put into the finished stack.  The goal is to have all of the flashcards end up in the finished stack.  Even this finished stack should be reviewed a couple times per year.

Read more:

• http://www.hoctoanonline.com/download/Arithmetic-facts-flashcards.doc
• Arithmetic Review Sheets for 7th grade - from 6th grade wkbk (.doc)

Read more »

Posted in: Basic and Anvanced Math

3rd Grade Arithmetic Facts Practice Sheets

All about these third grade arithmetic facts practice sheets

• Free download! You can download our third grade arithmetic facts practice sheets for free from our website: www.meaningfulmathbooks.com.  On this website, there are also sheets designed for fourth and fifth grade, as well as a variety of other resources related to Making Math Meaningful books.

• Facts of the Week!  (See next page.)  Central to the idea behind these sheets is that every week there are five facts on the board which the teacher works on with the whole class during the week in a variety of ways (e.g., using movement, rhythmical work, games, etc.).  These facts of the week then appear multiple times on the sheets for the current week, and are then reviewed systematically for the next several weeks. 

Background work.  These sheets should ideally be the culmination of two years of work.  If the work in first and second grade has been effective, then the children should feel that these sheets are easy.  If these sheets become too difficult and tedious, then it is likely that the classroom work being done in preparation for these sheets is either insufficient or not effective enough.

Timing and rhythm.  The intention is that the first practice sheet should be done at some point between the end of September and the end of October of third grade.  It can, of course, vary depending upon the class.  After that, a sheet should be done (nearly) every day until the whole set of 100 sheets is completed.  There are 20 weeks (100 days) of sheets in this set.  Each sheet has 30 problems.

Completion.  Since these sheets are designed to be an integral part of learning the math facts, it is important that each sheet of the entire set be completed, otherwise certain facts won’t get adequate exposure.

Caution!  This should be fun and easy for the students.  If successful, this builds their confidence.  It is important to make sure that these sheets don’t become torture for the students.  Try to de-emphasize the importance of speed.  Help the students to realize that improvement is what is important.

The whole picture.  The 30 problems listed on a particular sheet are only a part of the daily math practice.  It would be very unfortunate if daily math practice consisted of nothing more that the 30 arithmetic facts practice problems that appear on these sheets.

• When the class is not in a math main lesson, daily math practice should take about 10 minutes.  The 30 arithmetic facts may take 3-5 minutes.  The remaining 5-7 minutes can be spent doing a couple of written (vertical) arithmetic problems, some brief rhythmical work, or something else.

• When the class is in a math main lesson, daily math practice should take about 30 minutes.  The 30 arithmetic facts may take 3-5 minutes.  After that, the remaining 25 minutes of math practice (during a math main lesson) consists of the material that was brought in previous blocks and the current one.

The elements of math practice.  The following list shows some of the aspects to consider when planning math practice for the day.

• Arithmetic facts practice sheet.  The teacher copies by hand the 30 problems from a given day (see following sheets) onto paper to be photocopied.[1]  (about 5 minutes)

• Mental arithmetic.  The teacher may decide to read the first 6 problems orally.

• Extra math practice problems.  There should be a few problems that the teacher comes up with and writes on the board.  The students copy them into their practice books and work out the answers.  These problems also include practice and review of material covered in previous math blocks.  (Takes 20-25 minutes if the class is in a math block, otherwise only 5 minutes.)

• Challenge problems.  It is important that the last few problems (that the teacher adds on) be more challenging in order to keep the “quicker” students fully engaged.

What comes next?  The next set of practice sheets is titled Fourth Grade Arithmetic Facts Review Sheets, and is intended to thoroughly review the math facts covered on the first practice sheets.

The hope is that just five minutes per day practicing these arithmetic facts results in the whole class quite effortlessly learning their math facts by heart.

And what happens if…?  We hope that it won’t happen, but there may be a few children at the end of third grade who still haven’t learned their arithmetic facts.  In order to help these children, we can give them a multiplication/division table (i.e., a square for the tables).  Additionally, these students should study the basic arithmetic problems with flashcards during morning practice time.

Read more:

• Third grade arithmetic facts practice sheets: http://www.kidsmathlearning.com/download/3rd-Grade-Arithmetic-Facts-Practice-Sheets.doc

• Fourth grade arithmetic facts review sheets
• Fifth grade arithmetic facts practice sheets
• Student / Parent / Teacher agreement for seventh grade math
• Student / Parent / Teacher agreement for eighth grade math

Read more »

Posted in: Basic and Anvanced Math

12th Asian Pacific Mathematics Olympiad 2000 Problems

12th Asian Pacific Mathematics Olympiad 2000 Problems

A1.  Find a₁³/(1 - 3a₁ + 3a₁²) + a₂³/(1 - 3a₂ + 3a₂²) + ... + a₁₀₁³/(1 - 3a₁₀₁ + 3a₁₀₁²), where a_n = n/101.

A2.  Find all permutations a₁, a₂, ... , a₉ of 1, 2, ... , 9 such that a₁ + a₂ + a₃ + a₄ = a₄ + a₅ + a₆ + a₇ = a₇ + a₈ + a₉ + a₁ and a₁² + a₂² + a₃² + a₄² = a₄² + a₅² + a₆² + a₇² = a₇² + a₈² + a₉² + a₁².

A3.  ABC is a triangle. The angle bisector at A meets the side BC at X. The perpendicular to AX at X meets AB at Y. The perpendicular to AB at Y meets the ray AX at R. XY meets the median from A at S. Prove that RS is perpendicular to BC.

A4.  If m < n are positive integers prove that nⁿ/(m^m (n-m)^n-m) > n!/( m! (n-m)! ) > nⁿ/( m^m(n+1) (n-m)^n-m).

A5.  Given a permutation s₀, s₂, ... , s_n of 0, 1, 2, .... , n, we may transform it if we can find i, j such that s_i = 0 and s_j = s_i-1 + 1. The new permutation is obtained by transposing s_i and s_j. For which n can we obtain (1, 2, ... , n, 0) by repeated transformations starting with (1, n, n-1, .. , 3, 2, 0)? 

Solutions

Find a₁³/(1 - 3a₁ + 3a₁²) + a₂³/(1 - 3a₂ + 3a₂²) + ... + a₁₀₁³/(1 - 3a₁₀₁ + 3a₁₀₁²), where a_n = n/101.

Solution

Answer: 51.

The nth term is a_n³/(1 - 3a_n + 3a_n²) = a_n³/( (1 - a_n)³ + a_n³) = n³/( (101 - n)³ + n³). Hence the sum of the nth and (101-n)th terms is 1. Thus the sum from n = 1 to 100 is 50. The last term is 1, so the total sum is 51.

Find all permutations a₁, a₂, ... , a₉ of 1, 2, ... , 9 such that a₁ + a₂ + a₃ + a₄ = a₄ + a₅ + a₆ + a₇ = a₇ + a₈ + a₉ + a₁ and a₁² + a₂² + a₃² + a₄² = a₄² + a₅² + a₆² + a₇² = a₇² + a₈² + a₉² + a₁².

Solution

We may start by assuming that a₁ < a₄ < a₇ and that a₂ < a₃, a₅ < a₆, a₈ < a₉.

Note that 1 + ... + 9 = 45 and 1² + ... + 9² = 285. Adding the three square equations together we get (a₁² + ... + a₉²) + a₁² + a₄² + a₇² = 285 + a₁² + a₄² + a₇². The total must be a multiple of 3. But 285 is a multiple of 3, so a₁² + a₄² + a₇² must be a multiple of 3. Now 3², 6² and 9² are all congruent to 0 mod 3 and the other squares are all congruent to 1 mod 3. Hence either a₁, a₄ and a₇ are all multiples of 3, or none of them are. Since 45 is also a multiple of three a similar argument with the three linear equations shows that a₁ + a₄ + a₇ is a multiple of 3. So if none of a₁, a₄, a₇ are multiples of 3, then they are all congruent to 1 mod 3 or all congruent to 2 mod 3. Thus we have three cases: (1) a₁ = 3, a₄ = 6, a₇ = 9, (2) a₁ = 1, a₄ = 4, a₇ = 7, and (3) a₁ = 2, a₄ = 5, a₇ = 8.

In case (1), we have that each sum of squares equals 137. Hence a₈² + a₉² = 47. But 47 is not a sum of two squares, so this case gives no solutions.

In case (2), we have that each sum of squares is 117. Hence a₅² + a₆² = 52. But the only way of writing 52 as a sum of two squares is 4² + 6² and 4 is already taken by a₄, so this case gives no solutions.

In case (3), we have that each sum of squares is 126 and each linear sum 20. We quickly find that the only solution is 2, 4, 9, 5, 1, 6, 8, 3, 7.

Obviously, this generates a large number of equivalent solutions. We can interchange a₂ and a₃, or a₅ and a₆, or a₈ and a₉. We can also permute a₁, a₄ and a₇. So we get a total of 2 x 2 x 2 x 6 =48 solutions. 

ABC is a triangle. The angle bisector at A meets the side BC at X. The perpendicular to AX at X meets AB at Y. The perpendicular to AB at Y meets the ray AX at R. XY meets the median from A at S. Prove that RS is perpendicular to BC.

Solution

Let the line through C parallel to AX meet the ray BA at C'. Let the perpendicular from B meet the ray C'C at T and the ray AX at U. Let the line from C parallel to BT meet BA at V and let the perpendicular from V meet BT at W. So CVWT is a rectangle.

AU bisects ∠CAV and CV is perpendicular to AU, so U is the midpoint of WT. Hence the intersection N of AU and CW is the center of the rectangle and, in particular, the midpoint of CW. Let M be the midpoint of BC. Then since M, N are the midpoints of the sides CB and CW of the triangle CBW, MN = BW/2.

Since CC' is parallel to AX, ∠CC'A = ∠BAX = ∠CAX = ∠C'CA, so AC' = AC. Let A' be the midpoint of CC'. Then AU = C'T - C'A'. But N is the center of the rectangle CTWV, so NU = CT/2 and AN = AU - NU = C'T - C'A' - CT/2 = C'T/2. Hence MN/AN = BW/C'T. But MN is parallel to BW and XY, so SX/AX = MN/AN = BW/C'T.

Now AX is parallel to VW and XY is parallel to BW, so AXY and VWB are similar and AX/XY = VW/BW = CT/BW. Hence SX/XY = (SX/AX) (AX/XY) = CT/C'T.

YX is an altitude of the right-angled triangle AXR, so AXY and YXR are similar. Hence XY/XR = XA/XY. But AXY and C'TB are similar, so XA/XY = C'T/BT. Hence SX/XR = (SX/XY) (XY/XR) = (CT/C'T) (C'T/BT) = CT/BT. But angles CTB and SXR are both right angles, so SXR and CTB are similar. But XR is perpendicular to BT, so SR is perpendicular to BC. 

If m < n are positive integers prove that nⁿ/(m^m (n-m)^n-m) > n!/( m! (n-m)! ) > nⁿ/( m^m(n+1) (n-m)^n-m).

Solution

The key is to consider the binomial expansion (m + n-m)ⁿ. This is a sum of positive terms, one of which is nCm m^m(n-m)^n-m, where nCm is the binomial coefficient n!/( m! (n-m)! ). Hence nCm m^m(n-m)^n-m < nⁿ, which is one of the required inequalities.

We will show that nCm m^m(n-m)^n-m is the largest term in the binomial expansion. It then follows that (n+1) nCm m^m(n-m)^n-m > nⁿ, which is the other required inequality.

Comparing the rth term nCr m^r(n-m)^n-r with the r+1th term nCr+1 m^r+1(n-m)^n-r-1 we see that the rth term is strictly larger for r ≥ m and smaller for r < m. Hence the mth term is larger than the succeeding terms and also larger than the preceding terms.

Given a permutation s₀, s₂, ... , s_n of 0, 1, 2, .... , n, we may transform it if we can find i, j such that s_i = 0 and s_j = s_i-1 + 1. The new permutation is obtained by transposing s_i and s_j. For which n can we obtain (1, 2, ... , n, 0) by repeated transformations starting with (1, n, n-1, .. , 3, 2, 0)?

Solution

Experimentation shows that we can do it for n=1 (already there), n = 2 (already there), 3, 7, 15, but not for n = 4, 5, 6, 8, 9, 10, 11, 12, 13, 14. So we conjecture that it is possible just for n = 2^m - 1 and for n = 2.

Notice that there is at most one transformation possible. If n = 2m, then we find that after m-1 transformations we reach

1  n  0  n-2  n-1  n-4  n-3 ... 4  5  2  3

and we can go no further. So n even fails for n > 2.

If n = 15 we get successively:

1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 start
1 0 14 15 12 13 10 11 8 9 6 7 4 5 2 3 after 7 moves
1 2 3 0 12 13 14 15 8 9 10 11 4 5 6 7 after 8 more moves
1 2 3 4 5 6 7 0 8 9 10 11 12 13 14 15 after 8 more moves

1   2   3   4   5   6   7   8   9  10  11  12  13  14  15   0   after 8 more moves

This pattern is general. Suppose n = 2^m - 1. Let P₀ be the starting position and P_r be the position:

1   2   3 ... R-1   0,   n-R+1  n-R+2  n-R+3 ... n,   n-2R+1  n-2R+2 ... n-R, ... , R  R+1 ... 2R-1 

Here R denotes 2^r and the commas highlight that, after the initial 1 2 ... R-1 0, we have increasing runs of R terms. If we start from P_r, then the 0 is transposed successively with R, 3R, 5R, ... , n-R+1, then with R+1, 3R+1, ... , n-R+2, and so on up to 2R-1, 4R-1, ... , n. But that gives P_r+1. It is also easy to check that P₀ leads to P₁ and that P_m is the required finishing position. Thus the case n = 2^m - 1 works. Now suppose n is odd but not of the form 2^m - 1. Then we can write n = (2a + 1)2^b - 1 (just take 2^b as the highest power of 2 dividing n + 1). We can now define P₀, P₁, ... , P_b as before. As before we will reach P_b:

1 2 ¼ B-1 0, 2aB 2aB+1¼ (2a+1)B-1, (2a-1)B ¼ 2aB-1, ¼ , 3B, 3B+1, ¼ 4B-1, 2B, 2B+1, ¼ , 3B-1, B, B+1, ¼ , 2B-1 

where B = 2^b - 1. But then the 0 is transposed successively with B, 3B, 5B, ... , (2a-1)B, which puts it immediately to the right of (2a+1)B-1 = n, so no further transformations are possible and n = (2a+1)2^b - 1 fails.

Read more »

Posted in: APMO

11th Asian Pacific Mathematics Olympiad 1999 Problems

11th Asian Pacific Mathematics Olympiad 1999 Problems

A1.  Find the smallest positive integer n such that no arithmetic progression of 1999 reals contains just n integers.

A2.  The real numbers x₁, x₂, x₃, ... satisfy x_i+j ≤ x_i + x_j for all i, j. Prove that x₁ + x₂/2 + ... + x_n/n ≥ x_n.

A3.  Two circles touch the line AB at A and B and intersect each other at X and Y with X nearer to the line AB. The tangent to the circle AXY at X meets the circle BXY at W. The ray AX meets BW at Z. Show that BW and BX are tangents to the circle XYZ.

A4.  Find all pairs of integers m, n such that m² + 4n and n² + 4m are both squares.

A5.  A set of 2n+1 points in the plane has no three collinear and no four concyclic. A circle is said to divide the set if it passes through 3 of the points and has exactly n - 1 points inside it. Show that the number of circles which divide the set is even iff n is even.

Find the smallest positive integer n such that no arithmetic progression of 1999 reals contains just n integers.

Solution

Answer: 70.

Using a difference of 1/n , where n does not divide 1999, we can get a progression of 1999 terms with m = [1998/n] or m = [1998/n] - 1 integers. Thus {0, 1/n, 2/n, ... , 1998/n} has m+1 integers, and {1/n, 2/n, ... , 1999/n} has m integers. So we are ok until n gets so large that the gap between [1998/n] and [1998/(n+1)] is 3 or more. This could happen for 1998/n - 1998/(n+1) just over 2 or n > 31. So checking, we find [1998/31] = 64, [1998/30] = 66, [1998/29] = 68, [1998/28] = 71.

We can get 68 integers with {1/29, 2/29, ... , 1999/29} and 69 with {0, 1/29, 2/29, ... , 1998/29}. We can get 71 with {1/28, 2/28, ... , 1999/28}, but we cannot get 70. Note that a progression with irrational difference gives at most 1 integer. A progression with difference a/b, where a and b are coprime integers, gives the same number of integers as a progression with difference 1/b. So it does not help to widen the class of progressions we are looking at.

The real numbers x₁, x₂, x₃, ... satisfy x_i+j <= x_i + x_j for all i, j. Prove that x₁ + x₂/2 + ... + x_n/n >= x_n.

Solution

We use induction. Suppose the result is true for n. We have:

x₁ >= x₁

x₁ + x₂/2 >= x₂

...

x₁ + x₂/2 + ... + x_n/n >= x_n

Also: x₁ + 2x₂/2 + ... + nx_n/n = x₁ + ... + x_n

Adding: (n+1) x₁ + (n+1)x₂/2 + ... + (n+1)x_n/n >= 2(x₁ + ... + x_n). But rhs = (x₁ + x_n) + (x₂ + x_n-1) + ... + (x_n + x₁) >= n x_n+1. Hence result.

Two circles touch the line AB at A and B and intersect each other at X and Y with X nearer to the line AB. The tangent to the circle AXY at X meets the circle BXY at W. The ray AX meets BW at Z. Show that BW and BX are tangents to the circle XYZ.

Solution

Let angle ZXW = a and angle ZWX = b. XW is tangent to circle AXY at X, so angle AYX = a. AB is tangent to circle AXY at A, so angle BAX = a. AB is tangent to circle BXY at B, so angle ABX = b. Thus, considering triangle ABX, angle BXZ = a+b. Considering triangle ZXW, angle BZX = a+b.

BXYW is cyclic, so angle BYX = angle BWX = b. Hence angle AYB = angle AYX + angle XYB = a+b = angle AZB. So AYZB is cyclic. Hence angle BYZ = angle BAZ = a. So angle XYZ = angle XYB + angle BYZ = a+b. Hence angle BZX = angle XYZ, so BZ is tangent to circle XYZ at Z. Similarly angle BXY = angle XYZ, so BX is tangent to circle XYZ at X.

Find all pairs of integers m, n such that m² + 4n and n² +4m are both squares.

Solution

Answer: (m, n) or (n, m) = (0, a²), (-5, -6), (-4, -4), (a+1, -a) where a is a non-negative integer.

Clearly if one of m, n is zero, then the other must be a square and that is a solution.

If both are positive, then m² + 4n must be (m + 2k)² for some positive k, so n = km + k² > m. But similarly m > n. Contradiction. So there are no solutions with m and n positive.

Suppose both are negative. Put m = -M, n = -N, so M and N are both positive. Assume M >= N. M² - 4N is a square, so it must be (M - 2k)² for some k, so N = Mk - k². If M = N, then M(k-1) = k², so k-1 divides k² and hence k² - (k-1)(k+1) = 1, so k = 2 and M = 4, giving the solution (m, n) = (-4, -4). So we may assume M > N and hence M > Mk - k² > 0. But that implies that k = 1 or M-1 and hence N = M-1. [If M > Mk - k², then (k-1)M < k². Hence k = 1 or M < k+2. But Mk - k² > 0, so M > k. Hence k = 1 or M = k+1.].

But N² - 4M is also a square, so (M-1)² - 4M = M² - 6M + 1 is a square. But (M-3)² > M² - 6M + 1 and (M-4)² < M² - 6M + 1 for M >= 8, so the only possible solutions are M = 1, 2, ... , 7. Checking, we find that only M = 6 gives M² - 6M + 1 a square. This gives the soluton (m, n) = (-6, -5). Obviously, there is also the solution (-5, -6).

Finally, consider the case of opposite signs. Suppose m = M > 0, n = -N < 0. Then N² + 4M is a square, so by the argument above M > N. But M² - 4N is a square and so the argument above gives N = M-1. Now we can easily check that (m, n) = (M, -(M-1) ) is a solution for any positive M.

A set of 2n+1 points in the plane has no three collinear and no four concyclic. A circle is said to divide the set if it passes through 3 of the points and has exactly n - 1 points inside it. Show that the number of circles which divide the set is even iff n is even.

Solution

Take two of the points, A and B, and consider the 2n-1 circles through A and B. We will show that the number of these circles which divide the set is odd. The result then follows almost immediately, because the number of pairs A, B is (2n+1)2n/2 = N, say. The total number of circles which divide the set is a sum of N odd numbers divided by 3 (because each such circle will be counted three times). If n is even, then N is even, so a sum of N odd numbers is even. If n is odd, then N is odd, so a sum of N odd numbers is odd. Dividing by 3 does not change the parity.

Their centers all lie on the perpendicular bisector of AB. Label them C₁, C₂, ... , C_2n-1, where the center of C_i lies to the left of C_j on the bisector iff i < j. We call the two half-planes created by AB the left-hand half-plane L and the right-hand half-plane R correspondingly. Let the third point of the set on C_i be X_i. Suppose i < j. Then C_i contains all points of C_j that lie in L and C_j contains all points of C_i that lie R. So X_i lies inside C_j iff X_i lies in R and X_j lies inside C_i iff X_j lies in L

Now plot f(i), the number of points in the set that lie inside C_i, as a function of i. If X_i and X_i+1 are on opposite sides of AB, then f(i+1) = f(i). If they are both in L, then f(i+1) = f(i) - 1, and if they are both in R, then f(i+1) = f(i) + 1. Suppose m of the X_i lie in L and 2n-1-m lie in R. Now suppose f(i) = n-2, f(i+1) = f(i+2) = ... = f(i+j) = n-1, f(i+j+1) = n. Then j must be odd. For X_i and X_i+1 must lie in R. Then the points must alternate, so X_i+2 lies in L, X_i+3 lies in R etc. But X_i+j and X_i+j+1 must lie in R. Hence j must be odd. On the other hand, if f(i+j+1) = n-2, then j must be even. So the parity of the number of C₁, C₂, ... , C_i which divide the set only changes when f crosses the line n-1 from one side to the other. We now want to say that f starts on one side of the line n-1 and ends on the other, so the final parity must be odd. Suppose there are m points in L and hence 2n-1-m in R. Without loss of generality we may take m <= n-1. The first circle C₁ contains all the points in L except X₁ if it is in L. So f(1) = m or m-1. Similarly the last circle C_2n-1 contains all the points in R except X_2n-1 if it is in R. So f(2n-1) = 2n-1-m or 2n-2-m. Hence if m < n-1, then f(1) = m or m-1, so f(1) < n-1. But 2n-1-m >= n+1, so f(2n-1) > n-1. So in this case we are done.

However, there are complications if m = n-1. We have to consider 4 cases. Case (1): m = n-1, X₁ lies in R, X_2n-1 lies in L. Hence f(1) = n-1, f(2n-1) = n > n-1. So f starts on the line n-1. If it first leaves it downwards, then for the previous point i, X_i is in L and hence there were an even number of points up to i on the line. So the parity is the same as if f(1) was below the line. f(2n-1) is above the line, so we get an odd number of points on the line. If f first leaves the line upwards, then for the previous point i, X_i is in R and hence there were an odd number of points up to i on the line. So again the parity is the same as if f(1) was below the line.

Case (2): m = n-1, X₁ lies in R, X_2n-1 lies in R. Hence f(1) = f(2n-1) = n-1. As in case (1) the parity is the same as if f(1) was below the line. If the last point j with f(j) not on the line has f(j) < n-1, then (since X_2n-1 lies in R) there are an odd number of points above j, so the parity is the same as if f(2n-1) was above the line. Similarly if f(j) > n-1, then there are an even number of points above j, so again the parity is the same as if f(2n-1) was above the line.

Case (3): m = n-1, X₁ lies in L, X_2n-1 lies in L. Hence f(1) = n-2, f(2n-1) = n. So case has already been covered.

Case (4): m=n-1, X₁ lies in L, X_n-1 lies in R. So f(1) = n-2, f(2n-1) = n-1. As in case (2), the parity is the same as if f(2n-1) was above the line.

Read more »

Posted in: APMO

10th Asian Pacific Mathematics Olympiad 1998 Problems

10th Asian Pacific Mathematics Olympiad 1998 Problems

A1.  S is the set of all possible n-tuples (X₁, X₂, ... , X_n) where each X_i is a subset of {1, 2, ... , 1998}. For each member k of S let f(k) be the number of elements in the union of its n elements. Find the sum of f(k) over all k in S.

A2.  Show that (36m + n)(m + 36n) is not a power of 2 for any positive integers m, n.

A3.  Prove that (1 + x/y)(1 + y/z)(1 + z/x) ≥ 2 + 2(x + y + z)/w for all positive reals x, y, z, where w is the cube root of xyz.

A4.  ABC is a triangle. AD is an altitude. X lies on the circle ABD and Y lies on the circle ACD. X, D and Y are collinear. M is the midpoint of XY and M' is the midpoint of BC. Prove that MM' is perpendicular to AM.

A5.  What is the largest integer divisible by all positive integers less than its cube root.

Solutions

S is the set of all possible n-tuples (X₁, X₂, ... , X_n) where each X_i is a subset of {1, 2, ... , 1998}. For each member k of S let f(k) be the number of elements in the union of its n elements. Find the sum of f(k) over all k in S.

Solution

Answer: 1998(2¹⁹⁹⁸ⁿ - 2¹⁹⁹⁷ⁿ).

Let s(n, m) be the sum where each X_i is a subset of {1, 2, ... , m}. There are 2^m possible X_i and hence 2^mn possible n-tuples. We have s(n, m) = 2ⁿs(n, m-1) + (2ⁿ - 1)2^n(m-1) (*). For given any n-tuple {X₁, ... , X_n} of subsets of {1, 2, ... , m-1} we can choose to add m or not (2 choices) to each X_i. So we derive 2ⁿ n-tuples of subsets of {1, 2, ... , m}. All but 1 of these have f(k) incremented by 1. The first term in (*) gives the sum for m-1 over the increased number of terms and the second term gives the increments to the f(k) due to the additional element.

Evidently s(n, 1) = 2ⁿ - 1. It is now an easy induction to show that s(n, m) = m(2^nm - 2^n(m-1)).

Putting m = 1998 we get that the required sum is 1998(2¹⁹⁹⁸ⁿ - 2¹⁹⁹⁷ⁿ). 

Show that (36m + n)(m + 36n) is not a power of 2 for any positive integers m, n.

Solution

Assume there is a solution. Take m ≤ n and the smallest possible m. Now (36m + n) and (m + 36n) must each be powers of 2. Hence 4 divides n and 4 divides m. So m/2 and n/2 is a smaller solution with m/2 < m. Contradiction.

Prove that (1 + x/y)(1 + y/z)(1 + z/x) ≥ 2 + 2(x + y + z)/w for all positive reals x, y, z, where w is the cube root of xyz.

Solution

(1 + x/y)(1 + y/z)(1 + z/x) = 1 + x/y + y/x + y/z + z/y + z/x + x/z = (x + y + z)(1/x + 1/y + 1/z) - 1 ≥ 3(x + y + z)/w - 1, by the arithmetic geometric mean inequality,
= 2(x + y + z)/w + (x + y + z)/w - 1 ≥ 2(x + y + z) + 3 - 1, by the arithmetic geometric mean inequality.

ABC is a triangle. AD is an altitude. X lies on the circle ABD and Y lies on the circle ACD. X, D and Y are collinear. M is the midpoint of XY and M' is the midpoint of BC. Prove that MM' is perpendicular to AM

Solution

Take P, Q so that PADB, AQCD are rectangles. Let N be the midpoint of PQ. Then PD is a diameter of the circumcircle of ABC, so PX is perpendicular to XY. Similarly, QY is perpendicular to XY. N is the midpoint of PQ and M' the midpoint of XY, so NM is parallel to PX and hence perpendicular to XY. NADM' is a rectangle, so ND is a diameter of its circumcircle and M must lie on the circumcircle. But AM' is also a diameter, so ∠AMM' = 90^o.

Thanks to Michael Lipnowski for the above. My original solution is below.

Let P be the circumcenter of ABD and Q the circumcenter of ADC. Let R be the midpoint of AM'. P and Q both lie on the perpendicular bisector of AD, which is parallel to BC and hence also passes through R. We show first that R is the midpoint of PQ.

Let the feet of the perpendiculars from P, Q, R to BC to P', Q', R' respectively. It is sufficient to show that . BP' = BD/2. BR' = BM' + M'R' = (BD + DC)/2 + M'D/2 = (BD + DC)/2 + ( (BD + DC)/2 - DC)/2 = 3BD/4 + DC/4, so P'R' = (BD + DC)/4. Q'C = DC/2, so BQ' = BD + DC/2 and P'Q' = (BD + DC)/2 = 2P'R'.

Now the circumcircle centre P meets XY in X and D, and the circumcircle centre Q meets XY in D and Y. Without loss of generality we may take XD >= DY. Put XD = 4x, DY = 4y. The circle center R through A, M' and D meets XY in a second point, say M''. Let the feet of the perpendiculars from P, Q, R to XY be P'', Q'', R'' respectively. So on XY we have, in order, X, P'', M'', R'', D, Q'', Y. Since R is the midpoint of PQ, R'' is the midpoint of P''Q''. Now P'' is the midpoint of XD and Q'' is the midpoint of DY, so P''Q'' = XY/2 = 2(x+y), so R''Q'' = x+y. But DQ'' = 2y, so R''D = x-y. R'' is the midpoint of M''D, so M''D = 2(x-y) and hence M''Y = M''D + DY = 2(x-y) + 4y = 2(x+y) = XY/2. So M'' is just M the midpoint of XY. Now AM' is a diameter of the circle center R, so AM is perpendicular to MM'. 

What is the largest integer divisible by all positive integers less than its cube root.

Solution

Answer: 420.

Let N be a positive integer satisfying the condition and let n be the largest integer not exceeding its cube root. If n = 7, then 3·4·5·7 = 420 must divide N. But N cannot exceed 8³ - 1 = 511, so the largest such N is 420.

If n ≥ 8, then 3·8·5·7 = 840 divides N, so N > 729 = 9³. Hence 9 divides N, and hence 3·840 = 2520 divides N. But we show that no N > 2000 can satisfy the condition.

Note that 2(x - 1)³ > x³ for any x > 4. Hence [x]³ > x³/2 for x > 4. So certainly if N > 2000, we have n³ > N/2. Now let p_k be the highest power of k which does not exceed n. Then p_k > n/k. Hence p₂p₃p₅ > n³/30 > N/60. But since N > 2000, we have 7 < 11 < n and hence p², p³, p⁵, 7, 11 are all ≤ n. But 77 p²p³p⁵ > N, so N cannot satisfy the condition.

Read more »

Posted in: APMO

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.

Read more »

Posted in: APMO

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.

Read more »

Posted in: APMO

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.hoctoanonline.com/download/Fractions-Decimals-Notes-for-students.doc

Read more »

Posted in: Basic and Anvanced Math

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).

Read more »

Posted in: APMO