Putnam 1997 Problem A5 Is the number of ordered 10-tuples of positive integers (a 1 , a 2 , ... , a 10 ) such that 1/a 1 + 1/a 2 + ... + 1/a 10 = 1 even or odd? Solution
: odd. Easy. Suppose that there are s unequal values for the a i , with m 1 equal to the first value, m 2 equal to the second and so on. Then there are n!/(m 1 ! ... m s !) distinct arrangements of the a i . But n!/(m 1 ! ... 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 © John Scholes jscholes@kalva.demon.co.uk 12 Dec 1998