Question

کوچکترین عدد $n$ که $17^2$ مقسوم علیه$\frac{(n+1)(n+2)...(2n)}{1×2×3×...×n}$ باشد، چند است؟

تلاش انجام شده: متاسفانه تلاش انجام شده است ولی به نتیجه ای نرسیده.

Answer 1

می‌دانیم تعداد عوامل عدد اول $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$ عبارت صورت سوال را می‌شمارد.

Comments

بسیار ممنونم.
ببخشید، چرا فرض کرده اید $n<289$ و دیگر فرض نکرده اید که $n$ بزرگتر مساوی از 289 باشد؟

---

اگر بتوانیم با فرض $n<289$ جوابی پیدا کنیم بس است، زیرا سوال کوچکترین عدد با این ویژگی را درخواست کرده است.