Material de Entrenamiento OMM

Combinatoria
Profesores
Mayo 2016

1 Paridad
Un número se dice par si se puede dividir exactamente por dos, en caso contrario se dice impar. La paridad
de un número es par o impar dependiendo si el número lo es.

Ejemplo 1. Números pares son −8, 0, 2, 10, 36, 128.

Ejemplo 2. Números impares impares son −13, −1, 7, 25, 321.
Observación 1. Todo número par es de la forma 2n para algún entero n. Ej. −28 = 2(−14), 0 =
2(0), 324 = 2(162).

Observación 2. Todo número impar es de la forma 2n + 1 para algún entero n. Ej. −15 = 2(−8) + 1, 7 =
2(3) + 1, 35 = 2(17) + 1.
Observación 3. La suma de dos números pares da como resultado un número par.
La suma de dos números impares da como resultado un número par.
La suma de un número par más un número impar da como resultado un número impar.
La multiplicación entre números pares da como resultado un número par.
La multiplicación entre números impares da como resultado un número impar.
La multiplicación entre un número par por un número impar da como resultado un número par.

1.1 Problemas para discutir

Ejercicio 1. En un tablero de ajedrez. ¿Puede un caballo regresar a su posición original después de once
movimientos?
Solución 1. Notemos que cada vez que se mueve el caballo, lo hace de tal manera que si se encuentra en
una casilla blanca cambia a una casilla negra y si se encuentra en una casilla negra cambia a una casilla
blanca. Entonces, para llegar a una casilla del mismo color, lo tendrá que hacer en una cantidad par de
movimientos. Ası́, como 11 es un número impar, no podrá haber llegado a la casilla original.
Ejercicio 2. ¿Puede un tablero de damas de 15 × 15 ser cubierto por fichas de dominó de 2 × 1?
Solución 2. Observemos que lado cada ficha de dominó cubre 2 cuadritos, entonces sin importar cuantas
fichas de dominó tengamos, la cantidad de cuadritos que éstas cubrirán en total deberá de ser un número
par. Por otro lado Observemos que el tablero tiene un total de 225 cuadritos, que es un número impar. Por
lo tanto no puede ser cubierto por las fichas de dominó.
Ejercicio 3. El producto de 34 números enteros es igual a 1. Pruebe que su suma no puede ser cero.

1
Solución 3. Como el producto de los 34 número es 1, la única posibilidad para que esto suceda es que todos
los números sean 1 o −1. Ahora, si buscamos que la suma de todos sea cero, entonces deberá haber mitad de
1’s y mitad de −1’s, es decir 17 de cada grupo. Sin embargo, si esto ocurre, la multiplicación de 17 números
1 por 17 números −1 da como resultado −1. Ası́, ambas situaciones no pueden ocurrir a la vez.
Nota para el Profesor 1. Observemos que en cada uno de los ejercicios se usaron implı́citamente las
observaciones enunciadas al inicio. Principalmente las propiedades de suma y multiplicación fueron necesarias
para plantear y resolver los problemas.

1.2 Problemas para resolver

1. En un tablero de ajedrez. ¿Puede ir un caballo de una esquina a la esquina opuesta pasando por cada
casilla una sola vez?
2. Consideremos todas las fichas de un dominó acomodadas en cadena (si dos fichas están juntas es porque
tienen el mismo número de puntos del lado donde están juntas). Diga si es posible construir una cadena
que empiece en 5 y termine en 4.

3. En un tablero de damas de 25 × 25, son colocadas 25 fichas de damas de tal manera que quedan
simétricas respecto de la diagonal. Pruebe que al menos una dama queda justo sobre la diagonal del
tablero.
4. Los números del 1 al 10 son escritos en un renglón con los signos + o − antes de cada número. Diga
si es posible que la suma de esos números de cero.

1.3 Soluciones
1. En total el tablero tiene 64 casillas, por lo tanto si se quiere ir de esquina a esquina pasando por todas
las casillas deberá hacerse en exactamente 63 movimientos. Sin embargo, como las esquinas opuestas
son del mismo color, para llegar de una a otra el caballo necesita una cantidad par de movimientos.
Por lo tanto es imposible llegar en 63 movimientos.
2. Probaremos que cada que una cadena completa debe iniciar y terminar en el mismo número. Supong-
amos que la ficha [5, 5] se encuentra en un extremo de la cadena, para continuar la cadena debemos
poner otra ficha con que tenga un cinco, esto nos deja con 5 fichas más que tengan algún cinco. Por
otro lado, cuando coloquemos cualquiera de ellas debemos continuar con otra más, es decir que se usan
por pares. Finalmente como debemos usar todas las fichas, la cadena deberá terminar en cinco. Ahora
si en un extremo de la cadena se encuentra una ficha de la forma [5, n], con n 6= 5, se tiene que en
algún momento debemos colocar la ficha [5, 5] y esto no puede ser en el extremo, pues serı́a el caso
anterior, en consecuencia cuando la coloquemos debemos usar en total 3 fichas, lo que nos deja con
3 fichas más que tienen algún cinco. Usando un razonamiento similar, la cadena deberá terminar en
cinco nuevamente.
3. Notemos que el tablero de damas se puede dividir en tres regiones: la diagonal y las dos regiones
triangulares que quedan por abajo y por arriba de la diagonal. Ahora, como las fichas se encuentran
simétricas respecto a la diagonal, se tiene que si hay alguna ficha en alguna de las dos regiones trian-
gulares, deberá haber otra ficha en la otra región triangular. Por lo tanto la cantidad de fichas en las
regiones triangulares es par, y como tenemos una cantidad impar de fichas, alguna deberá estar justo
en la diagonal.
4. En total tenemos cinco números pares y cinco números impares. La suma de los cinco pares es par y
la suma de los cinco impares es impar, por lo tanto la suma total deberá de ser impar, que tiene que
ser distinto de cero pues cero es par.

2
Nota para el Profesor 2. En algunos de los problemas anteriores vale la pena sugerir algunas preguntas
adicionales después de analizar la solución. Por ejemplo en el Problema 3 se puede preguntar ¿qué pasarı́a si
las fichas quedan simétricas respecto a las dos diagonales? En éste caso una ficha deberı́a quedar una ficha
en el centro del tablero. Otro ejemplo de pregunta adicional en el Problema 4 es ¿qué ocurre si en vez de
tener sólo los números del 1 al 10 se tienen los números del 1 al 1000? En donde con un argumento similar
se concluye la misma respuesta.

2 Principios de conteo
En los siguientes problemas se pide contar cierta cantidad de objetos que satisfacen alguna condición. Las
técnicas utilizadas para realizar este tipo de conteos se enuncian a continuación.
1. Principio fundamental de conteo. Si una primera tarea puede realizarse de n maneras y a su vez una
segunda tarea puede realizarse de m maneras, entonces ambas tareas pueden realizarse juntas de n · m
maneras.
2. Factorial de un número. Definimos el factorial de un número n ≥ 0, como el producto de todos los
enteros positivos menores o iguales que n, escribimos
n! = 1 × 2 × 3 . . . ×n
por convención definimos 0! = 1.
3. Permutaciones. Para n ≥ k, si se quieren acomodar n objetos en k lugares y el orden importa, el
número de formas posibles para hacerlo es
n!
(n − k)!

4. Combinaciones. Para n ≥ k, si se quieren elegir k elementos de un conjunto de n elementos sin importar

el orden, el número de formas posibles para hacerlo es
 
n n!
=
k (n − k)!k!

2.1 Problemas para discutir

Ejercicio 4. Para viajar de Durango a Cancún, se puede realizar un viaje en autobús de Durango a la
Ciudad de México y una vez ahı́ tomar un vuelo hacia Cancún. Si hay 9 corridas de autobús Dgo-CDMX y
sólo 4 vuelos CDMX-Cancún, ¿de cuántas maneras distintas se puede realizar el viaje?
Solución 4. Se usa directamente el principio fundamental de conteo. La primera tarea consiste en realizar
el viaje en autobús para la cual tenemos 9 posibilidades y para la segunda tarea, que es tomar el vuelo,
tenemos 4 opciones. Finalmente el total de formas distintas es 9 · 4 = 36.
Ejercicio 5. En Letrolandia todas las palabras tienen a lo más cuatro letras y el alfabeto consta únicamente
de las letras A, B, C, ¿cuántas palabras distintas se pueden formar con éstas caracterı́sticas?
Solución 5. Contamos las palabras de una, dos, tres y cuatro letras y sumamos al final, obteniendo un total
de 3 + 32 + 33 + 34 = 120.
Ejercicio 6. En una bolsa hay 6 pelotas azules y 4 pelotas rojas, ¿de cuántas maneras podemos colocarlas
en una fila?
Solución 6. El problema se puede analizar de la siguiente manera, en total tenemos 10 espacios para llenar,
podemos acomodar las 4 bolas azules en los 10 y el resto de espacios vacı́os los ocupamos con las
bolas rojas.
El número de formas en las que podemos acomodar las 4 bolas azules en los 10 espacios es 10 4 .

3
2.2 Problemas para resolver
1. ¿De cuántas maneras se pueden colocar un rey negro y un rey blanco, en un tablero de ajedrez, de tal
manera que no se ataquen?
2. ¿Cuántos números de diez cifras hay, tales que todas sus cifras tengan la misma paridad?

3. ¿Cuántas palabras distintas se pueden formar usando todas letras de la palabra ”MATEMATICA”?
4. ¿De cuantas maneras podemos elegir tres rebanadas de pizza, de manera que dos rebanadas elegidas
no sean consecutivas?
5. En una clase de baile asisten n niños y n niñas. ¿De cuántas maneras se pueden acomodar en parejas
para tomar la clase?
6. Se tienen 8 piezas de ajedrez: 2 torres, 2 alfiles, 2 caballos y 2 peones. De cada uno de los cuatro tipos
de piezas, una es blanca y la otra negra. ¿De cuántas maneras se pueden acomodar las ocho piezas
en una columna de un tablero de ajedrez, de tal manera que ninguna pieza quede en un cuadro de su
color?

7. Hay tres habitaciones en un dormitorio, una sencilla, una doble y una cuádruple. ¿De cuántas maneras
se pueden acomodar siete estudiantes en el dormitorio?
8. ¿De cuántas formas se pueden colocar los números de 1 al 7 en los puntos marcados en la figura de tal
forma que la suma de los números en los triángulos sombreados sea la misma?

9. ¿De cuántas maneras se pueden elegir dos fichas de dominó, de tal forma que tengan un número en
común?
10. Consideremos todos los posibles productos distintos que se pueden obtener multiplicando al menos dos
elementos del conjunto {1, 2, 3, 4, . . . , 2016}. ¿Cuál es la suma de todos esos productos?

11. Un domador de leones quiere colocar 5 leones y 4 tigres en una fila, de manera que ningún tigre quede
junto a otro tigre. ¿De cuántas maneras puede hacerlo?
¿De cuántas formas puede hacer el domador un arreglo de 9 animales salvajes (tigres o leones) de tal
manera que no haya dos tigres juntos, pero puede usar cualquier cantidad de tigres o leones?

Nota para el Profesor 3. Durante la sesión de problemas, siempre hay algunas sugerencias que se pueden
comentar al momento de analizar los problemas. Por ejemplo, en el Problema 1 se puede comentar las
distintas que las distintas posibilidades de ataque dependen de las posiciones de las piezas. En el Problema
3, que el uso de letras iguales no cambia una palabra si sólo éstas se intercambian de posición entre sı́, se
puede hacer un ejemplo que lo exhiba. En el Problema 8, que el número del centro juega un papel importante.
O en el Problema 10, analizar casos más sencillos con menos números, en donde todos los productos posibles
se obtengan en pocos pasos.

4
2.3 Soluciones
1. El rey blanco puede estar en 64 posiciones diferentes. Sin embargo, las posibilidades de ataque varı́an
dependiendo de la posición. Analizamos cada caso.
Si el rey blanco se encuentra en una de las cuatro esquinas. Entonces para cada una de las esquinas
hay 60 casillas en donde podemos colocar el rey negro.
Si se encuentra en alguno de los bordes del tablero, que no son esquinas, hay 58 casillas posibles para
el rey negro. Se tienen 24 casillas de este tipo.
Por último, si no se encuentra en ningún borde del tablero, se tienen 55 casillas en donde se puede
colocar rey negro. Son en total 36 casillas como esta.
Sumamos los totales y obtenemos 4 × 60 + 24 × 58 + 36 × 55 = 3612.

2. Si todas las cifras de número son impares se tienen 510 números posibles. En cambio si todas las cifras
son pares, como no se puede usas el cero al inicio, se tienen 4 · 59 posibilidades. La suma de ambos es
el resultado final.
3. Si las diez letras fueran distintas, total de palabras que se pueden formar es 10!; sin embargo, hay que
considerar que si dos o más letras iguales se cambian de lugar entre si, se obtiene un acomodo diferente
pero la palabra es la misma. Esta situación ocurre para todos los posibles movimientos de las tres
letras A’s, las dos letras M’s y las dos letras T’s. En consecuencia el total de palabras que se pueden
formar es
10!
3!2!2!
4. Una manera de ver el problema es contar el total de formas para elegir tres rebanadas de la pizza y
luego ver en cuántos casos hay dos

o más rebanadas juntas. El número de formas posibles para elegir
tres de las ocho rebanadas es 83 = 56. Ahora hay 8 maneras distintas en las que están las tres juntas
(ponerlas juntas en una posición y luego rotarlas). Ahora, las formas en que están dos juntas y una
separada se pueden contar de la siguiente manera: poner las dos juntas en una posición, luego elegir
la tercera de manera que haya una, dos, tres o cuatro rebanadas con las otras dos en el sentido de
las manecillas del reloj. En total son cuatro posibilidades, luego las rotamos ocho veces cada una y
obtenemos un total de 32 casos posibles. Haciendo la resta se tiene que hay 16 formas en las que
quedan las tres rebanadas separadas.
5. Si sólo tuviéramos un niño tenemos n posibilidades para elegirle pareja, si tuviéramos dos serı́an n(n−1),
n formas para el primero y n − 1 para el el segundo niño, si tuviéramos 3 serı́an n(n − 1)(n − 2), de
esta manera si tenemos n niños, el resultado serı́a n!.
6. En una columna de un tablero de ajedrez se tienen 4 casillas negras, en las cuales debemos acomodar
las cuatro piezas blancas, esto puede hacerse de 4! formas diferentes. Análogamente para acomodas
las 4 piezas negras en las restantes 4 casillas blancas se tienen 4! posibilidades. Por último el total de
acomodos será 4! × 4! = 576.
7. Imaginemos las siete camas ordenadas como sigue: primero colocamos la cama de cuarto sencillo, luego
las dos del cuarto doble y al final las cuatro del cuarto restante. Si queremos acomodar a los siete
estudiante en las camas, tendremos 7! maneras de hacerlo. Sin embargo al considerar las habitaciones
por separado, no importa el orden en que llegaron los estudiantes a una misma habitación, es decir que
algunas se repiten dependiendo de cómo se pueden acomodar los estudiantes en esa misma habitación,
en conclusión tendremos
7!
1!2!4!
.
8. La suma de los números 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Llamémosle n al numero central. Como queremos
que la suma de los tres triángulos sombreados sea la misma, entonces 28 − n debe ser divisible entre

5
 tres. Luego n sólo puede ser 1, 4, o 7. Analizamos cada caso por separado.
Para n = 1, la suma de los otros dos vértices en cada triángulo sombreado deberá ser 28−1 3 = 9. Luego,
las posibilidades para los vértices en los triángulos sólo pueden ser: 2 con 7, 3 con 6 y 4 con 5.
Para n = 4, la suma de los otros dos vértices en cada triángulo sombreado deberá ser 28−4 3 = 8. Luego,
las posibilidades para los vértices en los triángulos sólo pueden ser: 2 con 6, 3 con 5 y 1 con 7.
Para n = 7, la suma de los otros dos vértices en cada triángulo sombreado deberá ser 28−7 3 = 7. Luego,
las posibilidades para los vértices en los triángulos sólo pueden ser: 1 con 6, 2 con 5 y 4 con 3.
Finalmente contamos las posibles formas de acomodar. Para el número central tenemos 3 posibilidades,
una vez elegido tenemos tres parejas de números para completar los vértices en cada triángulo som-
breado que se pueden acomodar de 3! formas distintas, finalmente una vez que se elige en qué triángulo
va cada pareja de números, éstos a su vez se pueden cambiar de vértices de 23 maneras diferentes. Ası́
el número de configuraciones distintas es 3 × 3! × 23 = 144.
9. La primera ficha se puede elegir de 28 formas. Pero, de éstas, 7 son “mulas” (mismo número
en ambos lados). Si la ficha elegida tiene el mismo número en ambos lados, entonces la segunda
ficha se puede elegir de 6 formas (por ejemplo la [1|1] se puede acoplar con cualquiera de las fichas
[1|0], [1|2], [1|3], [1|4], [1|5], [1|6].De otra manera (cuando el número es diferente en cada lado de la
primera ficha), la segunda ficha se puede elegir de 12 formas (por ejemplo, la [0|1] se puede acoplar con
cualquiera de las fichas, [0|0], [0|2], ..., [0|6], [1|1], [1|2], ..., [1|6]).De acuerdo al principio multiplicativo,
hay 42 formas para el primer caso y 252 para el segundo. El total de posibilidades de elección serı́a
42 + 252 = 294.Pero como el orden en que se eligen las fichas es irrelevante, la respuesta final es la
mitad de 294, es decir, hay 147 formas de elegir dos fichas con algún número en común de las 28 del
dominó.

10. Notemos que al desarrollar el producto

(1 + 1)(1 + 2)(1 + 3) . . . (1 + 2015)(1 + 2016)

cada sumando en cada uno de los productos buscados, salvo el 1 · 1 . . . ·1 = 1. Finalmente la suma
buscada es el producto anterior menos uno, es decir 2017! − 1.

11. Para que dos tigres no queden juntos, estos tendrán que estar separados por al menos un león. Entonces
podemos proceder de la siguiente manera. Se pueden colocar los 5 leones en fila, de manera que dejemos
un espacio vacı́o antes del primer león, otro espacio al final del último león y un espacio más entre cada
dos leones, esto se ve como *L*L*L*L*L* donde los asteriscos se pueden pensar como los 7 espacios
vacı́os. Luego para tener un acomodo donde no estén dos tigres juntos basta colocarlos en
esos espacios
vacı́os, ya que estarán separados por leones, el número de formas para hacer esto es 73 . El caso en el
que se usan distintas cantidades de animales se resuelve de manera similar.