Show that there are no 2-tuples $ (x,y)$ of positive integers satisfying the equation $ (x+1) (x+2)\cdots (x+2014)= (y+1) (y+2)\cdots (y+4028).$
Problem
Source: China Nanjing , 23 Mar 2014
Tags: number theory proposed, number theory, Diophantine equation, China TST
SCP
07.04.2014 18:40
ideas Remark that $x>2^{1200}-2014$ as the number of factors $2$ in the $RHS$ is at least $2014+1007+503$ . If $x=y^2+4029y+2705137$ the RHS is smaller, for $x>y^2+4029y+2705138$ the RHS > LHS.
MathPanda1
01.02.2015 18:12
Does anyone have a solution?
MathPanda1
08.03.2015 17:35
Could a generalization to this problem be: determine all positive integers $n$ such that $ (x+1) (x+2)\cdots (x+n)= (y+1) (y+2)\cdots (y+n)$ has a solution? However, for the China TST problem, would it help to look at the exponent of specific primes $p$ (e.g. 2,3,5, 4027) in the LHS and the RHS and forcing them to equate by setting the $x+i$'s to be divisible by $p^{(...)}$?
MathPanda1
19.03.2015 01:15
Just wondering, does the China Math Olympiads have an official website? Thank you very much!
61plus
19.03.2015 17:27
probably not. most problems I find are on blogs or online forums.
MathPanda1
12.04.2016 06:43
Did anyone get this problem during the test? I am very curious to see a solution to this beautiful and difficult problem!
First
12.04.2016 06:45
You do realize that very few people in the world could do this under timed conditions.
MathPanda1
15.04.2016 04:55
Does anyone have a solution to this problem? Thank you very much to all your help!
rmrf
15.04.2016 05:53
MathPanda1 wrote: Does anyone have a solution to this problem? Thank you very much to all your help! I have a solution to this problem! But I don't really want to help
sohappy
15.04.2016 05:57
rmrf wrote: MathPanda1 wrote: Does anyone have a solution to this problem? Thank you very much to all your help! I have a solution to this problem! But I don't really want to help why?
qwerty137
15.04.2016 06:03
Hello, he lives in USA, has USAMO in 5 days, does not want spend energy typing solution
biomathematics
15.04.2016 07:47
qwerty137 wrote: Hello, he lives in USA, has USAMO in 5 days, does not want spend energy typing solution rmrf wrote: MathPanda1 wrote: Does anyone have a solution to this problem? Thank you very much to all your help! I have a solution to this problem! But I don't really want to help What was the point of writing this then?
pavel kozlov
15.04.2016 13:22
That's a signal for you solution will be in approximately 1 week
MathPanda1
28.04.2016 02:59
Now that USA(J)MO is finished, could you post your solution please, rmrf? Thank you very much for all your help!
MathPanda1
24.05.2016 22:06
Anyone? Thanks!
rmrf
25.05.2016 07:42
Dear MathPanda1, It seem you ask many question but do not answer when other asked your. Always looking for solution to problems! Maybe slow down and make sure you can solving the problems you get solution to. You can start with this problem here
qwerty137
01.09.2016 04:28
Alright MathPanda1, if you're still interested in a complete solution (after about 3 months), here you go.
First, we note that \[v_2\left(\prod_{j=1}^{4028}(y+j)\right)\ge\left\lfloor\frac{4028}{2}\right\rfloor+\left\lfloor\frac{4028}{4}\right\rfloor+\cdots+\left\lfloor\frac{4028}{2048}\right\rfloor.\]Thus, we see that $x\ge 2^{2014}-2014$ or else
\[v_2\left(\prod_{i=1}^{2014}(x+i)\right)<\left(\left\lfloor\frac{2014}{2}\right\rfloor+\left\lfloor\frac{2014}{4}\right\rfloor+\cdots+\left\lfloor\frac{2014}{1024}\right\rfloor+9\right)+2004<v_2\left(\prod_{j=1}^{4028}(y+j)\right).\]Thus, since $x\ge 2^{2014}-2014>2^{2013}\sqrt{2}$, we have that $y\ge 2^{1006}-4029$ or else
\[\prod_{j=1}^{4028}(y+j)<2^{1006\times4028}<2^{1007\times4027}<\prod_{i=1}^{2014}(x+i).\]
(Really, all we need is some large bound on $x,y$- it can be pretty loose.)
Now, if we can bound $x$ between two quadratics in $y$ that differ by $1$, we can reach a contradiction (as that's saying that $x$ is an integer between two consecutive integers). Thus, we compute the first few coefficients of the RHS and get
\[\prod_{j=1}^{4028}(y+j)=\prod_{j=1}^{2014}(y^2+4029y+j(4029-j))\]\[=y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+\left(\sum_{j=1}^{2014}j(4029-j)\right)\right)y^{4026}+\cdots\]\[=y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+(2014\times2015\times1343)\right)y^{4026}+\cdots\]
First, we note that the linear term for our quadratics must be $4029y$, or else our difference will have a term with $y$ in it and $4029$ is the only value we can have so that the $y^{4027}$ coefficient in the LHS will end up matching the $y^{4027}$ coefficient in the RHS. Thus, we have $y^2+4029y+c$ for some value of $c$, and plugging that in for $x$, we get
\[\prod_{i=1}^{2014}(y^2+4029y+c+i)=y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+\left(\sum_{j=1}^{2014}c+i\right)\right)y^{4026}+\cdots\]\[=y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+(1007\times2015)+ 2014c\right)y^{4026}+\cdots\]
"Solving" for $c$, we get
\[1007\times2015+2014c=2014\times2015\times1343\]\[\implies 2014c=2014\times2015\times1342.5\]\[\implies c=2015\times1342.5=2705137.5,\]so we want to prove that $y^2+4029y+2705137<x<y^2+4029y+2705138$.
Now, we note that since the coefficients of $(y+4029)^{4028}=(y^2+8058y+16232841)^{2014}$ are greater than the coefficients of $\prod_{j=1}^{4028}(y+j)$ and $\prod_{i=1}^{2014}(y^2+4029y+c+i)$ when $c=2705137$, we have that, for all $x,y\ge 0$,
\[\prod_{j=1}^{4028}(y+j)-\left(y^{4028}+2014\times4029y^{4027}+\left(blah_1\right)y^{4026}\right)<(y+4029)^{4028}-(y^{4028}+4028\times4029y^{4027}+(blah)y^{4026}),\]\[\prod_{i=1}^{2014}(y^2+4029y+c+i)-\left(y^{4028}+2014\times4029y^{4027}+\left(blah_2\right)y^{4026}\right)<(y+4029)^{4028}-(y^{4028}+4028\times4029y^{4027}+(blah)y^{4026})\](shortened or else it'll be very condensed).
Lemma 1: For all integers $1\le n\le 4028$, the coefficient of $x^{n-1}$ in $(y+4029)^{4028}$ is less than $4029^2$ times the coefficient of $x^{n}$ in $(y+4029)^{4028}$.
Proof:
\[4029^{4029-n}\binom{4028}{n-1}=4029\times\frac{n}{4029-n}\times4029^{4028-n}\binom{4028}{n}.\]Now, since $\frac{n}{4029-n}=\frac{4029}{4029-n}-1$ is maximized, for $1\le n\le 4028$, when $n=4028$, the maximum value for $\frac{n}{4029-n}$ in this case is $4028$, so
\[4029\times\frac{n}{4029-n}\times4029^{4028-n}\binom{4028}{n}\le 4029\times4028\times4029^{4028-n}\binom{4028}{n}<4029^2\left(4029^{4028-n}\binom{4028}{n}\right)\]\[\implies 4029^{4029-n}\binom{4028}{n-1}<4029^2\left(4029^{4028-n}\binom{4028}{n}\right),\]completing the proof.
Thus, since $y\ge 2^{1006}-4029>>4029^6+4029^2$, we have
\[(y+4029)^{4028}-(y^{4028}+4028\times4029y^{4027}+(blah)y^{4026})=\sum_{k=0}^{4025}\left(\binom{4028}{k}4029^{4028-k}\right)y^k\]\[<\sum_{k=0}^{4025}4029^{8056-2k}y^k\]\[=y^{4026}\sum_{k=0}^{4025}4029^4\times\left(\frac{4029^2}{y}\right)^{4026-k}\]\[<y^{4026}\times4029^4\times\frac{4029^2}{y-4029^2}<y^{4026}.\]
Therefore, we have that
\[\prod_{j=1}^{4028}(y+j)-\left(y^{4028}+2014\times4029y^{4027}+\left(blah_1\right)y^{4026}\right)<y^{4026},\]\[\prod_{i=1}^{2014}(y^2+4029y+c+i)-\left(y^{4028}+2014\times4029y^{4027}+\left(blah_2\right)y^{4026}\right)<y^{4026}\]for $c=2705137$.
Thus, if $c=2705137$,
\[\prod_{i=1}^{2014}(y^2+4029y+c+i)=y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+(1007\times2015)+2014c\right)y^{4026}+\cdots\]\[<y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+(1007\times2015)+2014c+1\right)y^{4026}\]\[<y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+(2014\times2015\times1343)\right)y^{4026}<\prod_{j=1}^{4028}(y+j)\]\[\implies LHS<RHS,\]
and if $c=2705138$,
\[\prod_{j=1}^{4028}(y+j)=y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+(2014\times2015\times1343)\right)y^{4026}+\cdots\]\[<y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+(2014\times2015\times1343)+1\right)y^{4026}\]\[<y^{4028}+2014\times4029y^{4027}+\left(\binom{2014}{2}4029^2+(1007\times2015)+2014c\right)y^{4026}<\prod_{i=1}^{2014}(y^2+4029y+c+i)\]\[\implies RHS<LHS.\]
Therefore, $y^2+4029y+2705137<x<y^2+4029y+2705138$, but $x$ is an integer, contradiction. Therefore, there are no solutions.
MathPanda1
01.09.2016 04:43
Thank you so much for posting a complete solution to this difficult problem qwerty137! I really appreciate it.
CQYIMO42
19.02.2017 06:05
@MathPanda1, here is another solution, as promised.
For $n=2^k \cdot m$ ($k$ being a nonnegative integer, $m$ being odd), denote $v(n)=2^k.$
Now for the sake of contradiction, let $(x,y)$ be 2-tuples of positive integer solutions satisfying the equation.
Let $$v(x+i)=\max\limits_{1 \le j \le 2014} \{v(x+j)\},$$then for $$1 \le j \le 2014, j \neq i,$$
there is $$v(x+j)=v(x+i+(j-i))=v(j-i),$$
so $$v\left(\prod\limits_{1 \le j \le 2014, j \neq i}(x+j)\right)=v((2014-j)!\cdot(j-i)!) \le v(2013!),$$
also, since $\prod\limits_{j=1}^{2014}(x+j)=\prod\limits_{j=1}^{4028}(y+j)$ is a multiple of $4028!$, it follows that $$x+i \ge v(x+i) \ge v\left(\frac{4028!}{2013!}\right) > 2^{1007},$$
thus, $$x > 2^{1006} \Rightarrow (y+4028)^{4028} > \prod_{j=1}^{4028}(y+j) = \prod_{j=1}^{2014}(x+j) > 2^{1006 \cdot 1004},$$
then we obtain $y+4028 > 2^{503}$, therefore $y>2^{502}.$
Lemma:
Let $0 \le x_i < \frac{1}{2}$ where $1 \le i \le n$,
if $$x=\frac{1}{n}\sum\limits_{i=1}^{n}x_i, y = 2 \max\limits_{1 \le i \le n} \{{x_i}^2\},$$
then $$1-x \ge \left(\prod\limits_{i=i}^n(1-x_i)\right)^{\frac{1}{n}} \ge 1-x-y.$$Proof of the lemma:
By AM-GM, the LHS inequality holds true.
Now completing the proof of the RHS inequality:
\begin{align*} \left(\prod_{i=1}^n(1-x_i)\right)^{\frac{1}{n}} & \ge \frac{n}{\sum\limits_{i=1}^n \frac{1}{1-x_i}} \ge \frac{n}{\sum\limits_{i=1}^n(1+x_i+2{x_i}^2)} \\ & = \frac{n}{n+nx+2 \sum\limits_{i=1}^n {x_i}^2} \\ & \ge \frac{1}{1+x+y} \ge 1-x-y,\\ \end{align*}and that completes the proof of the lemma.//
Now let $w=x+2015 > 2^{1007}, z=y+\frac{4029}{2}>2^{502},$
then the original equation can be written as: \begin{align*}w \cdot \left(\left(1-\frac{1}{w}\right)\left(1-\frac{2}{w}\right) \cdots \left(1-\frac{2014}{w}\right)\right)^{\frac{1}{2014}} & \\= z^2 \cdot \left(\left(1-\frac{1}{4z^2}\right)\left(1-\frac{9}{4z^2}\right) \cdots \left(1-\frac{4027^2}{4z^2}\right)\right)^{\frac{1}{2014}}. \end{align*}From the Lemma, we learn that \begin{align*}w\left(1-\frac{2015}{2w}\right) & > w\cdot\left(\left(1-\frac{1}{w}\right)\left(1-\frac{2}{w}\right)\cdots\left(1-\frac{2014}{w}\right)\right)^{\frac{1}{2014}} \\ & > w\left(1-\frac{2015}{2w}-\frac{2\cdot 2014^2}{w^2}\right) \\ & > w\left(1-\frac{2015}{2w}\right)-\frac{1}{8}, \end{align*}Therefore the decimal part of $w\left(\left(1-\frac{1}{w}\right)\left(1-\frac{2}{w}\right)\cdots\left(1-\frac{2014}{w}\right)\right)^{\frac{1}{2014}}$ is within the interval $\left(\frac{3}{8}, \frac{1}{2}\right).$
Also from the Lemma, \begin{align*}z^2\left(1-\frac{1^2+3^2+\cdots+4027^2}{4z^2\cdot 2014}\right) & >z^2\left(\left(1-\frac{1}{4z^2}\right)\left(1-\frac{9}{4z^2}\right)\cdots \left(1-\frac{4027^2}{4z^2}\right)\right)^{\frac{1}{2014}} \\ & >z^2\cdot \left(1-\frac{1^2+3^2+\cdots+4027^2}{4z^2\cdot 2014}-\frac{2\cdot 4027^4}{(4z^2)^2}\right), \end{align*}so \begin{align*}z^2-\frac{4\cdot 2014^2-1}{12} &>z^2\left(\left(1-\frac{1}{4z^2}\right)\left(1-\frac{9}{4z^2}\right)\cdots \left(1-\frac{4027^2}{4z^2}\right)\right)^{\frac{1}{2014}} \\ & >z^2-\frac{4\cdot 2014^2-1}{12}-\frac{4027^4}{8z^2} \\ & >z^2-\frac{4\cdot 2014^2-1}{12}-\frac{1}{8}. \end{align*}Since $z^2-\frac{4\cdot 2014^2-1}{12}$ is an integer, the decimal part of $z^2\cdot\left(\left(1-\frac{1}{4z^2}\right)\left(1-\frac{9}{4x^2}\right)\cdots \left(1-\frac{4027^2}{4z^2}\right)\right)^{\frac{1}{2014}}$ is within the interval $\left(\frac{7}{8}, 1\right)$, which is obviously a contradiction.
$\therefore$ the equation $\prod\limits_{j=1}^{2014}(x+j)=\prod\limits_{j=1}^{4028}(y+j)$ has no 2-tuples integer solutions $(x,y)$.
$Q.E.D.$
mathcool2009
09.10.2017 05:17
Assume for the sake of contradiction that such $(x,y)$ does exist.
Note that we have \[(y+1)(y+2)\cdots (y+4028) = ((y+1)(y+4028))((y+2)(y+4027))\cdots ((y+2014)(y+2015))\]
\[ = (y^2 + 4029y + 1\cdot 4028)(y^2 + 4029y + 2 \cdot 4027)\cdots (y^2 +4029y + 2014\cdot 2015)\]
Now observe that \[S = 1\cdot 4028 + 2\cdot 4027 + \cdots + 2014\cdot 2015 = \frac{1}{2} \sum_{i=1}^{4028} i(4029-i) = \frac{1}{2}(4029 \cdot \frac{4028\cdot 4029}{2} - \frac{4028 \cdot 4029 \cdot 8057}{6})\]
\[ = \frac{1}{2}(\frac{4028 \cdot 4029}{6})(3 \cdot 4029 - 8057) = \frac{1}{2}(\frac{4028 \cdot 4029}{6})(4030) = 2014 \cdot 1343 \cdot 2015\]
It follows that \[(y^2 + 4029y + 1\cdot 4028)(y^2 + 4029y + 2 \cdot 4027)\cdots (y^2 +4029y + 2014\cdot 2015) \]\[< (y^2 + 4029y + (b-1007))(y^2+4029y+(b-1006))\cdots (y^2+4029y + (b-1))(y^2 + 4029y + (b+1))\cdots (y^2 + 4029y + (b+1007))\]where $b = 1343 \cdot 2015$. Thus we have $x \le y^2 + 4029y + c$, where $c = b-1008 = 1343 \cdot 2015 - 1008$.
Note that $4028! | (y+1)(y+2) \cdots (y+4028)$, so $4028! | (x+1)(x+2) \cdots (x+2014)$.
Let $\nu_p (z)$ denote the largest $k$ such that $p^k | z$, and let $s_p (z)$ denote the sum of the digits of $z$ when expressed in base $p$. Note that $\nu_2 (4028!) = 4028 - s_2 (4028) = 4028 - 9 = 4019$. Thus $2^{4019} | (x+1)(x+2) \cdots (x+2014)$.
Let's try to show that one of the numbers $x+1, x+2, \cdots, x+2014$ is divisible by $2^{2015}$. We see that we have at most $\lceil \frac{2014}{2^k} \rceil$ numbers that are divisible by $2^k$. Summing from $k=1$ to $k = 11$ yields at most $1007 + 504 + 252 + 126 + 63 + 32 + 16 + 8 + 4 + 2 + 1 = 2015$ factors of $2$ contributed by $1 \le k \le 11$. Thus, we have at least $4019 - 2015 = 2004$ factors of $2$ contributed by $k \ge 12$. However, all of these factors of $2$ must be from the same number, so we conclude the existence of a number divisible by $2^{11 + 2004} = 2^{2015}$.
It follows that $2^{2015} \le x+2014 \le y^2 + 4029y + (c+2014) = y^2 + 4029y + (1343 \cdot 2015 + 1006)$. We see that \[y > 2^{1000}.\]
Note that $(x+1)(x+2) \cdots (x+2014) \le (y^2 + 4029y + (c+1))(y^2 + 4029y + (c+2)) \cdots (y^2 + 4029y + (c+2014))$. I claim that \[(y^2 + 4029y + (c+1))(y^2 + 4029y + (c+2)) \cdots (y^2 + 4029y + (c+2014)) < (y+1)(y+2) \cdots (y+4028);\]this implies $(x+1)(x+2) \cdots (x+2014) < (y+1)(y+2) \cdots (y+4028)$, which is our desired contradiction.
Let's expand both sides of $(y^2 + 4029y + (c+1))(y^2 + 4029y + (c+2)) \cdots (y^2 + 4029y + (c+2014)) < (y+1)(y+2) \cdots (y+4028)$ as polynomials in $y$. Both sides have degree $4028$ and contain terms $y^{4028}, 4029 \cdot 2014 y^{4027}$. Let's try to find the coefficient of $y^{4026}$ on both sides.
On the LHS the coefficient of $y^{4026}$ is seen to be \[(c+1) + (c+2) + \cdots + (c+2014) + 4029^2 \cdot \binom{2014}{2}\]
On the RHS the coefficient of $y^{4026}$ is seen to be \[\frac{1}{2}((1+2+\cdots + 4028)^2 - (1^2 + 2^2 + \cdots + 4028^2))\]
After some computation we get that the RHS coefficient of $y^{4026}$ exceeds the LHS coefficient of $y^{4026}$ by $1007$.
Let $a_k$ denote the LHS coefficient of $y^k$. It suffices to show that \[\sum_{k=0}^{4025} a_k y^{k-4026} < 1007.\]We will do some bounding for $k \le 4022$. Note that the LHS coefficient of $y^k$ is at most the coefficient of $y^k$ in $(y^2 + 4029y + 4029^2)^{2014}$, which in turn is at most $4029^{4028-k} \cdot 3^{2014}$. Thus $a_k \le 4029^{4028-k} \cdot 3^{2014}$ and \[a_ky^{k-4026} \le (\frac{4029}{y})^{4026-k} \cdot 4029^2 \cdot 3^{2014} < (\frac{4029}{2^{1000}})^{4026-k} \cdot 4029^2 \cdot 3^{2014} \le (\frac{4029}{2^{1000}})^4 \cdot 4029^2 \cdot 3^{2014} \]\[ = \frac{4029^6 \cdot 3^{2014}}{2^{4000}} < (\frac{3}{4})^{2000} \cdot 10000^6 \cdot 3^{14} \]
We calculate $3^7 = 2187 < 3000$, so $3^{14} < 3000^2 = 9000000 = 9 \cdot 10^6$. Furthermore, $10000^6 = 10^{24}$, so $10000^6 \cdot 3^{14} < 9 \cdot 10^{30} < 10^{31}$.
We calculate $(\frac{3}{4})^4 = \frac{81}{256} < \frac{1}{3}$, so $(\frac{3}{4})^{2000} < \frac{1}{3^{500}}$. Now note that $3^{5} = 243 > 10^2$, so $3^{500} > 10^{200}$ and $\frac{1}{3^{500}} < 10^{-200}$.
Putting it all together we find that \[a_ky^{k-4026} < 10^{-200+31} = 10^{-169}.\]Thus \[\sum_{k=0}^{4025} a_k y^{k-4026} < \frac{a_{4025}}{y} + \frac{a_{4024}}{y^2} + \frac{a_{4023}}{y^3} + (4023 \cdot 10^{-169}).\]
To deal with the remaining $a_{4025}, a_{4024}, a_{4023}$, we will make the following observation. Suppose we are trying to find the coefficient of $y^k$ in the expression $(y^2 + 4029y + 4029^2)^{2014}$, for $4023 \le k \le 4025$. We can imagine, for each of the $2014$ multiplicands, choosing one of $\{ y^2, 4029y, 4029^2 \}$ to contribute to the resulting expression. We must have at least $k - 2014$ summands in which the $y^2$ is chosen. This means that, with overcounting, we have at most $\dbinom{2014}{4028-k} \cdot 3^{4028-k}$ ways to choose terms such that the resulting product is a scalar multiple of $y^k$. We conclude that \[a_k \le 4029^{4028-k} \cdot \dbinom{2014}{4028-k} \cdot 3^{4028-k} \le 4029^5 \cdot \dbinom{2014}{5} \cdot 3^5 \]and thus \[\frac{a_{4025}}{y} + \frac{a_{4024}}{y^2} + \frac{a_{4023}}{y^3} \le (4029^5 \cdot \dbinom{2014}{5} \cdot 3^5)(\frac{1}{y} + \frac{1}{y^2} + \frac{1}{y^3})\]\[ < (4029^5 \cdot 2014^5 \cdot 3^5)(\frac{1}{2^{1000}} + \frac{1}{2^{2000}} + \frac{1}{2^{3000}}) < (10000^5 \cdot 10000^5 \cdot 1000)(\frac{10}{2^{1000}})\]\[ = \frac{10^{44}}{2^{1000}} = \frac{10^{44}}{1024^{100}} < \frac{10^{44}}{1000^{100}} = 10^{44-300} = 10^{-256}.\]
We conclude that \[\sum_{k=0}^{4025} a_k y^{k-4026} < (10^{-256}) + (4023 \cdot 10^{-169}) < 1007,\]as desired. $\blacksquare$
neel02
08.06.2018 20:20
MathPanda1 wrote: Could a generalization to this problem be: determine all positive integers $n$ such that $ (x+1) (x+2)\cdots (x+n)= (y+1) (y+2)\cdots (y+n)$ has a solution? However, for the China TST problem, would it help to look at the exponent of specific primes $p$ (e.g. 2,3,5, 4027) in the LHS and the RHS and forcing them to equate by setting the $x+i$'s to be divisible by $p^{(...)}$? Why you write $n$ to both side ? If you really want to look for an generalization replace $n$ by $2n$ at one side of the equality !
Luve96
09.06.2018 04:04
neel02 wrote: MathPanda1 wrote: Could a generalization to this problem be: determine all positive integers $n$ such that $ (x+1) (x+2)\cdots (x+n)= (y+1) (y+2)\cdots (y+n)$ has a solution? However, for the China TST problem, would it help to look at the exponent of specific primes $p$ (e.g. 2,3,5, 4027) in the LHS and the RHS and forcing them to equate by setting the $x+i$'s to be divisible by $p^{(...)}$? Why you write $n$ to both side ? If you really want to look for an generalization replace $n$ by $2n$ at one side of the equality ! Unnecessary comment (like this one), obviously it's a typo.
TheUltimate123
25.10.2020 10:51
Solved with nukelauncher. First we show \(x\) is large. We analyze the 2-adic valuations of both sides. Observe from \(\left\lceil\frac{2014}{2^k}\right\rceil\le\frac{2014}{2^k}+1\) for \(k\le\log_2(x+2014)\) that the left-hand side has at least \[\sum_{k=1}^{\log_2(x+2014)}\left\lceil\frac{2014}{2^k}\right\rceil\le2014+\log_2(x+2014).\]factors of 2. Analogously, from \(\left\lfloor\frac{4028}{2^k}\right\rfloor\ge\frac{4028}{2^k}-1\) for \(k\le\log_24028\), the right-hand side has at most \[\sum_{k\ge1}\left\lfloor\frac{4028}{2^k}\right\rfloor\ge4028-\log_24028\]factors of 2. Combining these bounds, \[\log_2(x+2014)\ge2014-\log_24028\implies x\ge2^{2002}-2014,\]so \(x\) is sufficiently large. \bigskip Now we will bound \(x\) between two integers; in particular, we will show \(y^2+4029y+2705137<x<y^2+4029y+2705138\). Consider the given equation in the form \[(x+1)\cdots(x+2014)=\left(y^2+4029y+1\cdot4028\right)\cdots\left(y^2+4029y+2014\cdot2015\right).\]It is clear \(y^2+4029y+4027\le x\le y^2+4029y+2014^2\) by comparing smallest/largest terms. Set \(z=y^2+4029y\) and \(K=x-z\), so that \(4027\le K\le2014^2\); then \(z\ge2^{2000}\) is also very large. Consider the \(z^{2014-t}\) coefficient of \[P(z):=(z+K+1)\cdots(z+K+2014)-(z+1\cdot4028)\cdots(z+2014\cdot2015).\]Its magnitude is upper bounded by \[\binom{2014}t\Big[(K+2014)^t+(2014\cdot2015)\Big]\ll2^{200t}<z^{t/10}.\]Hence the \(z^{2014-t}\) monomial has magnitude at most \[z^{2014-t}\cdot z^{t/10}\ll z^{2013}/2013\]for \(t\ge2\). It follows that \(P(z)\) is dominated by the \(z^{2013}\) monomial. But for \(P\) to have a root \(z\ge2^{2000}\), the \(z^{2013}\) monomial must vanish to zero. Comparing the \(z^{2013}\) coefficients, we have \begin{align*} (K+1)\cdots+(K+2014)&=1+4028+\cdots+2014\cdot2015\\ \implies K&=2705137.5, \end{align*}which is not an integer, contradiction.
squareman
08.01.2022 07:30
Solved with rama1728. There must be at least $$\left \lfloor \frac{4028}{2^1} \right \rfloor+\left \lfloor \frac{4028}{2^2} \right \rfloor+\left \lfloor \frac{4028}{2^3} \right \rfloor +\dots = 4019$$powers of $2$ dividing the RHS. Besides the highest $v_2$ product term on the LHS, there can be at most $$\left \lceil \frac{2014}{2^2} -1 \right \rceil +\left \lceil \frac{2014}{2^2} -1 \right \rceil +\left \lceil \frac{2014}{2^3} -1 \right \rceil +\dots = 2004$$powers of $2$ dividing the LHS. So $x \ge 2^{2015}-2014.$ Let $A = y^2+4029y,$ then $$(x+1)\cdots (x+2014)= (A+1 \times 4028)\cdots (A+2014 \times 2015).$$Let $x - A = D.$ Note $A + 1 \times 4028 < x+1 \implies 4027 < D,$ and $x+2014 < A+2014\times 2015 \implies D < 2014^2.$ Some silly bounding follows. Consider the polynomial $P(a)$ with degree at most $2013$ and with integer coefficients where $$P(a) = (a+D+1) \cdots (a+D+2014) - (a+1 \times 4028) \cdots (a+2014 \times 2015),$$and $P(a)$ has a root $A.$ It suffices to prove that the $a^{2013}$ term is zero, since that would mean $D$ is not an integer for parity reasons. Consider the $a^{2014-n}$ term for any $2 \le n \le 2014,$ there are only $2013$ such terms in the polynomial. If we plug in $A,$ the term has magnitude (by Triangle Inequality) less than \begin{align*}\binom{2014}n \times \Big( (D+2014)^n+(2014\times 2015)^n\Big) \times A^{2014-n} &< 2048^n \times (2 \times 2048^{2n}) \times A^{2014-n}\\ &= \frac{2^{33n+1}}{A^{n-1}} \times A^{2013} \end{align*}which is much less than $\frac{A^{2013}}{2013}$ so the $a^{2013}$ coefficient has to be $0$ if $A$ is a root. $\square$
NO_SQUARES
13.01.2024 17:00
It seems that no one has yet noted the similarity of this problem and the problem from the 239 MO in 2009 (author is Fedor Petrov). If I'm mistaken, please, say it...
Fedor Petrov
16.01.2024 11:17
Ah, I remember this problem about two boys multiplying consecutive numbers, but I did not know their names until today.