Let $n$ be the number of ordered $5$-tuples $(a_1,a_2,\ldots,a_5)$ of positive integers such that $\frac1{a_1}+\frac1{a_2}+\ldots+\frac1{a_5}=1$. Is $n$ an even number?
Problem
Source:
Tags: combinatorics
07.04.2021 18:17
For any particular solution, we can permute the solution to form other solutions. Let's do casework on the number of distinct terms in a tuple Case 1: We have one distinct term, so there is only one way to arrange it. There only exists one solution of this form, $(5,5,5,5,5)$. Case 2: Note that for any solution, the number of ways to arrange it will be $\binom{5}{k}$, where $0<k\leq 2$ If $k=2$, then the number of permutations is even, so we can disregard it. If $k=1$, then the number of permutations is odd. Our solutions are in the form $(a,a,a,a,b)$. This means $$\frac{4}{a}+\frac{1}{b}=1$$$$ab-4b-a+4=4$$$$(a-4)(b-1)=4$$There are 3 different solutions of this form corresponding to the 3 factor pairs of $4$ that yield positive solutions. Case 3: There will be $\binom{5}{a,b,c}$, with $a+b+c=5$ and $0<a,b,c$ The only solutions to $a+b+c=5$ are $1,1,3$ and $1,2,2$ Note that $\binom{5}{1,1,3}=20\equiv 0\mod 2$ and $\binom{5}{1,2,2}=30\equiv 0\mod 2$. Hence, there will always be an even number of solutions Case 4: This means that we will have 4 distinct terms with exactly 1 appearing twice. There are $\binom{5}{1,1,1,2}=60\equiv 0\mod 2$ ways to arrange these, so there will be an even number of solutions. Case 5: There will always be $5!=120\equiv 0\mod 2$ ways to arrange any solution forms. Since cases 3,4,5 return an even number of solutions, and cases 1,2 both return an odd number of solutions, $n\equiv 0\mod 2$