Putnam 1997/A5 solution

Putnam 1997

Problem A5

Is the number of ordered 10-tuples of positive integers (a₁, a₂, ... , a₁₀) such that 1/a₁ + 1/a₂ + ... + 1/a₁₀ = 1 even or odd?

Solution

Answer: odd.

Easy.

Suppose that there are s unequal values for the a_i, with m₁ equal to the first value, m₂ equal to the second and so on. Then there are n!/(m₁! ... m_s!) distinct arrangements of the a_i. But n!/(m₁! ... m_s!) = nCm_i x integer, so it is only odd if all the nCm_i are odd [where nCm is the binomial coefficient n!/(m!(n-m)!).]

But the only values m in the range 1, 2, ... , 10 for which 10Cm is odd are 2, 8 and 10. Thus we need only consider solutions involving these values (because all the other solutions come in even sized groups). It is easy to see that the only such solutions are:

(1) 1/4 + 1/4 + 1/16 + ... + 1/16,
(2) 1/3 + 1/3 + 1/24 + ... + 1/24,
(3) 1/6 + 1/6 + 1/12 + ... + 1/12,
(4) 1/18 + 1/18 + 1/9 + ... + 1/9,
(5) 1/10 + ... + 1/10.

[With only 10 terms available, the possibilities are 1 = 10/a, 1 = 2/a + 8/b, 1 = 2/a + 2/b + 2/c + 2/d + 2/e, but the latter does not work because 10!/(2!2!2!2!2!) is even. The interesting case is 1 = 2/a + 8/b, which is equivalent to (a - 2)(b - 8) = 16, which gives the solutions shown.] There are an odd number of solutions of each of these (45 for each of (1) - (4) and 1 for (5)), so the total number of solutions is odd.

Putnam 1997