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
Problem
Source: ELMO SL 2018 N1
Tags: number theory, algebra, polynomial, induction
29.06.2018 00:13
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$
29.06.2018 07:13
The Motivation of the proposer must have come from the fact that: Product of $n$ consecutive numbers is divisible by $n!$.
29.06.2018 16:00
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$.
29.06.2018 18:12
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.
29.06.2018 18:24
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\}$.
29.06.2018 18:28
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\}$.
30.06.2018 16:17
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.
07.07.2018 02:19
see here https://artofproblemsolving.com/community/c6h373518p2061559
24.10.2018 19:19
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.
25.10.2018 07:00
Apparently this is also Putnam 1982 B4: https://mks.mff.cuni.cz/kalva/putnam/putn82.html
02.03.2019 23:39
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.
11.06.2021 15:19
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$
26.01.2022 13:56
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$.
06.02.2022 11:45
$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$$
26.03.2022 08:08
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$
30.03.2022 18:11
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.
12.12.2023 06:32
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....
21.01.2024 16:03
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.
16.05.2024 19:35
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.