Asian Pacific Mathematical Olympiad(apmo)

12th APMO 2000

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.

 
Problem 2

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.

 
Problem 4

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.

 
Problem 5

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.