Página 1 de 1

CIMA 2019 - P1

Publicado: Jue 06 Jun, 2019 6:20 pm
por jujumas
Sen $m$, $n$ enteros positivos. Demuestre que $m!^nn!$ divide a $(mn)!$

Re: CIMA 2019 - P1

Publicado: Jue 06 Jun, 2019 9:56 pm
por LuchoLP
Spoiler: mostrar
Supongamos que tenemos $m$ letras del tipo $1$, $m$ letras del tipo $2$, ..., $m$ letras del tipo $n$. Entonces la cantidad total de palabras que podemos armar con esas letras es $\frac{(mn)!}{(m!)^n}$.
Llamemos "movimiento permitido" a transformar una palabra del conjunto en otra reemplazando todas las letras del tipo $i$ por letras del tipo $j$ y viceversa.
Ahora el total de palabras se puede dividir en subconjuntos de la siguiente manera, que forman una partición del conjunto: dos palabras están en el mismo subconjunto si y solo si se puede pasar de una a otra mediante una cantidad finita de movimientos permitidos. La cantidad de palabras en cada subconjunto de esta partición es $n!$, pues tenemos todos los reordenamientos de los $n$ tipos de letras posibles. Luego $n!$ divide a $\frac{(mn)!}{(m!)^n}$.

Re: CIMA 2019 - P1

Publicado: Jue 06 Jun, 2019 10:25 pm
por Turko Arias
Como se nota que tenés licencia para conducir... Sino no se entiende como alguien podría manejar tanta magia. Tremenda solución bestia, mañana en el taller nos sacamos una foto para que la gente me crea que conozco al gran @LuchoLP

Re: CIMA 2019 - P1

Publicado: Dom 09 Jun, 2019 10:22 pm
por Fran5
Bueno, no voy a hacer mucho al lado de lo que ya hizo lucho... pero acá va una no tan galezaro.
Spoiler: mostrar
La idea es ver que entre todo los factores de $(mn)!$, tenemos suficientes para hacer un múltiplo de $m!^nn!$.

Sea $m_1 = 1 \cdot 2 \cdots m = m!$, y sean $$m_2 = (m+1) \cdot (m+2) \cdot (m+3) \cdots 2m,$$ $$\ldots,$$ $$m_n = ((n-1)m+1) \cdot ((n-1)m +2) \cdot ((n-1)m+3) \cdots nm,$$ de modo que $$(mn)! = m_1 m_2 \cdots m_n$$

Vemos que en cada uno de los primeros $m-1$ factores de $m_j$, hay al menos un múltiplo de $1$, al menos un múltiplo de $2$, así hasta encontrar al menos un múltiplo de $m-1$, con lo cual $(m-1)!$ divide a $m_j$ para todo $j$. Luego $(m-1)!^n$ divide a $(mn)!$.

Ahora, también vemos que si multiplicamos todos los $m_j$, considerando el último factor de cada término (es decir, $jm$), tenemos que $$m \cdot 2m \cdot 3m \cdots nm$$ divide a $(mn)!$, esto es $m^nn!$ divide a $m$.

Como los factores que consideramos en cada casito son distintos, tenemos que $(m-1)!^nm^nn!$ divide a $(mn)!$. Esto es $m!^nn!$ divide a $(mn)!$, qed.