Question

N_n is the number of ordered n-tuples (a_1,a_2, ..., a_n) that satisfy 1/a_1 + 1/a_2 + ... + 1/a_n = 1. Is N_10 even or odd?

Answer 1

I'm assuming each \(a_i\) must be an integer correct?

Answer 2

yes, positive integer

Answer 3

Let's say that \(a_1=2\). Then we have that \[{1 \over a_2}+{1 \over a_3}+...+{1 \over a_{10}}={1 \over 2}\]The simplest way to do this, is each \(a_j=18\) so that we have \[{1 \over 18}+{1 \over 18}+...+{1 \over 18}=9 \cdot {1 \over 18}=3\cdot {1 \over 6}\] So for three \(a_1, a_2, a_3\), we need to find how many ways \[{1 \over a_1}+{1 \over a_2}+{1 \over a_3}={1 \over 6}\]

Answer 4

I don't see how this will work. Not every combination will include an a_i = 2, nor 3 a_j's whose inverses add to 1/6. You can't find every combination using this method. Anyways, I think the trick is to look at what the answer is asking for: even or odd, so it probably has to do with pairs.

Answer 5

You're probably right. This is too much of a brute force method.

Answer 6

Let's start with small cases then. If \(n=1\), we obviously only have 1 way to do it.

Answer 7

If \(n=2\), we only have the possibility that \(a_1=a_2=2\) So again, one possibility.

The next step is where it starts getting a little trickier.

Answer 8

If \(n=3\), we have the cases that \[a_1=a_2=a_3=3\]and that two of those \(a_j\) are 4, and the other is 4. Thus, we have 1+3=4 ways to do this if \(n=3\).

Answer 9

I should have said "and the other is 2."

Answer 10

After that, I'm lost for now.

Answer 11

For n=3,
if we have a solution (a1,a2,a3,...,an), then we can generate another one by switching a1 and a2, so since we are looking for even or odd, any solution with a1=/=a2 can be disregarded, so we can set a1=a2, get
1/a1+1/a2+1/a3=2/a1+1/a3=1 so, a1-a1a3+2a3 = 0 => (a1-2)(a3-1)=-2, so the even or odd-ness of the solutions will depend on that of the number of 2 factor combinations of factors of -2, or -1,2; 1,-2, so N_3 is even.
I think that this is extendable to the case with n=10

Answer 12

Anyways, thanks for the help. Just so you know, this is an old Putnam problem... I think I have it figured out now.

Answer 13

Putnam... That would explain it. What year?

Answer 14

I don't remember... 1997 maybe? or '79? I think it was problem A3 that year.

Answer 15

1997 A5

Answer 16

That's an interesting solution I'm getting. I'm not quite following it.

Answer 17

From what I'm understanding, the way I first approached the problem is closest to the best way to do it, but I did it backwards.