Cute problem! We can take finite differences of $p(x) \overset{\text{def}}{:=} \prod^n_{i=1} (x+a_i)$ to obtain $p(0) \mid n!$. Now this can only be possible when $\{a_1, \dots, a_n\}$ is a permutation of $\{1, 2, \dots, n\}$. Finally, for this particular set, we know for a fact that binomial coefficients are a thing. $\blacksquare$

The Motivation of the proposer must have come from the fact that: Product of $n$ consecutive numbers is divisible by $n!$.

Here's another solution: Let $a_1<a_2<...<a_n$, $P=a_1a_2\cdots a_n$ and $Q$ be some multiple of $P$ that is greater than $n$. Now, we use strong induction to prove $a_k=k$. Firstly, note that $$0\equiv \prod_{i=1}^n (Q-1+a_i) \equiv \prod_{i=1}^n (a_i-1) \mod P.$$Since $\prod_{i=1}^n (a_i-1)<P$ we have $$\prod_{i=1}^n (a_i-1)=0,$$so $a_1=1$. Now, assume $a_i=i$ for $i=1,2,...,k-1$. Similar to above we get $$0\equiv \prod_{i=1}^n (Q-k+a_i) \equiv \prod_{i=1}^n (a_i-k) \mod P,$$but since $|\prod_{i=1}^n (a_i-k)|=|\prod_{i=1}^{k-1} a_i \prod_{j=k}^n (a_j-k)|<P$ we have $$\prod_{i=1}^n (a_i-k)=0,$$so $a_k=k$.

anantmudgal09 wrote: Cute problem! We can take finite differences of $p(x) \overset{\text{def}}{:=} \prod^n_{i=1} (x+a_i)$ to obtain $p(0) \mid n!$. Now this can only be possible when $\{a_1, \dots, a_n\}$ is a permutation of $\{1, 2, \dots, n\}$. Finally, for this particular set, we know for a fact that binomial coefficients are a thing. $\blacksquare$ I'm new to this finite difference stuff so I'd be really appreciated if anyone can explain why should taking the $n$th finite difference of $p(x)$ implies $p(0) \mid n!$. Thanks in advance.

Let $P(x)=\frac{(x+a_1)...(x+a_n)}{\prod^n_{i=1} a_i}$. Since it's an integer polynomial, it can be written as sum of binomials in $x$, so looking at the coefficient of $x^n$ we get $\frac{1}{\prod^n_{i=1} a_i}=\frac{\alpha_n}{n!}$, so $\prod^n_{i=1} a_i$ divides $n!$. By size argument, the only sets that work are $\{1,2,...,n\}$.

Alternatively, let $a_1<a_2<\cdots<a_n$, wlog. Notice that, $P\triangleq a_1a_2\cdots a_n>n!>n$. Now, look at $x=a_1a_2\cdots a_n-1$, $(x+a_i)\equiv a_i-1\pmod{a_1a_2\cdots a_n}$, hence, the product is $(a_1-1)\cdots (a_n-1)$, hence, $a_1=1$. Next, insert $x=a_1a_2\cdots a_n-2$, and obtain $a_2\cdots a_n \mid (x+1)(x+a_2)\cdots (x+a_n)\equiv (-1)(a_2-2)\cdots (a_n-2)\pmod{a_1a_2\cdots a_n}$, hence, $a_2=2$. Continuing in this manner (namely, inserting $x=a_1a_2\cdots a_n-3$, $x=a_1a_2\cdots a_n-4$, $\dots$, $x=a_1a_2\cdots a_n-n$) yields $\{a_1,\dots,a_n\}=\{1,2,\dots,n\}$.

a1267ab wrote: Determine all nonempty finite sets of positive integers $\{a_1, \dots, a_n\}$ such that $a_1 \cdots a_n$ divides $(x + a_1) \cdots (x + a_n)$ for every positive integer $x$. Proposed by Ankan Bhattacharya I believe you should add that all $a_i's$ are distinct.

see here https://artofproblemsolving.com/community/c6h373518p2061559

This is an old problem and it appeared in number theory concepts and problems by titu the sourse is writtren putnam there but the year isn't mentioned.

Apparently this is also Putnam 1982 B4: https://mks.mff.cuni.cz/kalva/putnam/putn82.html

Clearly $\{1,\ldots,n\}$ works. We'll show that nothing else works. Let $f(x)=(x+a_1)\cdots(x+a_n)$. In fact, all we need is that $f$ takes integer values for integer $x$, $f(0)=a_1\cdots a_n$, and that $f$ is monic. Use the binomial basis to write \[f(x)=a_1\cdots a_n+b_1\binom{x}{1}+\cdots+b_{n-1}\binom{x}{n-1}+n!\binom{x}{n}.\]Let $\Delta g(x)=g(x+1)-g(x)$. Then, it is easy to see that $\Delta^n f(x)=n!$. But this is an integer combination of integer inputs to $f$, so we must have $a_1\cdots a_n\mid n!$, so in particular, \[a_1\cdots a_n\le n!.\]Thus, we have $\{a_1,\ldots,a_n\}=\{1,\ldots,n\}$ since all the $a_i$ are distinct.

Here's a solution that doesn't have anything to do with polynomials. The answer is when $\{a_1,\ldots,a_n\}=\{1,2,\ldots,n\}$, in which case $\frac{(x+a_1)\cdots (x+a_n)}{a_1\cdots a_n}=\binom{x+n}{n} \in \mathbb{Z}$. I will now show nothing else works. Let the polynomial be $f(x)$ and the product $a_1\cdots a_n$ be $P$, where $n$ is fixed. The key claim is the following. Claim: For every prime $p$, we require $\nu_p(P) \leq \sum_{k=1}^\infty \left \lfloor \frac{n}{p^k}\right\rfloor$. Proof: I will show that we can select $x$ such that for all $k \geq 1$, at most $\lfloor n/p^k\rfloor$ elements of $\{x+a_1,\ldots,x+a_n\}$ are divisible by $p^k$, which clearly establishes the result. This is by repeated applications of pigeonhole: we can clearly pick the value of $x \pmod{p}$ such that $\lfloor n/p\rfloor$ elements of $\{x+a_1,\ldots,x+a_n\}$ are divisible by $p$. Now consider $x \pmod{p^2}$, of which there are $p$ possible residues (since $x \pmod{p}$ is fixed). Again by pigeonhole, there exists a mod $p^2$ class such that at most $$\left\lfloor \frac{\lfloor n/p\rfloor}{p}\right\rfloor \leq \left\lfloor \frac{n}{p^2}\right\rfloor$$elements in $\{x+a_1,\ldots,x+a_n\}$ are divisible by $p^2$. Repeating this infinitely gives the result. $\blacksquare$ To finish, note that from the key claim, we have $$P=\prod_{p \text{ prime}}p^{\nu_p(P)}\leq \prod_{p \text{ prime}} p^{\sum_{k=1}^\infty \lfloor n/p^k\rfloor}.$$On the other hand, by Legendre we have $$n!=\prod_{p\text{ prime}} p^{\sum_{k=1}^\infty \lfloor n/p^k\rfloor},$$so $P \leq n!$. However, we clearly must have $P \geq n!$, since $P$ is the product of $n$ distinct positive integers. This implies that $P=n!$, from which we clearly obtain the solution set and only the solution set (if anything in $\{a_1,\ldots,a_n\}$ is larger than $n$, we obtain a simple size contradiction). $\blacksquare$

Since we deal with modulo ${a_1a_2\cdots a_n}$ we can take negative $x$ also (i.e. taking $x=-k$ and $x=-k+ta_1a_2\cdots a_n$ gives same result). $\mathbf{Claim 1:a_1=1. }$ $\mathbf{Proof:}$ Assume $a_1\ne 1$. So $a_1>$. Now taking $x=-a_1+1$ gives that $a_1a_2\cdots a_n\mid 1 \cdot (a_2-a_1+1)(a_3-a_1+1)\cdots (a_n-a_1+1)$. But $0<1 \cdot (a_2-a_1+1)(a_3-a_1+1)\cdots (a_n-a_1+1)<a_1a_2\cdots a_n$ which is contradiction $\square.$ $\mathbf{Claim 2:a_i=i}$ for all $1\le i \le 2018.$ $\mathbf{Proof:}$ I will Incudt on $i$. We have already prove $i=1$ case. Assume $a_i=i$ for all $i=1,2,\cdots , m-1$ and $a_m\ne m$. So $a_m>m$. Taking $x=-m$ gives that $$(m-1)!\cdot a_m\cdots a_n \mid (-1)^{m-1}\cdot (m-1)! \cdot (a_m-m)\cdots (a_n-m) \implies a_m\cdots a_n \mid (a_m-m)\cdots (a_n-m)$$But $0< (a_m-m)\cdots (a_n-m)<a_m\cdots a_n$ which is contradiction$\square$. $\mathbf{Claim 3: (1,2,...,n) }$ works. $\mathbf{Proof:}$ $(x+1)\cdot (x+2)\cdots (x+n)=$ $\binom {n+x}{x}\cdot $ $\cdot n!$ which is obviously divisible by $n!$ $\blacksquare$.

$a_1 \leq a_2 \leq ... \leq a_n$ $A =a_1a_2...a_n$ $x \implies -1$mod($A$) $\implies A|(a_1-1)(a_2-1)...(a_n-1) \implies a_1 = 1$ Similaritiy $a_k =k$ $$\binom{x+n}{n} \in Z$$

WLOG $a_1\le a_2\le\dots\le a_n$ as permutations are equivalent to the original set in $\frac{(x+a_1)\cdots(x+a_n)}{a_1\cdots a_n}.$ Claim: $a_i=i$ is necessary. Proof. We proceed by strong induction. For our base case $n=1,$ $a_1\mid x+a_1$ so $a_1\mid x$ for all integers $x.$ Hence, $a_1\mid 1$ and $a_1=1.$ Suppose $a_i=i$ for $a_1,a_2,\dots,a_{k-1}.$ Then, $$\frac{(x+a_1)\cdots(x+a_k)}{a_1\cdots a_k}=\frac{(x+1)\cdots(x+k-1)(x+a_k)}{(k-1)!}=\frac{(x+k-1)!(x+a_k)}{(k-1)!x!a_k}=\binom{x+k-1}{k-1}\frac{x+a_k}{a_k}$$so $a_k\mid x+a_k.$ Hence, $a_k=1$ and our induction is complete. $\blacksquare$ Claim: $a_i=i$ is sufficient. Proof. If $a_i=i,$ we have $$\frac{(x+a_1)\cdots(x+a_k)}{a_1\cdots a_k}=\frac{(x+1)\cdots(x+n)}{n!}=\frac{(x+n)!}{x!n!}=\binom{x+n}{n}$$is an integer. $\blacksquare$ Hence, our solutions are permutations of $\{1,2,\dots,n\}.$ $\square$

Claim: $a_1\cdots a_n\mid n!$ Let $f(x)=\prod_{i=1}^n(x+a_i)$ and let $g:\mathbb N^2\to\mathbb Z$ be the "finite differences" function of $p$ defined by $g(1,b)=p(b)$ and $g(a+1,b)=g(a,b+1)-g(a,b)$. Since $a_1\cdots a_n\mid f(x)$, $a_1\cdots a_n$ also divides $g(n+1,1)$. So the subclaim is that $g(n+1,1)=n!$. Let's write: $$f(a,b)=k_0+k_1b+\ldots+k_{n-1}b^{n-1}+n!\binom bn$$where $a=1$ and $k_0,\ldots,k_{n-1}$ are some integers. Increasing $a$ by $1$ reduces the degree of $f(a,b)$ (as a polynomial in $b$) but keeps the coefficient of $\binom bn$ the same. Then $g(n+1,1)=n!$, so the claim is proven. WLOG $a_1<\ldots<a_n$. Then: $$n!\le a_1\cdots(a_1+n-1)\le a_1\cdots a_n\le n!$$so equality holds and $a_k=k$ for each $k$. Finally, $n!\mid\binom{x+n}x\cdot n!=\prod_{i=1}^n(x+i)$ so this set works.

The answer is $\{1,2, \dots, n \}$ only. This works because it's the choose function which is an integer always. Define $P = a_1 a_2 \cdots a_n$ and WLOG $a_1 < a_2 < \dots < a_n$. We prove with (strong) induction that $a_i = i$. Our inductive step does not require $i>1$ so it is our base case too. Inductive step: to prove $a_i = i$, let $x = P - i$. Then our expression taken modulo $P$ equals \begin{align*}& \left[(1-i)(2-i) \cdots (i-1 - i) \right] \cdot \left[(a_i - i)(a_{i+1} - i) \cdots (a_n - i) \right] \\ \equiv ~ & \pm \left[ 1 \cdot 2 \cdots (i-1) \right] \cdot \left[(a_i - i)(a_{i+1} - i) \cdots (a_n - i) \right] \\ \equiv ~ & \pm a_1 \cdot a_2 \cdots a_{i-1} \cdot (a_i - i)(a_{i+1} - i) \cdots (a_n - i) \pmod{P}. \end{align*}If $a_i > i$ we have \[ 0< \left|a_1 \cdot a_2 \cdots a_{i-1} \cdot (a_i - i)(a_{i+1} - i) \cdots (a_n - i) \right| < |a_1 \cdot a_2 \cdots a_n| = P.\]This is a contradiction so $i-1 = a_{i-1} < a_i \leq i$, hence $a_i = i$. What happens when you allow duplicates....

math_pi_rate wrote: a1267ab wrote: Determine all nonempty finite sets of positive integers $\{a_1, \dots, a_n\}$ such that $a_1 \cdots a_n$ divides $(x + a_1) \cdots (x + a_n)$ for every positive integer $x$. Proposed by Ankan Bhattacharya I believe you should add that all $a_i's$ are distinct. By definition, a set has all of its elements pairwise distinct.

Let $a_1 < a_2 < a_3 < \cdots < a_n,$ and $P = \prod a_i.$ Now we use induction to show that $a_i = i$ for all $i$. First, note that \[0 \equiv \prod(P - 1 + a_i) \equiv \prod(a_i - 1) \pmod P.\] Then as $\prod(a_i - 1) < P,$ we actually have $\prod(a_i - 1) = 0.$ So $a_1 = 1.$ Assume it is true for $i \leq k-1$. Then, for $k$, notice \[0 \equiv \prod(P - k + a_i) \equiv \prod_{i \leq k-1} a_i \prod_{i > k-1} (a_i - k) \pmod P.\] Since, $\prod_{i \leq k-1} a_i \prod_{i > k-1} (a_i - k) < P$, we again see that $\prod_{i > k-1} (a_i - k) = 0 \implies a_k = k$ completing the induction.