Разделы 
Дополнительно
Задача по математике - 1047
2015-02-17 
Докажите, что для любых неотрицательных целых чисел $m$ и $n$ число $\frac{(2m)!(2n)!}{m!n!(m+n)!}$ является целым (полагаем $0!=1$).
Решение:
Покажем, что максимальная степень простого числа $p$, на которую делится числитель данной дроби, не меньше максимальной степени того же числа $p$, на которую делится знаменатель данной дроби. Тем самым задача будет решена.
Лемма 1. Пусть для некоторого простого числа $p$ и для некоторых натуральных чисел $n$ и $k$ выполняется неравенство $p^{k+1} > n$. Тогда число $p$ входит в разложение числа $n!$ на простые множители в степени $\left [ \frac{n}{p} \right ] + \left [ \frac{n}{p^{2}} \right ] + \left [ \frac{n}{p^{3}} \right ] + \cdots + \left [ \frac{n}{p^{k}} \right ]$, где через $[a]$ обозначена целая часть числа $a$.
Мы предоставим доказательство этой леммы.
Лемма 2 (выражающая свойство целых чисел). Пусть $a$ и $b$ - неотрицательные числа. Тогда для них справедливо неравенство
$[2a] + [2b] \geq [a] + [b] + [a+b]$.
Пусть $a=[a] + \alpha$ и $b=[b] + \beta$, где $0 \leq \alpha < 1$ и $0 \leq \beta < 1$.
Если $\alpha + \beta < 1$, то $[a+b] = [a] + [b]$ и поэтому $[2a] + [2b] \geq 2[a] + 2[b] = [a] + [b] + [a+b]$.
Если же $\alpha + \beta \geq 1$, то либо $2 \alpha \geq 1$, либо $2 \beta \geq 1$.
Пусть, например, $2 \alpha \geq 1$ (случай $2 \beta \geq 1$ рассматривается аналогично). Тогда $[a+b] = [a] + [b] + 1$ и $[2a] = 2[a] + 1$. Поэтому $[2a] + [2b] \geq 2[a] + 1 + 2 [b] = [a] + [b] + [a+b]$.
Итак, лемма 2 доказана.
Возьмем теперь любое простое число и столь большое $k$, что $p^{k+1} > 2n$ и $p^{k+1} > 2m$. Тогда и $p^{k+1} > m+n$. Применяя лемму 1, получаем, что число $p$ входит в числитель данной дроби в степени
$s = \left [ \frac{2n}{p} \right ] + \left [ \frac{2n}{p^{2}} \right ] + \cdots + \left [ \frac{2n}{p^{k}} \right ] + \left [ \frac{2m}{p} \right ] + \left [ \frac{2m}{p^{2}} \right ] + \cdots + \left [ \frac{2m}{p^{k}} \right ]$.
а в знаменатель — в степени
$t = \left [ \frac{m}{p} \right ] + \left [ \frac{m}{p^{2}} \right ] + \cdots + \left [ \frac{m}{p^{k}} \right ] + \left [ \frac{n}{p} \right ] + \left [ \frac{n}{p^{k}} \right ] + \cdots + \left [ \frac{n}{p^{k}} \right ] + \left [ \frac{m+n}{p} \right ] + \left [ \frac{m+n}{p^{2}} \right ] + \cdots + \left [ \frac{m+n}{p^{k}} \right ]$.
Далее, применяя к числам $a = \frac{m}{p^{i}}$ и $b = \frac{n}{p^{i}}$ лемму 2, получаем:
$\left [ \frac{2m}{p^{i}} \right ] +\left [ \frac{2n}{p^{i}} \right ] \geq \left [ \frac{m}{p^{i}} \right ] + \left [ \frac{n}{p^{i}} \right ] + \left [ \frac{m+n}{p^{i}} \right ]$.
Складывая все такие неравенства для $i=1,2,3, \cdots, k$, получаем, что $s \geq t$. Откуда и следует, что числитель данной дроби нацело делится на знаменатель.
Докажите, что для любых неотрицательных целых чисел $m$ и $n$ число $\frac{(2m)!(2n)!}{m!n!(m+n)!}$ является целым (полагаем $0!=1$).
Решение:
Покажем, что максимальная степень простого числа $p$, на которую делится числитель данной дроби, не меньше максимальной степени того же числа $p$, на которую делится знаменатель данной дроби. Тем самым задача будет решена.
Лемма 1. Пусть для некоторого простого числа $p$ и для некоторых натуральных чисел $n$ и $k$ выполняется неравенство $p^{k+1} > n$. Тогда число $p$ входит в разложение числа $n!$ на простые множители в степени $\left [ \frac{n}{p} \right ] + \left [ \frac{n}{p^{2}} \right ] + \left [ \frac{n}{p^{3}} \right ] + \cdots + \left [ \frac{n}{p^{k}} \right ]$, где через $[a]$ обозначена целая часть числа $a$.
Мы предоставим доказательство этой леммы.
Лемма 2 (выражающая свойство целых чисел). Пусть $a$ и $b$ - неотрицательные числа. Тогда для них справедливо неравенство
$[2a] + [2b] \geq [a] + [b] + [a+b]$.
Пусть $a=[a] + \alpha$ и $b=[b] + \beta$, где $0 \leq \alpha < 1$ и $0 \leq \beta < 1$.
Если $\alpha + \beta < 1$, то $[a+b] = [a] + [b]$ и поэтому $[2a] + [2b] \geq 2[a] + 2[b] = [a] + [b] + [a+b]$.
Если же $\alpha + \beta \geq 1$, то либо $2 \alpha \geq 1$, либо $2 \beta \geq 1$.
Пусть, например, $2 \alpha \geq 1$ (случай $2 \beta \geq 1$ рассматривается аналогично). Тогда $[a+b] = [a] + [b] + 1$ и $[2a] = 2[a] + 1$. Поэтому $[2a] + [2b] \geq 2[a] + 1 + 2 [b] = [a] + [b] + [a+b]$.
Итак, лемма 2 доказана.
Возьмем теперь любое простое число и столь большое $k$, что $p^{k+1} > 2n$ и $p^{k+1} > 2m$. Тогда и $p^{k+1} > m+n$. Применяя лемму 1, получаем, что число $p$ входит в числитель данной дроби в степени
$s = \left [ \frac{2n}{p} \right ] + \left [ \frac{2n}{p^{2}} \right ] + \cdots + \left [ \frac{2n}{p^{k}} \right ] + \left [ \frac{2m}{p} \right ] + \left [ \frac{2m}{p^{2}} \right ] + \cdots + \left [ \frac{2m}{p^{k}} \right ]$.
а в знаменатель — в степени
$t = \left [ \frac{m}{p} \right ] + \left [ \frac{m}{p^{2}} \right ] + \cdots + \left [ \frac{m}{p^{k}} \right ] + \left [ \frac{n}{p} \right ] + \left [ \frac{n}{p^{k}} \right ] + \cdots + \left [ \frac{n}{p^{k}} \right ] + \left [ \frac{m+n}{p} \right ] + \left [ \frac{m+n}{p^{2}} \right ] + \cdots + \left [ \frac{m+n}{p^{k}} \right ]$.
Далее, применяя к числам $a = \frac{m}{p^{i}}$ и $b = \frac{n}{p^{i}}$ лемму 2, получаем:
$\left [ \frac{2m}{p^{i}} \right ] +\left [ \frac{2n}{p^{i}} \right ] \geq \left [ \frac{m}{p^{i}} \right ] + \left [ \frac{n}{p^{i}} \right ] + \left [ \frac{m+n}{p^{i}} \right ]$.
Складывая все такие неравенства для $i=1,2,3, \cdots, k$, получаем, что $s \geq t$. Откуда и следует, что числитель данной дроби нацело делится на знаменатель.
