
Problem 3. Find the smallest positive integer $n$, such that there exist $n$ integers $x_{1}, x_{2}, \ldots, x_{n}$ (not necessarily different), with $1 \leq x_{k} \leq n, 1 \leq k \leq n$, and such that

$$
x_{1}+x_{2}+\cdots+x_{n}=\frac{n(n+1)}{2}, \quad \text { and } \quad x_{1} x_{2} \cdots x_{n}=n!
$$

but $\left\{x_{1}, x_{2}, \ldots, x_{n}\right\} \neq\{1,2, \ldots, n\}$.


Solution. If it is possible to find a set of numbers as required for some $n=k$, then it will also be possible for $n=k+1$ (choose $x_{1}, \ldots, x_{k}$ as for $n=k$, and
let $x_{k+1}=k+1$ ). Thus we have to find a positive integer $n$ such that a set as required exists, and prove that such a set does not exist for $n-1$.

For $n=9$ we have $8+6+3=9+4+4$, and $8 \cdot 6 \cdot 3=9 \cdot 4 \cdot 4$, so that a set of numbers as required will exist for all $n \geq 9$. It remains to eliminate $n=8$.

Assume $x_{1}, \ldots, x_{8}$ are numbers that satisfy the conditions of the problem. Since 5 and 7 are primes, and since $2 \cdot 5>8$ and $2 \cdot 7>8$, two of the $x$-numbers have to be equal to 5 and 7 ; without loss of generality we can assume that $x_{1}=5, x_{2}=7$. For the remaining numbers we have $x_{3} x_{4} \cdots x_{8}=2^{7} \cdot 3^{2}$, and $x_{3}+x_{4}+\cdots+x_{8}=36-12=24$. Since $3^{2}=9>8$, it follows that exactly two of the numbers $x_{3}, \ldots, x_{8}$ are divisible by 3 , and the rest of the numbers are powers of 2. There are three possible cases to consider: two of the numbers are equal to 3 ; two of the numbers are equal to 6 ; one number is equal to 3 and another one is equal to 6 .

Case 1. $x_{3}=x_{4}=3$

We then have $x_{5}+x_{6}+x_{7}+x_{8}=18$, and $x_{5} x_{6} x_{7} x_{8}=2^{7}$. The possible powers of 2 with sum 18 are $(1,1,8,8)$ and $(2,4,4,8)$, none of them gives the product $2^{7}$.

Case 2. $x_{3}=3, x_{4}=6$

We have $x_{5}+x_{6}+x_{7}+x_{8}=15$, and $x_{5} x_{6} x_{7} x_{8}=2^{6}$. It is immediate to check that the only possibility for the remaining numbers is $(1,2,4,8)$, which is not allowed, since it gives $\left\{x_{1}, x_{2}, \ldots, x_{8}\right\}=\{1,2, \ldots, 8\}$.

Case 3. $x_{3}=x_{4}=6$

Now we have $x_{5}+x_{6}+x_{7}+x_{8}=12$, and $x_{5} x_{6} x_{7} x_{8}=2^{5}$. The possible powers of 2 which give the correct sum are $(1,1,2,8)$ and $(2,2,4,4)$, but again, they do not give the desired product.

Thus the smallest positive integer with the required property is 9 .
