Maths Olympiad Prep

Library / China Team Selection Test /68 of 92

China Team Selection Test

Number theory Difficulty 8.4 Shortlist Prove it China

Show that there are no 2-tuples (x,y)(x, y) of positive integers satisfying the equation
(x+1)(x+2)⋯(x+2014)=(y+1)(y+2)⋯(y+4028). (x+1)(x+2)\cdots(x+2014) = (y+1)(y+2)\cdots(y+4028).

Solution

Proof For n=2k⋅mn = 2^k \cdot m (kk is a non-negative integer, mm is odd), let v(n)=2kv(n) = 2^k.
We prove by contradiction: assume (x,y)(x, y) is one positive integer solution of the equation. Let
v(x+i)=max⁡1≤j≤2014{v(x+j)}, v(x + i) = \max_{1 \le j \le 2014} \{v(x + j)\},
then if 1≤j≤2014, j≠i1 \le j \le 2014,\ j \ne i,
v(x+j)=v(x+i+(j−i))=v(j−i), v(x + j) = v(x + i + (j - i)) = v(j - i),
so
v(∏1≤j≤2014, j≠i(x+j))=v((2014−j)!⋅(j−1)!)≤v(2013!) v\left(\prod_{1 \le j \le 2014,\ j \ne i} (x + j)\right) = v\left((2014 - j)! \cdot (j - 1)!\right) \le v(2013!)
since ∏j=12014(x+j)=∏j=14028(y+j)\prod_{j=1}^{2014} (x + j) = \prod_{j=1}^{4028} (y + j) is a multiple of 4028!4028!, thus
x+i≥v(x+i)≥v(4028!2013!)>21007, x + i \geq v(x + i) \geq v\left(\frac{4028!}{2013!}\right) > 2^{1007},
therefore x>21006x > 2^{1006}. So (y+4028)4028>∏j=14028(y+j)=∏j=12014(x+j)>21006⋅2014(y + 4028)^{4028} > \prod_{j=1}^{4028} (y + j) = \prod_{j=1}^{2014} (x + j) > 2^{1006 \cdot 2014}, we have y+4028>2503y + 4028 > 2^{503}, y>2502y > 2^{502}.

Lemma: Let 0≤xi<12 (1≤i≤n)0 \le x_i < \frac{1}{2}\ (1 \le i \le n), if x=1n∑i=1nxix = \frac{1}{n} \sum_{i=1}^{n} x_i, y=2max⁡1≤i≤n{xi2}y = 2 \max_{1 \le i \le n} \{x_i^2\}, then
1−x≥(∏i=1n(1−xi))1n≥1−x−y. 1 - x \ge \left( \prod_{i=1}^{n} (1 - x_i) \right)^{\frac{1}{n}} \ge 1 - x - y.
Proof of lemma: By AM-GM inequality, the inequality on the left is easy to prove. The inequality on the right holds, since
(∏i=1n(1−xi))1n≥n∑i=1n11−xi≥n∑i=1n(1+xi+2xi2)=nn+nx+2∑i=1nxi2≥11+x+y≥1−x−y, \begin{aligned} \left( \prod_{i=1}^{n} (1-x_i) \right)^{\frac{1}{n}} &\ge \frac{n}{\sum_{i=1}^{n} \frac{1}{1-x_i}} \\ &\ge \frac{n}{\sum_{i=1}^{n} (1+x_i + 2x_i^2)} \\ &= \frac{n}{n+nx+2\sum_{i=1}^{n} x_i^2} \\ &\ge \frac{1}{1+x+y} \\ &\ge 1-x-y, \end{aligned}
the lemma is proved.

Back to the problem, Let w=x+2015>21007w = x + 2015 > 2^{1007}, z=y+40292>2502z = y + \frac{4029}{2} > 2^{502}, then the equation is equivalent to
w⋅((1−1w)(1−2w)⋯(1−2014w))12014=z2⋅((1−14z2)(1−94z2)⋯(1−402724z2))12014. 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}}.
By lemma,
w(1−20152w)>w⋅((1−1w)(1−2w)⋯(1−2014w))12014 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(1−20152w−2⋅20142w2)>w(1−20152w)−18,\begin{aligned} &> 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{aligned}
thereforethedecimalof$w⋅((1−1w)(1−2w)⋯(1−2014w))12014$belongsto$(38,12)$.Ontheotherhand,bylemma therefore the decimal of \$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}}\$ belongs to \$\left( \frac{3}{8}, \frac{1}{2} \right)\$. On the other hand, by lemma
z2(1−12+32+⋯+402724z2⋅2014)>z2⋅((1−14z2)(1−94z2)⋯(1−402724z2))12014>z2(1−12+32+⋯+402724z2⋅2014−2⋅40274(4z2)2),\begin{aligned} z^2 \left( 1 - \frac{1^2 + 3^2 + \cdots + 4027^2}{4z^2 \cdot 2014} \right) &> 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}} \\ &> z^2 \left( 1 - \frac{1^2 + 3^2 + \cdots + 4027^2}{4z^2 \cdot 2014} - \frac{2 \cdot 4027^4}{(4z^2)^2} \right), \end{aligned}
thus thus
z2−4⋅20142−112>z2⋅((1−14z2)(1−94z2)⋯(1−402724z2))12014>z2−4⋅20142−112−402748z2>z2−4⋅20142−112−18.\begin{aligned} z^2 - \frac{4 \cdot 2014^2 - 1}{12} &> 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}} \\ &> 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{aligned}
Since$z2−4⋅20142−112$isaninteger,sothedecimalof$z2⋅((1−14z2)(1−94z2)⋯(1−402724z2))12014$belongsto$(78,1)$,thisisacontradiction.Therefore,thereareno2−tuples$(x,y)$ofpositiveintegerssatisfying Since \$z^2 - \frac{4 \cdot 2014^2 - 1}{12}\$ is an integer, so the decimal of \$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}}\$ belongs to \$\left( \frac{7}{8}, 1 \right)\$, this is a contradiction. Therefore, there are no 2-tuples \$(x, y)\$ of positive integers satisfying
∏j=12014\prod_{j=1}^{2014} (x + j) = ∏j=14028\prod_{j=1}^{4028} (y + j).

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.