### Putnam 1997

Problem A5

Is the number of ordered 10-tuples of positive integers (a1, a2, ... , a10) such that 1/a1 + 1/a2 + ... + 1/a10 = 1 even or odd?

Solution

Easy.

Suppose that there are s unequal values for the ai, with m1 equal to the first value, m2 equal to the second and so on. Then there are n!/(m1! ... ms!) distinct arrangements of the ai. But n!/(m1! ... ms!) = nCmi x integer, so it is only odd if all the nCmi 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.