CIMA 2019 - P1

jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
FOFO 9 años - Jurado-FOFO 9 años OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 402
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 13
Nivel: Exolímpico

CIMA 2019 - P1

Mensaje sin leer por jujumas »

Sen $m$, $n$ enteros positivos. Demuestre que $m!^nn!$ divide a $(mn)!$
LuchoLP

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Plata-OFO 2017
Mensajes: 191
Registrado: Mié 17 Abr, 2013 7:27 pm
Medallas: 3
Nivel: Exolímpico

Re: CIMA 2019 - P1

Mensaje sin leer 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}$.
9  
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: CIMA 2019 - P1

Mensaje sin leer 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
5  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: CIMA 2019 - P1

Mensaje sin leer 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.
1  
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: CIMA 2019 - P1

Mensaje sin leer por Gianni De Rico »

La verdad es que a veces me gusta matar un mosquito con un cañón
Spoiler: mostrar
Fijemos un primo $p$.
Basta ver que $v_p(m!^nn!)\leq v_p((mn)!)$. Esto es equivalente a $nv_p(m!)+v_p(n!)\leq v_p((mn)!)$. Por la Fórmula de Legendre, esto es equivalente a $n\dfrac{m-s_p(m)}{p-1}+\dfrac{n-s_p(n)}{p-1}\leq \dfrac{mn-s_p(mn)}{p-1}$, donde $s_p(a)$ es la suma de los dígitos de $a$ en base $p$. Como $p\geq 2$, esto es equivalente a $n+s_p(mn)\leq ns_p(m)+s_p(n)$. La suma de dígitos en cualquier base es submultiplicativa, es decir, $s_p(mn)\leq s_p(m)s_p(n)$, de modo que basta ver que $n+s_p(m)s_p(n)\leq ns_p(m)+s_p(n)$. Esto es equivalente a $0\leq (n-s_p(n))(s_p(m)-1)$, que es cierto pues $n\geq s_p(n)$ y $s_p(m)\geq 1$ para todos $m,n\in \mathbb{N}$. Ganamos.
♪♫ do re mi función lineal ♪♫
Responder