Problem of the Week #2 Solution

First, a reminder of the problem:

Problem: The arithmetic, geometric, and harmonic mean of two positive integers are themselves three distinct positive integers. What is the smallest possible value of the arithmetic mean.

The solution Maeve gave in the comments works, but it relies on a lot of searching through cases. It would be nice to have a more general approach, especially since we might some day encounter a similar problem for which the solution isn’t so conveniently small (which would make testing cases much more impractical.). So let’s consider:

Solution: Let’s start by reminding ourselves of the definitions of arithmetic, geometric, and harmonic means. Let our two positive integers be a and b. Then:

  • Arithmetic Mean of a and b: (a+b)/2

  • Geometric Mean of a and b: √ ab 

  • Harmonic Mean of a and b: 2ab/(a+b)

We need each of these to be an integer, and then to minimize the arithmetic mean.

Let’s start by considering a special case. Suppose a and b have no factors in common. (This is a natural special case to consider, because we might anticipate that if a and b have a common factor, they are less likely to provide a minimal arithmetic mean.) Then we can note the following:

  1. For the arithmetic mean of a and b to be an integer, a + b must be even.

  2. For the harmonic mean of a and b to be an integer, a + b must divide 2ab. Because a + b is even, (a+b)/2 must divide ab. Since a and b are relatively prime, we must have (a+b)/2 divide either a or b.

Suppose (without loss of generality) that (a+b)/2 divides a. Then there is some positive integer k such that a=k(a+b)/2. With a bit of algebra, we get b=a(2-k)/k. To make b a positive integer, we then need k = 1. But k = 1 gives us b = a, which won’t produce three different numbers for arithmetic, geometric, and harmonic means. So there is no solution when a and b are relatively prime.

Since there are no solutions when a and b are relatively prime, we need to consider cases in which they aren’t relatively prime. Let’s let m be the greatest common divisor of a and b. Then we can write a = mc and b = md for some positive and relatively prime integers c and d. The harmonic mean can then be rewritten as (2mcmd)/(mc+md) = 2mcd/(c+d). But c + d has no factors in common with c. (If k were a factor of both c and c + d, then k would also be a factor of d. But then c and d would have a common factor, which we know they don’t.) Similarly, c + d has no factors in common with d. Since 2mcd/(c+d) is an integer, and c + d has no factors in common with c or d, c + d must be a factor of 2m.

The geometric mean of a and b can now be written as $\sqrt{mcmd}=m\sqrt{cd}$. Again, since c and d are relatively prime, they must both be perfect squares to make $\sqrt{cd}$ an integer.

We are trying to minimize the arithmetic mean, which is m(c+d)/2, so we’ll try to minimize both m and (c+d)/2.

Now let’s consider two cases: c + d even or c + d odd:

  1. c + d is even: If c + d is even, then for c + d to be a factor of 2m, we need (c+d)/2 to be a factor of m. Since c and d are both perfect squares, we look for the smallest possible pair of perfect squares that have an even sum. That is 1 and 9. So we need (1+9)/2=5 to be a factor of m. The smallest way to do that is to have m be 5. So both m and (c+d).2 minimize to 5, which would make the arithmetic mean 25. We get this by taking c = 1, d = 9, and m = 5, which makes our starting numbers 5 and 45.

  2. c + d is odd: If c + d is odd, then for c + d to be a factor of 2m, we need c + d to be a factor of m. So we want c + d to be the smallest odd sum of squares. Thus we take 1 and 4. So c + d is 5. But we need m(c+d)/2 to be an integer, and since c + d is odd, we thus need m to be even. So m has both 2 and 5 as factors, so we minimize m by taking m = 10. That gives 25 as the arithmetic mean, as before. We get this by taking c = 1, d = 4, and m = 10, which makes our starting numbers 10 and 40.

We thus find two pairs of numbers that work: 5, 45 and 10. 40. Both produce an arithmetic mean of 25.

Comments

Post a Comment

Popular posts from this blog

Problem of the Day: June 21

A magical castle has n identical rooms, each of which contains m distinguishable doors arranged in a line. In each room i<n, there is one door that takes you to room i+1, and all other doors take you back to room 1. In room n, there is one door that takes you out of the castle, and all other doors take you back to room 1. When you go through a door into a room, you are unable to tell which room of the castle is is (and there is no way of marking rooms). You also cannot tell which doors have been opened before. Determine for which pairs (n,m) there is a strategy that guarantees escape from the castle, and explain the strategy. Edited to add solution: Here's a starting thought: if we could reliably know when we are in room 1, we could solve the problem easily for any n and m. We would then: 1. Enumerate all length n sequences from the alphabet {1,...,m}. 2. For each sequence in that list, (i) get to room 1, and (ii) then follow that sequence. Eventually we'd get to the c...
Read more

Problem of the Day: June 12

Find all positive integers x, y, and z satisfying x 2 + y 2 + z 2 = 2xyz. (As usual, give solutions in comments to this post. On Friday I'll post some combination of my own solution and the most elegant approaches suggested by others.) Edited to add solution : If x 2 + y 2 + z 2 = 2xyz, then x 2 + y 2 + z 2 must be even. Thus there are two cases to consider: 1. One of x, y, z is even and two are odd. 2. All three of x, y, and z are even. Start with case 1. Assume (without loss of generality) that x is even, so x = 2a. Then we have 4a 2 + y 2 + z 2 = 4ayz. But then y 2 + z 2 must be a multiple of 4. But odd numbers are always 1 mod 4, so this is impossible. Thus case 1 can't be achieved. Now consider case 2. We have x=2a, y=2b, and z=2c. Thus 4a 2 + 4b 2 + 4c 2 = 16abc, or a 2 + b 2 + c 2 = 4abc. So let's now focus on this new equation. Again we  need the sum to be even, so we need either one or three even numbers. But one even and two odd...
Read more