Find the number of positive integral solutions of the equation $x_1+x_2+x_3+x_4+x_5=x_1\cdot x_2\cdot x_3\cdot x_4\cdot x_5$

Question

Find the number of positive integral solutions of the equation $x_1+x_2+x_3+x_4+x_5=x_1\cdot x_2\cdot x_3\cdot x_4\cdot x_5$

This is one of the questions from the Indian Institution of Technology Joint Entrance Examination question. I have been struck on this problem for hours.

I was solving some intriguing maths problems on combinatorics. Then I came across this wonderful questions and I was surprised looking at it. Firstly what I thought to give it a try was to Give it a BIJECTION of Distinct Balls distribution in Identical Boxes. For example $x_1+x_2+x_3=20$ can have $(20+3-1)C(3-1)$ solutions (including zero) but how does it work here?

Answer 1

I was solving some intriguing maths problems on combinatorics. Then I came across this wonderful questions and I was surprised looking at it. Firstly what I thought to give it a try was to Give it a BIJECTION of Distinct Balls distribution in Identical Boxes. For example $x_1+x_2+x_3=20$ can have $(20+3-1)C(3-1)$ solutions (including zero) but how does it work here?

Answer 2

$$ 0= x_1 + x_2 + x_3 + x_4 +x_5 - x_1 x_2 x_3 x_4 x_5 \tag{1}$$

An immediate observation I see is that the the above expression is symmetric , so finding one solution will lead to 5! other solutions. Hence, we search unique solution after putting an ordering on our variables:

$$ 1 \leq x_1 \leq x_2 \leq x_3 \leq x_4 \leq x_5$$

From the comment by lulu(*), we can deduce that:

$$ x_1 x_2 x_3 x_4 x_5 \leq 5x_5$$

Or,

$$ x_1 x_2 x_3 x_4 \leq 5 \tag{2}$$

For the max case consider putting $x_4= 5$ , this leads to the following ordering:

$$ x_1 \leq x_2 \leq x_3 \leq x_4 \leq 5 \tag{3}$$

Since the cases are small , we can find them by directly counting as the four number lists which satisfy (2) and (3) :

$$ (x_1,x_2, x_3 , x_4 ) = \{ (1,1,1,1), (1,1,1,2) ,(1,1,1,3), (1,1,1,4) , (1,1,2,2) \} \tag{4}$$

Now consider $(1)$ and rearrange it such that we write $x_5$ as a function of othervariables:

$$ 0 = x_1 + x_2 + x_3 + x_4 + x_5(1-x_1 x_2 x_3 x_4)$$

Or, $$ \frac{x_4 + x_2 + x_3 + x_1 }{x_3 x_4 x_2 x_1 - 1} = x_5$$

Plug in the number lists to the above equation, this will lead us the following set of $(x_1,x_2,x_3,x_4,x_5)$ quintuples : $\{(1,1,1,2,5),(1,1,1,3,2) , (1,1,2,2,3) \}$ (As checked using a Pascal program by @Raffaele )[ I have neglected the cases where plugging in the list gave me negative/ undefined number to satisfy the conditions of the question]

Now, with the solutions, I'll leave it to you to permute them and find the total :^)

---

(*): If the values of $x_1,x_2,x_3,x_4,x_5$ are positive integers, then after putting the ordering, it must be that the sum of rest of numbers is less than five times the sum of the largest number. For example,

$$ 1 +2 +3 +4 +5 \leq 5(5)$$

The sum of first five integers is definitely less than five times the largest integer

Answer 3

The more general question: given size $n$, which sets of positive integers share sum and product, i.e.

$$ \prod\limits_{i=1}^n x_i=\sum\limits_{i=1}^n x_i $$

In addition to the trivial case ($n=1$ yields the set of all integers) we also ignore non-positive $0$ solutions. The $n=2$ case may be written $x_1=\frac{x_2}{x_2-1}$ which yields the only integer with shared sum, product and exponent, namely, $2+2=2\cdot2=2^2=4$. Let's find minimum and maximum values for a brute-force search.

Since $1^{n-1} \cdot x \, =x < n - 1 + x$, start with set $\{1,1, \ldots 2,k\}$. What is $k$?

$$ \begin{align} 2 \cdot k \cdot \prod\limits_{i=1}^{n-2} 1 &= 2 + k + \sum\limits_{i=1}^{n-2} 1\\ k &= n \end{align} $$

Any positive integer satisfies $k=n$, so every set has a solution $\{1,1,\ldots,2,n\}$. Our first test in a brute-force analysis, then, is $\{1,1,...1,3,i\}$ starting with $i=3$. When the product becomes greater than the sum, increment the set, meaning $\{1,1,...1,j,i\}$ becomes $\{1,1,...,2,2,2\}$. If the product is greater than the sum after incrementing the set, all of the sets for a given size $n$ have been found.

Using the same logic as for the "universal" set, it's possible to construct generators for other sets. Let's try $\{1,1,\ldots,3,k\}$:

$$ \begin{align} 3 \cdot k \cdot \prod\limits_{i=1}^{n-2} 1 &= 3 + k + \sum\limits_{i=1}^{n-2} 1\\ k &= \frac{n+1}{2} \end{align} $$

Which means that every set with odd $n$ has a solution $\{1,1, \ldots 3,\frac{n+1}{2}\}$. More generally, if there are two non-$1$ values in the set, they relate by $k=\frac{n-2+r}{r-1}$. A clever algorithm could exploit this relationship by incrementing $r$ to find integer values of $k$, ending when $r>k$.

The process of creating generators can continue ad nauseam with the next example being $\{1,1,...,k,r, \frac{r+k+n-3}{rk-1} \}$, but these generators have diminishing value unless $n$ is quite large because we only have 1 equation with an ever increasing number of unknowns.

If we treat the sets as ordered, the drudgery of permuting each set must also be included, an exercise left to the bored.

A033178