22st IMO 1981

Solution　We have PD.BC + PE.CA + PF.AB = 2 area of triangle. Now use Cauchy‘s inequality with x₁ = Ö(PD.BC), x₂ = Ö(PE.CA), x₃ = Ö(PF.AB), and y₁ = Ö(BC/PD), y₂ = Ö(CA/PE), y₃ = Ö(AB/PF). We get that (BC + CA + AB)² < 2 x area of triangle x (BC/PD + CA/PE + AB/PF) with equality only if x_i/y_i = const, ie PD = PE = PF. So the unique minimum position for P is the incenter.

Solution　Denote the binomial coefficient n!/(r!(n-r)!) by nCr.
Evidently nCr F(n,r) = 1 (n-1)C(r-1) + 2 (n-2)C(r-1) + ... + (n-r+1) (r-1)C(r-1). [The first term denotes the contribution from subsets with smallest element 1, the second term smallest element 2 and so on.]
Let the rhs be g(n,r). Then, using the relation (n-i)C(r-1) - (n-i-1)C(r-2) = (n-i-1)C(r-1), we find that g(n,r) - g(n-1,r-1) = g(n-1,r), and we can extend this relation to r=1 by taking g(n,0) = n+1 = (n+1)C1. But g(n,1) = 1 + 2 + ... + n = n(n+1)/2 = (n+1)C2. So it now follows by an easy induction that g(n,r) = (n+1)C(r+1) = nCr (n+1)/(r+1). Hence F(n,r) = (n+1)/(r+1).

Solution　Experimenting with small values suggests that the solutions of n² - mn - m² = 1 or -1 are successive Fibonacci numbers. So suppose n > m is a solution. This suggests trying m+n, n: (m+n)² - (m+n)n - n² = m² + mn - n² = -(n² - mn - m²) = 1 or -1. So if n > m is a solution, then m+n, n is another solution. Running this forward from 2,1 gives 3,2; 5,3; 8,5; 13,8; 21,13; 34,21; 55,34; 89,55; 144,89; 233,144; 377,233; 610,377; 987,610; 1597,987; 2584,1597.
But how do we know that there are no other solutions? The trick is to run the recurrence the other way. For suppose n > m is a solution, then try m, n-m: m² - m(n-m) - (n-m)² = m² + mn - n² = -(n² - mn - m²) = 1 or -1, so that also satisfies the equation. Also if m > 1, then m > n-m (for if not, then n >= 2m, so n(n - m) >= 2m², so n² - nm - m² >= m² > 1). So given a solution n > m with m > 1, we have a smaller solution m > n-m. This process must eventually terminate, so it must finish at a solution n, 1 with n > 1. But the only such solution is 2, 1. Hence the starting solution must have been in the forward sequence from 2, 1.
Hence the solution to the problem stated is 1597² + 987².

Solution　(a) n = 3 is not possible. For suppose x was the largest number in the set. Then x cannot be divisible by 3 or any larger prime, so it must be a power of 2. But it cannot be a power of 2, because 2^m - 1 is odd and 2^m - 2 is not a positive integer divisible by 2^m.
For k >= 2, the set 2k-1, 2k , ... , 4k-2 gives n = 2k. For k >= 3, so does the set 2k-5, 2k-4, ... , 4k-6. For k >= 2, the set 2k-2, 2k-3, ... , 4k-2 gives n = 2k+1. For k >= 4 so does the set 2k-6,2k-5, ... , 4k-6. So we have at least one set for every n >= 4, which answers (a).
(b) We also have at least two sets for every n >= 4 except possibly n = 4, 5, 7. For 5 we may take as a second set: 8, 9, 10, 11, 12, and for 7 we may take 6, 7, 8, 9 ,10, 11, 12. That leaves n = 4. Suppose x is the largest number in a set with n =4. x cannot be divisible by 5 or any larger prime, because x-1, x-2, x-3 will not be. Moreover, x cannot be divisible by 4, because then x-1 and x-3 will be odd, and x-2 only divisible by 2 (not 4). Similarly, it cannot be divisible by 9. So the only possibilities are 1, 2, 3, 6. But we also require x >= 4, which eliminates the first three. So the only solution for n = 4 is the one we have already found: 3, 4, 5, 6.

Solution　Let the triangle be ABC. Let the center of the circle touching AB and AC be D, the center of the circle touching AB and BC be E, and the center of the circle touching AC and BC be F. Because the circles center D and E have the same radius the perpendiculars from D and E to AB have the same length, so DE is parallel to AB. Similarly EF is parallel to BC and FD is parallel to CA. Hence DEF is similar and similarly oriented to ABC. Moreover D must lie on the angle bisector of A since the circle center D touches AB and AC. Similarly E lies on the angle bisector of B and F lies on the angle bisector of C. Hence the incenter I of ABC is also the incenter of DEF and acts as a center of symmetry so that corresponding points P of ABC and P’ of DEF lie on a line through I with PI/P‘I having a fixed ratio. But OD = OE = OF since the three circles have equal radii, so O is the circumcenter of DEF. Hence it lies on a line with I and the circumcenter of ABC.

Solution　f(1,n) = f(0,f(1,n-1)) = 1 + f(1,n-1). So f(1,n) = n + f(1,0) = n + f(0,1) = n + 2.
f(2,n) = f(1,f(2,n-1)) = f(2,n-1) + 2. So f(2,n) = 2n + f(2,0) = 2n + f(1,1) = 2n + 3.
f(3,n) = f(2,f(3,n-1)) = 2f(3,n-1) + 3. Let u_n = f(3,n) + 3, then u_n = 2u_n-1. Also u₀ = f(3,0) + 3 = f(2,1) + 3 = 8. So u_n = 2ⁿ⁺³, and f(3,n) = 2ⁿ⁺³ - 3.
f(4,n) = f(3,f(4,n-1)) = 2^f(4,n-1)+3 - 3. f(4,0) = f(3,1) = 2⁴ - 3 = 13. We calculate two more terms to see the pattern: f(4,1) = 2²⁴ - 3, f(4,2) = 2²²⁴ - 3. In fact it looks neater if we replace 4 by 2², so that f(4,n) is a tower of n+3 2s less 3.