so it should be a subset of the {1,2,....,n}

@above, it doesn't have to be a subset of $(1,2,3 \cdots ,n)$. .. But I don't think that such a set is possible, if $1 \le k \le n$. Because in order to replace some numbers, the product must mean the same, and there needs to be the same amount of numbers in the set.

djb86 wrote: Find the smallest positive integer $n$, such that there exist $n$ integers $x_1, x_2, \dots , x_n$ (not necessarily different), with $1\le x_k\le n$, $1\le k\le n$, and such that \[x_1 + x_2 + \cdots + x_n =\frac{n(n + 1)}{2}\quad\text{, and }x_1x_2 \cdots x_n = n!,\] but $\{x_1, x_2, \dots , x_n\} \ne \{1, 2, \dots , n\}$. $n=16$ is possible : we can choose $\{2,2,4,4,4,4,4,6,9,11,13,14,14,15,15,15\}$ It remains to show that this is the smallest.

djb86 wrote: Find the smallest positive integer $n$, such that there exist $n$ integers $x_1, x_2, \dots , x_n$ (not necessarily different), with $1\le x_k\le n$, $1\le k\le n$, and such that \[x_1 + x_2 + \cdots + x_n =\frac{n(n + 1)}{2}\quad\text{, and }x_1x_2 \cdots x_n = n!,\] but $\{x_1, x_2, \dots , x_n\} \ne \{1, 2, \dots , n\}$. In fact, $n=9$ is possible : $\{1,2,4,4,4,5,7,9,9\}$ and I think it's the smallest (proof later)

In fact $n=8$ is also possible: 1,2,4,4,4,5,7,9

manuel153 wrote: In fact $n=8$ is also possible: 1,2,4,4,4,5,7,9 Wrong : with $n=8$, you need all $x_k\le 8$ and so you can not use $9$.

Pretty cute problem, but the proof is kind of tiresome, unless there's a better solution that I'm missing (which is quite possible). pco wrote: In fact, $n=9$ is possible : $\{1,2,4,4,4,5,7,9,9\}$ Let us now prove that $n \le 8$ is not possible. It suffices to show $n=8$; otherwise we can just add in the numbers $n+1, n+2, \cdots, 8$ to the sequence. Consider a good sequence $\left\{ x_i \right\}$. Since $\textstyle\prod_{i=1}^{8} x_i = 8!$ and $x_i \le 8$ for all $i$, it is easy to deduce that $\left\{ 5,7 \right\}$ appear exactly once in the $x_i$ (since no multiple may appear). Also, there cannot be a $9$, so the two factors of $3$ in $8!$ must belong to different elements. Since there are no other primes less than $8$, we may assume now assume that, up to permutation, we have \[ x_1=2^a \quad x_2 = 2^b \quad x_3 = 2^c \quad x_4 = 2^d \] and \[ x_5 = 3 \cdot 2^m \quad x_6 = 3 \cdot 2^n \quad x_7 = 5 \quad x_8 = 7. \] So, we want to find $a,b,c,d,m,n$ nonnegative integers, with $0 \le a \le b \le c \le d \le 3$ and $0 \le m \le n \le 1$ such that \[ 2^a + 2^b + 2^c + 2^d + 3 \cdot 2^m + 3 \cdot 2^n = 36 - 5 - 7 = 24, \] and by considering exponents, \[ a+b+c+d+m+n = 7. \] First, taking modulo $3$, we observe that $(-1)^a + (-1)^b + (-1)^c + (-1)^d \equiv 0 \pmod{3}$. It is easy to check that this implies that exactly two of $a,b,c,d$ are even. In particular, $a+b+c+d$ is even, so $m+n=7-(a+b+c+d)$ is odd. This forces $(m,n) = (0,1)$. Now, we get that \[ 2^a + 2^b + 2^c + 2^d = 15 \quad \text{and} \quad a+b+c+d=6. \] Looking at the first equation mod 2, we see that either one or three of $a,b,c,d$ are zero (so that $2^a$ is odd.) Using the fact that exactly two of $a,b,c,d$ are even, however, it is easy to force $a=0$ and $bcd \neq 0$. From here, it is just a matter of casework to get $(b,c,d) = (2,3,4)$. So $n=9$ is the answer.