Cómo probar que \frac{(5m) $$! \cdot (5n)!} {m! n \cdot! \cdot (3m + n)! \cdot (3n + m)!} ¿$$ es un número natural $\forall m, n\in\mathbb N$, $m\geqslant 1$ y $n\geqslant 1$?
Gracias de antemano.
Respuestas
¿Demasiados anuncios?
Deje que $p$ ser un número primo. Usted debe mostrar que
$$\left\lfloor \frac{5 m}{p^k}\right\rfloor+\left\lfloor \frac{5n}{p^k}\right\rfloor \geq \left\lfloor \frac{m}{p^k}\right\rfloor+\left\lfloor \frac{n}{p^k}\right\rfloor+\left\lfloor \frac{3m+n}{p^k}\right\rfloor+\left\lfloor \frac{3n+m}{p^k}\right\rfloor$$
por $k \geq 1.$ Por Hermite de la identidad obtendrá
$$\left\lfloor \frac{5 m}{p^k}\right\rfloor=\left\lfloor \frac{m}{p^k}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{1}{5}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{2}{5}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{3}{5}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{4}{5}\right\rfloor$$
Entonces usted debe mostrar que
$$\sum_{i=1}^{4} \left\lfloor \frac{m}{p^k}+\frac{i}{5}\right\rfloor+\sum_{j=1}^{4}\left\lfloor \frac{n}{p^k}+\frac{j}{5}\right\rfloor \geq \left\lfloor \frac{3m+n}{p^k}\right\rfloor+\left\lfloor \frac{3n+m}{p^k}\right\rfloor$$
que se puede hacer, considerando los diferentes casos para los valores de $\frac{m}{p^k}, \frac{n}{p^k}$ es decir, cada uno puede estar en los siguientes intervalos de tiempo $(0,\frac15), [\frac15, \frac25), [\frac25, \frac35), [\frac35, \frac45), [\frac45, 1),$ ya $\lfloor x+n \rfloor=\lfloor x\rfloor+n,$ para y el número real de $x$ y un entero $n,$ usted puede simplemente ignorar el caso cuando $\frac{m}{p^k}, \frac{n}{p^k}$ son más grandes que los de 1$.$
Antes pensaba: La expresión puede reescribirse como
$$\frac{\binom{5m}{3m}(3m)!\binom{5n}{n}n!}{(3m+n)!} \frac {\binom{4n}{3n}(3n)!\binom{2m}{m}m!}{(3n+m)!}$$
Tenía la esperanza de encontrar una combinatoria interpretación de esta expresión, pero no he encontrado todavía!
mahler
Puntos
161
Si $ m=n $ esto es $ \binom{5m}{m} ^ 2$
Se asume que $m>n$
$$ \frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!} $$
$ $ a = \frac{(4m+(m-n)+n)! \cdot (4n-(m-n)+m)!}{m! \cdot n! \cdot (4m-(m-n))! \cdot (4n+(m-n))!} $$
$ $ a = \frac{(4m-(m-n)+n+2(m-n))! \cdot (4n+(m-n)+m-2(m-n))!}{n! \cdot (4m-(m-n))! \cdot m! \cdot (4n+(m-n))!} $$
$$ = \binom{4 m-(m-n)+n}{n}\cdot\frac{(4m-(m-n)+n+2(m-n))!}{(4m-(m-n)+n)!} \cdot\binom{4n+(m-n)+m}{m}\cdot\frac{(4n+(m-n)+m-2(m-n))!}{(4n+(m-n)+m)!} $$
$$ = \binom{3m+2n}{n}\cdot\frac{(5m)!}{(3m+2n)!} \cdot\binom{3n+2m}{m}\cdot\frac{(5n)!}{(3n+2m)!} $$
$$ = \binom{3m+2n}{n} \cdot\frac{(5m)!}{(3m+2n)!} \cdot\frac{(5m-(3m+2n))!}{(5m-(3m+2n))!} \cdot\binom{3n+2m}{m} \cdot\frac{(5n)!}{(3n+2m)!} $$
$$\cdots 5n<3n+2m $$
$$ = \binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot (5m-(3m+2n))! \cdot\binom{3n+2m}{m} \cdot\frac{(5n)!}{(3n+2m)!} $$
$$ = \binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot\binom{3n+2m}{m} \cdot \frac{(2m-2n)! (5n)!}{(3n+2m)!} $$
$ $ a = \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot\binom{3n+2m}{m}} {\binom{3n+2m}{5n}} $$
Considerar el último factor en el denominador: $$ \frac{\binom{3n+2m}{m}} {\binom{3n+2m}{5n}} $$ $ $ a= \frac{\frac{(3n+m)\cdots(3n+2m)}{m.}} {\frac{(2m-2n)\cdots(2m+3n)}{(5n)!}} $$ $$= {\frac{(m+3n)\cdots(2m+3n)}{(2m-2n)\cdots(2m+3n)}} \cdot {\frac{(5n)!}{m.}} $$
Casos: ($m\le5n$ o $m>5n$) y ($m+3n<2m-2n$ o $m+3n\ge2m-2n$)
es decir ($m\le5n$ o $m>5n$) y ($5n<m$ o $5n\ge m$)
es decir, $m\le5n$ o $m>5n$
Caso: $m\le5n$ es decir $2m-2n \le m+3n$
$$= {\frac{(m+1)\cdots(5n)}{(2m-2n)\cdots(m+3n-1)}} $$
Caso: $m>5n$ es decir $2m-2n > m+3n$
$$= {\frac{(m+3n)\cdots(2m-2n-1)}{(5n+1)\cdots(m)}} $$
Probablemente hay un simple paso final ahora que no sé/ver en ese momento...
Alternativamente:
$$ = \binom{3m+2n}{n} \cdot\frac{(5m)!}{(3n+2m)!} \cdot\frac{(5m-(3n+2m))!}{(5m-(3n+2m))!} \cdot\binom{3n+2m}{m} \cdot\frac{(5n)!}{(3m+2n)!} $$
$$\cdots 5n<3m+2n $$
$$ = \binom{3m+2n}{n} \cdot\binom{5m}{3n+2m} \cdot\binom{3n+2m}{m} \cdot\frac{(3m-3n)! (5n)!}{(3m+2n)!} $$
$ $ a = \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3n+2m} \cdot\binom{3n+2m}{m}} {\binom{3m+2n}{5n}} $$
Otro:
$$ \frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!} $$
$ $ a = \frac{(5m)!}{m!(4m)!}\cdot(4m)! \cdot \frac{(5n)!}{n!(4n)!}\cdot(4n)! \cdot \frac{1} {(3m+n)! \cdot (3n+m)!} $$
$ $ a = \frac{(5m)!}{m!(4m)!} \cdot \frac{(5n)!}{n!(4n)!} \cdot \frac{(4m)!\cdot(4n)!} {(4m-(m-n))! \cdot (4n+(m-n))!} $$
$ $ a = \frac{(5m)!}{m!(4m)!} \cdot \frac{(5n)!}{n!(4n)!} \cdot \frac{(4m)!} {(4m-(m-n))!(m-n)!} \cdot\frac{(m-n)!\cdot(4n)!} {(4n+(m-n))!} $$
$ $ a = \frac{\binom{5m}{m}\binom{5n}{n}\binom{4m}{m n}}{\binom{4n+(m-n)}{m n}} $$
$$ \dots espacio \\text{usando} espacio \\binom{n}{r}\binom{n-r}{k}=\binom{n}{k}\binom{n-k}{r}$$
$ $ a = \frac{\binom{5n}{n}\binom{5m}{m n}\binom{5 m-(m-n)}{m}}{\binom{4n+(m-n)}{m n}} $$
$ $ = \frac{\binom{5n}{n}\binom{4n}{k}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{4n}{k}\binom{4n+(m-n)}{m-n}} $$
$$ \dots espacio \\text{y otra vez para algunos}\espacio k : espacio \0\leq k\leq 4n $$
$ $ = \frac{\binom{5n}{k}\binom{5n-k}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{4n+(m-n)-k}{m-n}\binom{4n+(m-n)}{k}} $$
$$ \dots espacio \\text{try}\espacio k=2n $$
$ $ = \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{2n+(m-n)}{2n}\binom{4n+(m-n)}{2n}} $$
Considerando $ \frac{(m-n)!\cdot(4n)!} {(4n+(m-n))!} $ ($= 1/\binom{4n+(m-n)}{m n}$):
$$ \frac{(m-n)!\cdot(4n)!} {(4n+(m-n))!} $$
$ $ a = \frac{(m-n)!^2(4n-(m-n))!\cdot(4n-(m-n)+(m-n))!} {(4n+(m-n))!(4n-(m-n))!(m-n)!} $$
$ $ a = \frac{(m-n)!^2(5n-m)!} {(3n+m)!} \cdot\binom{4n}{m n} \dots \text{si } 5n>m $$
y esto es claramente un entero si $ 5n-m>3n+m $ es decir, $ n>m $, pero hemos asumido el contrario :-(
Posiblemente el mejor "asunción": Se asume que $m=k+n>n$
$$ \frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!} $$
$ $ a = \frac{(5k+5n)! \cdot (5n)!}{(k+n)! \cdot n! \cdot (3k+4n)! \cdot (4n+k)!} $$
Aplicado a los resultados anteriores:
$ $ a = \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot\binom{3n+2m}{m}} {\binom{3n+2m}{5n}} $$
$ $ a = \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{3k+5n} \cdot\binom{5n+2k}{k+n}} {\binom{5n+2k}{5n}} $$
$ $ a = \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{2k} \cdot\binom{5n+2k}{k+n}} {\binom{5n+2k}{2k}} $$
. . .
$ $ a = \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3n+2m} \cdot\binom{3n+2m}{m}} {\binom{3m+2n}{5n}} $$
$ $ a = \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{5n+2k} \cdot\binom{5n+2k}{n+k}} {\binom{3k+5n}{5n}} $$
$ $ a = \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{3k} \cdot\binom{5n+2k}{n+k}} {\binom{3k+5n}{3k}} $$
. . .
$ $ = \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{2n+(m-n)}{2n}\binom{4n+(m-n)}{2n}} $$
$ $ = \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5n+5k}{k}\binom{5n+4k}{n+k}}{\binom{2n+k}{2n}\binom{4n+k}{2n}} $$
$ $ a = \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5n+5k}{k}\binom{5n+4k}{n+k}}{\binom{2n+k}{k}\binom{4n+k}{2n}} $$
wujj123456
Puntos
171
Este es USAMO'1975 Problema 1. Una prueba requiere el lema siguiente. Sin embargo, me encantaría ver una combinatoria de la prueba.
Lema: Dejar que $x,y\geq 0$. Entonces, $\lfloor 5x\rfloor +\lfloor 5 a\rfloor \geq \lfloor x\rfloor +\lfloor y\rfloor+\lfloor 3x+y\rfloor +\lfloor 3y+x\rfloor$.
(Para demostrar el lema, usted sólo tiene que comprobar la desigualdad cuando $0\leq x,y<1$. Tomar $u:=\lfloor 5x\rfloor$ y $v:=\lfloor 5y\rfloor$, entonces $x < \frac{u+1}{5}$ y $y<\frac{v+1}{5}$. El resto se hace por considerar $u,v\in\{0,1,2,3,4\}$, donde también se puede suponer $u \leq v$.)
