Entrenamiento para Olimpiadas de Matemática
Contando de dos Formas
Emerson Soriano
Lista 1 Grupo de Olimpiadas, Jorge Basadre
En muchas ocasiones hay máss de una forma de contar los elementos de un conjunto.
A veces una de estas formas es más fácil de identi car, o incluso puede ser su ciente
para responder un problema. Sin embargo, existen ocasiones en las que encontrar formas
alternativas para contar los elementos de un conjunto nos ayuda a encontrar la solución
de un problema, o bien, nos permite obtener resultados interesantes.
La técnica de doble conteo es muy poderosa. Sin embargo, una de las principales
di cultades es que a veces no se ve fácilmente dónde podemos usarla. A través de la
solución de varios problemas esperamos dar una mejor idea del tipo de situaciones donde se
puede utilizar. Suponemos que el lector maneja los principios básicos de conteo. También
usaremos la notación de suma y sus propiedades.
La idea principal es encontrar un conjunto que se pueda contar de dos formas distintas.
Veremos un par de ejemplos introductorios y en la siguiente sección veremos algunos
ejemplos más avanzados.
1. El Principio de Doble Conteo
Todas las demostraciones por doble conteo se basan en el siguiente principio.
Principio de Doble Conteo. Si contamos la cantidad de objetos de cierto conjunto de
una forma y resulta a y luego las contamos de otra forma y resulta b, entonces a = b.
Parece un principio muy sencillo y su demostración es igual de sencilla: ambos números
son iguales pues tanto a como b son la cantidad de elementos en el conjunto. La utilidad
del principio del doble conteo se basa en que encontremos dos formas distintas y correctas
de contar los elementos de un conjunto. Un ejemplo es la manera en la que demostramos
la fórmula para la suma de los primeros n enteros positivos. Nos gustaría encontrar una
fórmula similar para la suma de los primeros n cuadrados. Pero antes de hacer esto, vamos
a usar el Principio de Doble Conteo para demostrar algunas identidades de coe cientes
binomiales.
Ejemplo 1.1. Demostrar que, para todo entero positivo n,
n
X n(n + 1)
i=
k=1
2
1
Combinatoria 1 EL PRINCIPIO DE DOBLE CONTEO
Prueba. Sobre la recta numérica pintamos de rojo los puntos del 0 al n, inclusive. La
idea es contar la cantidad de segmentos que podemos formar con esos puntos rojos. En
efecto, es claro que cada par de puntos rojos determinan un segmento, en síntesis, como
hay n+12
= n(n+1)
2
parejas de puntos rojos, entonces hay exactamente n(n+1)
2
segmentos.
Por otro lado, hay 1 segmento de longitud n, 2 segmentos de longitud n − 1, 3 segmentos
de longitud n − 2, y así sucesivamente, n segmentos de longitud 1. Como hemos contado
la misma cosa, podemos deducir que
n(n + 1)
1 + 2 + 3 + ··· + n =
2
Ejemplo 1.2. En un salón hay 25 alumnos que estudian 7 temas. Se sabe que a cada
alumno le gustan al menos dos temas. Demuestre que existe un tema que le gusta al menos
a 8 personas.
Ejemplo 1.3. Para cada pareja de enteros m, n, con 0 6 m 6 n, probar que
n n
=
m n−m
Ejemplo 1.4. Demostrar que, para todo entero positivo n,
n
X n
= 2j
j=0
j
Ejemplo 1.5. Probar que para cada entero positivo n,
n
X n
i = n · 2n−1
i=1
i
Ejemplo 1.6. Para cada pareja de enteros no negativos m, n, probar que
m
X n+k n+m+1
=
i=0
n n+1
Ejemplo 1.7. Probar que para todo entero positivo n,
n
X n(n + 1)(2n + 1)
i2 =
i=1
6
Ejemplo 1.8. Probar que para todo entero n > 0,
bX
2c
n
n−k
= Fn+1
k=0
k
donde Fj denota el j−ésimo número de Fibonacci.
2
Combinatoria 2 PRINCIPIO DE DOBLE CONTEO CON NOTACIÓN DE PAREJAS
2. Principio de Doble Conteo con Notación de Parejas
Proposición 2.1. Consideremos dos conjuntos nitos no vacíos A y B . Sea S un sub-
conjunto no vacío de A × B . Denotemos por ai el número de parejas de S cuya primera
coordenada es i. Denotemos por bj el número de parejas de S cuya segunda coordenada
es j . Entonces, X X
ai = bj
i∈A j∈B
Ejemplo 2.1. Probar que si n es un entero positivo, entonces
n
X
2k = 2n+1 − 1
k=0
Ejemplo 2.2. Se tiene un 2010−ágono regular. Se pintan 1005 de sus vértices de rojo y
los demás vértices de azul. Demuestre que se pueden elegir dos polígonos de 503 vértices,
uno con vértices rojos y el otro con vértices azules, de modo que sean congruentes.
Proposición 2.2. Considere un tablero de m las y n columnas, de modo que en cada
casilla esté escrito un 0 o un 1. Se de ne por ci a la suma de todos los números en la
i−ésima columna, para i = 1, 2, ... , n. Suponga que existe ` tal que, para cada par de
las, existen exactamente ` columnas que tienen unos en ambas las. Entonces,
X n
m ci
` =
2 i=1
2
Ejemplo 2.3. (IMC 2002) En una competencia de matemática participan 200 estudian-
tes. La prueba consiste de seis problemas. Se sabe que cada problema fue resuelto por al
menos 120 estudiantes. Demostrar que existen dos estudiantes tal que, cada problema fue
resuelto por al menos uno de ellos.
Ejemplo 2.4. Sean los conjuntos A1 , A2 , ..., Ak ⊂ {1, 2, ..., n} tales que
n
|Ai | > , para todo i = 1, 2, ... , k .
2
n
|Ai ∩ Aj | 6 , para todo 1 6 i, j 6 n, con i 6= j .
4
Probar que
k
[ kn
Ai >
i=1
k+1
Ejemplo 2.5. Para cada entero positivo n, sea d(n) el número de divisores positivos de
n. Para cada entero positivo n, se de ne `(n) de la siguiente forma
n
1X
`(n) = d(i)
n i=1
Demuestre que
n n
X 1 X 1
6 `(n) 6
i=2
i i=1
i
3
Combinatoria 3 PROBLEMAS DE ENTRENAMIENTO
3. Problemas de Entrenamiento
Problema 3.1. En un torneo de ajedrez, cada participante juega exactamente una vez
contra cada uno de los demás. Cada jugador recibe 1 punto por cada partido ganado, 1/2
punto por cada partido empatado y 0 puntos por cada partido perdido. Si cada jugador
obtiene la misma cantidad de puntos contra hombres y contra mujeres, demostrar que la
cantidad de participantes es un cuadrado perfecto.
Problema 3.2. En un comité, cada miembro pertenece a exactamente tres subcomités y
cada subcomité tiene exactamente tres miembros. Demuestre que la cantidad de miembros
es igual a la cantidad de subcomités.
Problema 3.3. Un album, compuesto por 2011 guritas, está siendo coleccionado por
33 amigos. Una distribución de guritas entre los 33 amigos es imcompleta cuando existe
por lo menos una gurita que ninguno de los 33 amigos tiene.
Determine el menor valor de m con la siguiente propiedad: toda distribución de guritas
con 33 amigos tal que, para cualquier par de amigos, faltan, para ambos, por lo menos m
guritas en común, es incompleta.
Problema 3.4. (Teorema de Euler) Un poliedro es un sólido delimitado por por polígo-
nos. Sean V , A, C los número de vértices, aristas y caras, respectivamente. Demuestre
que
V − A + C = 2.
Problema 3.5. (Lema de Sperner) Dividimos un triángulo grande T en triángulos pe-
queños, de modo que cada par de triángulos pequeños, o no tienen un vértice en común,
o tienen un vértice en común o tienen un lado (completo) en común. Los vértices de T se
enumeran con los números: 1, 2 y 3. Los vértices de los triángulos pequeños son enume-
rados con los números 1, 2, 3 de manera arbitraria, excepto que, si un vértice v , que no
sea vértice de T , pertenece a un lado ` de T , entonces a v no se le asigna el número del
vértice de T que es opuesto de `. Entonces, entre los triángulos pequeños existe uno de
ellos cuyos vértices tienen los números 1, 2 y 3.
Problema 3.6. (Lista Corta, IMO 2004) Hay 1001 estudiantes en una universidad. Los
estudiantes se juntan en pandillas (un estudiante puede estar en varias pandillas) y las
pandillas se juntan en sociedades (una pandilla puede estar en varias sociedades). Suponga
que hay k sociedades y que se cumple lo siguiente:
Cada pareja de estudiantes está en exactamente una pandilla.
Por cada estudiante y cada sociedad, el estudiante pertenece a exactamente una
pandilla de la sociedad.
Cada pandilla tiene una cantidad impar de estudiantes. Además, si una pandilla
tiene ` estudiantes, con ` > 0, entonces está en exactamente ` sociedades.
Determine todos los posibles valores de k .
