میدانیم تعداد عوامل عدد اول $p$ در $n!$ به صورت زیر به دست میآید:
$$N(n, p) = \sum_{i=1}^{ \infty } \lfloor \frac{n}{p^i} \rfloor$$
حال داریم:
$$\frac{(n+1)(n+2)\ldots(2n)}{1\times 2 \times 3\ldots \times n}=\frac{(2n)!}{n! \times n!}$$
یعنی تعداد عوامل عدد اول $p$ در این عبارت برابر است با:
$$S(n,p) = N(2n, p) - 2N(n,p)$$
$$=\sum_{i=1}^{\infty} \left( \lfloor \frac{2n}{p^i} \rfloor - 2\lfloor \frac{n}{p^i} \rfloor \right)$$
خواستهی مسئله این است که
$S(n, 17) \geq 2$
باشد. اگر فرض کنیم
$n < 17^2 = 289$
باشد. آنگاه
$S(n, 17)$
به صورت زیر در میآید.
$$S(n, 17) =\left( \lfloor \frac{2n}{17} \rfloor - 2\lfloor \frac{n}{17} \rfloor \right) + \left( \lfloor \frac{2n}{17^2} \rfloor - 2\lfloor \frac{n}{17^2} \rfloor \right)$$
اکنون اگر $n$ را بر $17$ و $289$ تقسیم کنیم، میتوان آن را به صورت
$$n = 17k_1 + r_1 = 289k_2 + r_2$$
نوشت که
$k_1, k_2, r_1, r_2$
اعداد صحیح و نامنفیاند و
$r_1 < 17, r_2 < 289$
است. حال داریم:
$$S(n, 17) =\left( \lfloor \frac{2n}{17} \rfloor - 2\lfloor \frac{n}{17} \rfloor \right) + \left( \lfloor \frac{2n}{17^2} \rfloor - 2\lfloor \frac{n}{17^2} \rfloor \right)$$
$$=\left( \lfloor \frac{2(17k_1 + r_1)}{17} \rfloor - 2\lfloor \frac{17k_1+r_1}{17} \rfloor \right) +
\left( \lfloor \frac{2(289k_2 + r_2)}{289} \rfloor - 2\lfloor \frac{289k_2+r_2}{289} \rfloor \right)
$$
$$=\left( 2k_1 + \lfloor \frac{2r_1}{17} \rfloor - 2k_1 \right) +
\left( 2k_2 + \lfloor \frac{2r_2}{289} \rfloor - 2k_2 \right)$$
$$=\lfloor \frac{2r_1}{17} \rfloor + \lfloor \frac{2r_2}{289} \rfloor \tag{II}$$
توجه کنید:
$2r_1 < 2 \times 17$
و
$2r_2 < 2 \times 289$
است. پس هر کدام از عبارتها در معادلهی $II$ یا برابر ۰ هستند یا برابر ۱. یعنی برای اینکه
$S(n, 17)\geq 2$
شود باید هردوی آنها برابر ۱ باشند. یعنی:
$$2r_2 \geq 289 \Longrightarrow r_2 \geq 145$$
یعنی
$n \geq 145$
باید باشد. همچنین توجه کنید:
$145 = 17 \times 8 + 9$.
پس
$r_1 = 9$
و برای آن داریم:
$\lfloor \frac{2r_1}{17} \rfloor = 1 $.
در نتیجه
$S(145, 17) = 2$.
پس $145$ کمترین مقدار برای $n$ است که
$17^2$
عبارت صورت سوال را میشمارد.
