Page 9/11 Date 18.10.2016 Size 190.93 Kb.

### 12th APMO 2000

Problem 1

Find a13/(1 - 3a1 + 3a12) + a23/(1 - 3a2 + 3a22) + ... + a1013/(1 - 3a101 + 3a1012), where an = n/101.

Solution

The nth term is an3/(1 - 3an + 3an2) = an3/( (1 - an)3 + an3) = n3/( (101 - n)3 + n3). 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 a1, a2, ... , a9 of 1, 2, ... , 9 such that a1 + a2 + a3 + a4 = a4 + a5 + a6 + a7 = a7 + a8 + a9 + a1 and a12 + a22 + a32 + a42 = a42 + a52 + a62 + a72 = a72 + a82 + a92 + a12.

Solution

We may start by assuming that a1 < a4 < a7 and that a2 < a3, a5 < a6, a8 < a9.

Note that 1 + ... + 9 = 45 and 12 + ... + 92 = 285. Adding the three square equations together we get (a12 + ... + a92) + a12 + a42 + a72 = 285 + a12 + a42 + a72. The total must be a multiple of 3. But 285 is a multiple of 3, so a12 + a42 + a72 must be a multiple of 3. Now 32, 62 and 92 are all congruent to 0 mod 3 and the other squares are all congruent to 1 mod 3. Hence either a1, a4 and a7 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 a1 + a4 + a7 is a multiple of 3. So if none of a1, a4, a7 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) a1 = 3, a4 = 6, a7 = 9, (2) a1 = 1, a4 = 4, a7 = 7, and (3) a1 = 2, a4 = 5, a7 = 8.

In case (1), we have that each sum of squares equals 137. Hence a82 + a92 = 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 a52 + a62 = 52. But the only way of writing 52 as a sum of two squares is 42 + 62 and 4 is already taken by a4, 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 a2 and a3, or a5 and a6, or a8 and a9. We can also permute a1, a4 and a7. So we get a total of 2 x 2 x 2 x 6 =48 solutions.

Problem 3

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 nn/(mm (n-m)n-m) > n!/( m! (n-m)! ) > nn/( mm(n+1) (n-m)n-m).

Solution

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

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

Comparing the rth term nCr mr(n-m)n-r with the r+1th term nCr+1 mr+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 s0, s2, ... , sn of 0, 1, 2, .... , n, we may transform it if we can find i, j such that si = 0 and sj = si-1 + 1. The new permutation is obtained by transposing si and sj. 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 = 2m - 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 = 2m - 1. Let P0 be the starting position and Pr 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 2r and the commas highlight that, after the initial 1 2 ... R-1 0, we have increasing runs of R terms. If we start from Pr, 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 Pr+1. It is also easy to check that P0 leads to P1 and that Pm is the required finishing position. Thus the case n = 2m - 1 works.

Now suppose n is odd but not of the form 2m - 1. Then we can write n = (2a + 1)2b - 1 (just take 2b as the highest power of 2 dividing n + 1). We can now define P0, P1, ... , Pb as before. As before we will reach Pb:

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 = 2b - 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)2b - 1 fails.