OMA Foros

Hola, soy Juan Pablo, soy estudiante de física en UBA y participe en olimpíadas de OMA desde 2003 hasta terminar el secundario.

Hola, soy Carlos Cardozo, soy profesor de Matemática y Física en la UNAM. De chico participe en las olimpiadas nacionales de Paraguay.

Bueno, me presento, soy Alejandro de Misiones, y participo en OMA desde los 10 años.

Problema 1:



¿Cuántas números de $4$ cifras se pueden formar con los números $1$, $2$,$3$ y $4$, si no se puede repetir ninguna cifra? ¿Y si se puede?





Para la segunda parte, vemos que cada cifra tiene $4$ opciones posibles, entonces la cantidad de números será, al haber $4$ cifras:

$4\times 4 \times4 \times4=4^4$





En general, si yo tengo $k$ cosas para hacer, y $n$ opciones distintas para cada cosa, la

cantidad total de posibilidades es $n^k$



En el ejemplo anterior, $n=4$, $k=4$, y las cosas para hacer eran elegir un numero para cada lugar o cifra.





Para la primer parte, vemos que para la primera cifra (unidades de mil), hay $4$ opciones de números a elegir, que pueden ser $1$, $2$, $3$ o $4$. Para la segunda cifra (centenas), ya no hay $4$ opciones, sino $3$, porque uno de los números ya fue usado para la primera cifra. Ahora, para las decenas, quedan sólo $2$ opciones, y para la unidad $1$. Es decir, la cantidad de números de $4$ cifras distintas formados por los números $1$, $2$, $3$ y $4$ es:

$4\times 3 \times 2 \times 1=24$.



A este número se lo escribe $4!$ y se lee cuatro factorial.

En general, $n!=1 \times 2 \times 3 \times \cdots \times (n-1) \times n$, es decir, $n!$ es el producto de todos los enteros desde $1$ hasta $n$. Los factoriales se usan muchísimo en combinatoria, como vamos a ver más adelante.



¿Pero qué pasa si yo tengo, por ejemplo, $k$ cajas, y tengo $n$ objetos distintos para meter, y tengo que meter exactamente uno en cada caja, cuántas formas hay?



Veámoslo con un ejemplo:



Tengo $3$ cajas, y tengo $5$ cosas para meter, y tengo que poner $1$ sola cosa en cada caja, ¿cuántas formas distintas de hacer esto hay?



Para la primer caja, tengo $5$ posibilidades, para la segunda tengo $4$, ya que una de las cosas la usé en la caja anterior, y ahora, para la tercer caja, tengo $3$, ya que otras $2$ fueron usadas en las primeras dos cajas. El total sería entonces $5\times 4\times 3 = 60$







¿Qué pasa si tengo $5$ cajas y $7$ cosas?



La cantidad de posibilidades sería, entonces,$7\times 6\times 5\times 4\times 3 = 2520$ formas.



Veamos si podemos generalizarlo para $k$ cajas, y $n$ objetos, con $k\leq n$ . Cabe aclarar que $k$ no puede exceder a $n$, porque entonces tendríamos más cajas que objetos, y quedarían cajas vacías, y la idea es meter un objeto en cada una.



La cantidad de posibilidades es: $n \times (n-1)\times (n-2) \times \cdots \times (n-k+1)$, ya que para la primera caja tenemos $n$ posibilidades, para la segunda tenemos $n-1$ porque ya usamos una, para la tercera tenemos $n-2$ y así siguiendo, para la $k$-ésima caja, es decir, para la ultima, tenemos $n-k+1$ (para la primera no restamos nada, para la segunda restamos $1$ porque ya fue usado ese objeto en la primer caja, para la tercera restamos $2$…y así, para la caja $k$, restamos $k-1$, es decir, hay $n - (k-1) = n - k + 1$ posibilidades para la caja en la posición $k$ (la última)



Entonces, como dijimos, la cantidad de posibilidades es $n \times (n-1)\times (n-2) \times \cdots \times (n-k+1)$.



Pero esto se puede escribir de otra forma, ya que si nos fijamos, esto es $\frac{n!}{(n-k)!}$ ya que al producto de los primeros $n$ enteros, le sacamos el producto de los primeros $n-k$ enteros y queda el producto de los enteros, desde $n-k+1$ hasta $n$, que era nuestro resultado.



Ahora, veamos si esto se cumple en los ejemplos que dimos:



Con $3$ cajas y $5$ cosas nos daba $60$, y efectivamente $60= \frac{5!}{2!}$, ya que $5 \times 4\times 3 = \frac{5 \times 4 \times 3 \times 2 \times1}{ 2 \times 1}$, es decir, estamos tachando lo que nos sobra.



Con $5$ cajas y $7$ cosas, el resultado era $2520$, y también $2520 = \frac{7!}{ 2!}$

(el $2!$ en este caso es porque $7-5=2$, que seria el $n-k$, ya que en este caso $n=7$ y $k=5$)



Conclusión: Si yo dispongo de $n$ objetos, y $k$ cajas, con $k\leq n$, la cantidad de formas distintas de meter $1$ objeto en cada caja es $\frac{n!}{(n-k)!}$



Veamos un último ejemplo de esto:



¿Cuántos números distintos de $3$ cifras distintas puedo formar con los números del $1$ al $7$?



Para la primera cifra, tengo $7$ posibilidades, para la segunda $6$, y para la tercera $5$, y esto es $7 \times 6\times 5$, que es lo mismo que $\frac{7!}{4!}$



Acá los $n$ objetos serian los números del $1$ al $7$ ($n=7$), las $k$ cajas serian las posiciones del numero de $3$ cifras ($k=3$), y el total es $\frac{n!}{(n-k)!} = \frac{7!}{4!} = 210$.



Volvamos al tema de formar números. Es claro que si yo quiero formar números de $5$ cifras usando una vez cada número del $1$ al $5$, la cantidad de números que puedo formar es $5!$.



Pero, ¿qué pasa si yo quiero formar números de $5$ cifras, con $1,\: 1,\: 2,\: 3,\: 4$?



La cantidad no será $5!$, porque si lo fuera estaríamos tomando a los dos $1$ como números distintos. Entonces escribamos así a las cifras: $1,\: 1',\: 2,\: 3,\: 4$.



Supongamos que tenemos un número, por ejemplo, $121'34$. ¿Qué pasa si cambiamos de posición el $1$ con el $1'$? Obtenemos el $1'2134$, que en realidad es igual al anterior si sacamos el $'$ que usamos para diferenciarlos. Y a esos dos casos los estamos tomando como distintos en caso de decir que la cantidad de permutaciones es $5!$ Por lo tanto, la cantidad real final de permutaciones, es decir, la cantidad de números de $5$ cifras usando$1,\: 1,\: 2,\: 3,\: 4$ será de $\frac{5!}{2}$.



En realidad el $\frac{5!}{ 2}$ es $\frac{5!}{ 2!}$, que sería la cantidad total de permutaciones si los números fueran distintos, dividido la cantidad de permutaciones de los números iguales, que yo estaría contando como distintos si dejo así nomás el $5!$.



Para entender mejor este concepto, veámoslo con otro ejemplo:



Tenemos la palabra $HAMACA$, y queremos ver cuantas palabras distintas podemos formar moviendo las letras. Pintemos de color las $A$, así las distinguimos:



$HAMACA$



Ahora, tomemos una palabra cualquiera que se forme con esas letras, por ejemplo,



$CAHAAM$, y veamos qué pasa si vamos cambiando solamente las $A$ de lugar



Obtenemos las siguientes palabras equivalentes:



$CA_1HA_2A_3M$



$CA_1HA_3A_2M$



$CA_2HA_1A_3M$



$CA_2HA_3A_1M$



$CA_3HA_1A_2M$



$CA_3HA_2A_1M$



Estas seis palabras en sí son iguales, pero las estaríamos contando como distintas si dijéramos que la cantidad total de palabras que podemos formar es $6!$







Y esto pasaría con cualquier palabra, para cada palabra, habría $6$ formas de variar los colores de las $A$, y quedaría la misma palabra con los colores en otro orden. Por lo tanto, al $6!$, lo tenemos que dividir por $6$. Ese $6$ es en realidad un $3!$, que justamente es la cantidad de formas distintas de ordenar las tres $A$.



Ejemplos:



La cantidad de palabras distintas moviendo las letras de $CASA$ es $\frac{4!}{ 2!}= 12$,



$CASA$

$CAAS$

$CSAA$

$SACA$

$SAAC$

$SCAA$

$ACAS$

$ACSA$

$ASCA$

$ASAC$

$AACS$

$AASC$



¿Pero qué pasa por ejemplo si yo tengo la palabra $ANANA$?



Tendría que dividir el $5!$ por la cantidad de formas de ordenar las $A$ y la cantidad de formas de ordenar las $N$.



Así, el total nos queda $\frac{5!}{3!\: 2!}= 10$ palabras.



($3!$ Es la cantidad de formas de ordenar las tres $A$, y $2!$ las formas de ordenar las dos $N$, por eso dividimos por $3!2!$, ya que de otro modo estaríamos tomando a las $A$ como letras distintas, y lo mismo con las $N$)



(Empezamos por $5!$ porque $ANANA$ tiene $5$ letras, y si fueran todas distintas la cantidad de palabras que podríamos formar sería $5!$)



Un último ejemplo:



¿Cuántas palabras distintas puedo formar moviendo las letras de $MISSISSIPPI$?



$\frac{11!}{4!4!2!} = 34650$



$11!$ porque son $11$ letras en total, y dividimos primero por $4!$ porque hay cuatro $I$, de nuevo por $4!$ porque hay cuatro $S$, y finalmente por $2!$ porque hay dos $P$.





Si esto lo usamos con números en vez de letras, es lo mismo, salvo que aparezca algún $0$, ahí la cosa cambia porque los números no pueden empezar por $0$, y tendríamos que dividirlo en casos.







Veamos un ejemplo de esto:



¿Cuántos números distintos de 6 cifras puedo formar con los dígitos $0,\: 1,\: 1,\: 2,\: 2,\: 3$?



Si empieza con 1, las otras 5 cifras son$0,\: 1,\: 2,\: 2,\: 3$, y se pueden ordenar de $\frac{5!}{2!}=60$ maneras



Si empieza con 2, las otras 5 cifras son $0,\: 1,\: 1,\: 2,\: 3$, y se pueden ordenar de $\frac{5!}{2!}=60$ maneras



Si empieza con $3$, las otras $5$ cifras son $0,\: 1,\: 1,\: 2,\: 2$, y se pueden ordenar de $\frac{5!}{2!\: 2!}=30$ maneras.



El total sería entonces $30 + 60 + 60 = 150$







Problema 2: Soy un jeque árabe, y tengo $7$ camisas, pero tengo que elegir sólo $3$ para irme de viaje a Argentina, ¿de cuántas formas puedo hacerlo?



Asignamos un número a cada camisa, $1$ si la llevo, y $0$ si no la llevo. Si ponemos los $7$ números formando uno solo, obtenemos un número de $7$ cifras, que puede o no empezar por $0$. Ahora, ¿cuántas formas hay de formar números distintos moviendo sus dígitos?



En total son $7$ dígitos, tres son $1$, y cuatro son $0$, entonces la cantidad de posibilidades será $\frac{7!}{3!\: 4!}=35$





Otro ejemplo: Voy a una heladería, que dispone de $10$ gustos en total, pero en mi cucurucho entran $2$. ¿De cuántas formas puedo elegir los gustos, si no me importa qué gusto esta arriba?



Nuevamente, asignamos un $1$ a los gustos que elegimos, y un $0$ a los que no. En total van a ser $10$ números, dos $1$ y ocho $0$, por lo tanto la cantidad de formas de elegir $2$ gustos entre $10$ será de $\frac{10!}{8!\: 2!}=45$.



Generalizando, si yo tengo $n$ cosas distintas, y quiero elegir $k$, con $k\leq n$ , asigno un $1$ a $k$ de los números, y un $0$ a los restantes $n-k$. Esto se puede hacer de $\binom{n}{k}=\frac{n!}{k!\: (n-k)!}$

formas, ya que habrá $n$ números, $k$ unos, y $n-k$ ceros.



Los números de esa forma son conocidos como números combinatorios, y se escriben así:



$\binom{n}{k}=\frac{n!}{k!\: (n-k)!}$

y representan la cantidad de formas distintas de elegir $k$ cosas entre $n$,

sin importar el orden en el cual son elegidas.















Veamos un último ejemplo: Mariano es mi entrenador de olimpíadas, y me dijo que quedemos en vernos dos veces por semana, fines de semana incluidos. ¿De cuántas formas puedo elegir los dos días?



En la semana hay $7$ días, y tengo que elegir $2$, esto lo puedo hacer de $\binom{7}{2}=\frac{7!}{2!\: 5!}=21$ formas.





Para cerrar, vale la pena decir que estas son herramientas que ayudan a que salgan más rápido los problemas, pero no podemos esperar hacer todo en una cuenta con $20$ factoriales. En general se suele dividir el problema en partes, y usar estas cosas varias veces para calcular la cantidad de combinaciones de cada partecita.

Pequeño Teorema de Fermat:
Si [math]p es primo y [math]a es un entero entonces [math]a^p\equiv a \pmod p. En otras palabras, [math]a^p-a es múltiplo de [math]p.