Cuadernillo de problemas resueltos: conteo, logica y grafos

Las matematicas discretas son el andamiaje logico de la informatica: como contar sin enumerar, como demostrar que algo es cierto y como razonar sobre redes de relaciones. Este cuadernillo cubre los nueve tipos de problema que caen en cualquier examen de la materia, con soluciones completas. Al final del semestre te servira tambien para probabilidad (todo conteo es un espacio muestral) y para estructuras de datos (todo grafo es una estructura).

Diagrama de matematicas discretas: grafo con nodos conectados, puertas logicas y diagramas de Venn. — Logica, conteo y grafos: las tres columnas de las matematicas discretas.

Metodo de estudio En demostraciones e induccion, la notacion lo es todo: copia las soluciones respetando el nombre de variables y los cuantificadores. En conteo, preguntate SIEMPRE: importa el orden (permutacion) o no (combinacion)?

Bloque 1 · Logica y demostracion

Problema 1. Traduce a simbolos: "Si estudio y repaso, entonces apruebo" y construye la tabla de verdad de (p ∧ q) → r.

Solución paso a paso

Atomicemos: p = "estudio", q = "repaso", r = "apruebo". La frase es (p ∧ q) → r.
Con 3 variables hay 2^3 = 8 filas. La conjuncion p ∧ q solo es V cuando ambas son V.
La implicacion A → B solo es FALSA cuando A es V y B es F. Aqui A = (p ∧ q) es V solo en la fila (V,V); de las dos filas con (p,q) = (V,V), la que tiene r = F hace falsa la implicacion.
Resultado: la formula es falsa exactamente en la fila (p,q,r) = (V,V,F): solo 1 de 8 filas. Es decir: "estudiar y repasar sin aprobar" es el unico contraejemplo.

Problema 2. Niega formalmente la frase: "Para todo estudiante x existe un curso y tal que x aprueba y", y explica la negacion en español.

Solución paso a paso

Simbolos: ∀x ∃y A(x,y).
Regla de negacion en cascada: ¬∀ = ∃; ¬∃ = ∀; y la predicacion final se niega: ¬∀x ∃y A ≡ ∃x ∀y ¬A.
En español: "Existe al menos un estudiante que no aprueba NINGUN curso" (es decir, todos los cursos se le niegan).
Ojo con la trampa: "no todos aprueban todo" NO significa "nadie aprueba nada". La negacion solo toca el primer cuantificador que encuentra.

Problema 3. Demuestra por induccion que 1 + 2 + ... + n = n(n + 1)/2 para todo n ≥ 1.

Solución paso a paso

Caso base (n = 1): izquierda = 1; derecha = 1·2/2 = 1. Cierto.
Hipotesis inductiva: supongamos la formula cierte para n = k, o sea 1 + ... + k = k(k+1)/2.
Paso inductivo: 1 + ... + k + (k+1) = k(k+1)/2 + (k+1) por la hipotesis.
Factoriza (k+1): = (k+1)(k/2 + 1) = (k+1)(k+2)/2 = n(n+1)/2 con n = k+1. La formula se propaga al siguiente: por induccion, vale para todo n.

Bloque 2 · Conteo y cardinalidad

Problema 4. En un grupo de 30 estudiantes, 18 juegan futbol, 15 basquetbol y 7 ambos. ¿Cuantos no juegan nada?

Solución paso a paso

Inclusion-exclusion: |F ∪ B| = |F| + |B| − |F ∩ B| = 18 + 15 − 7 = 26.
Complemento: 30 − 26 = 4 estudiantes no juegan nada.
Lee el diagrama de Venn: solo futbol = 11, solo basket = 8, ambos = 7; suma 26. La interseccion se resta porque se conto dos veces.

Problema 5. ¿Cuantas palabras distintas (con o sin sentido) se forman reordenando las letras de MISSISSIPPI?

Solución paso a paso

Cuenta las letras: 11 total: M(1), I(4), S(4), P(2).
Permutaciones con repeticion: 11!/(1!·4!·4!·2!).
Calcula: 39,916,800 / (24·24·2) = 39,916,800 / 1152 = 34,650 palabras.
La idea: si las 4 I fueran distinguibles, cada palabra apareceriria 4 veces; dividir por 4! colapsa los duplicados.

Problema 6. Un comite de 3 se elige al azar entre 5 mujeres y 4 hombres. ¿Cual es la probabilidad de que todas las personas del comite sean mujeres? ¿Y de que haya al menos un hombre?

Solución paso a paso

Espacio muestral: C(9,3) = 84 comites posibles (no importa el orden).
Comites todo-mujeres: C(5,3) = 10. Probabilidad: 10/84 ≈ 0.119.
"Al menos un hombre" es el complemento de "ningun hombre": 1 − 10/84 = 74/84 ≈ 0.881.
Patron: ante "al menos", cuenta el cero. Contar directamente los comites con 1, 2 o 3 hombres exige tres calculos; el complemento, uno.

Bloque 3 · Recurrencias y grafos

Problema 7. Resuelve la recurrencia a(n) = a(n−1) + 2n con a(0) = 1, hallando una formula cerrada.

Solución paso a paso

Desenrolla: a(n) = a(0) + suma de 2k para k de 1 a n = 1 + 2·(1 + 2 + ... + n).
Usa Gauss: 1 + ... + n = n(n+1)/2. Entonces a(n) = 1 + 2·n(n+1)/2 = 1 + n(n+1).
Verifica dos terminos: a(1) = 1 + 2 = 3 y la formula da 1 + 1·2 = 3 ✓; a(2) = 3 + 4 = 7 y 1 + 2·3 = 7 ✓.

Problema 8. Un grafo tiene 6 vertices y todos de grado 4. ¿Cuantas aristas tiene? ¿Tiene circuito euleriano? ¿Y si un vertice tuviera grado 3?

Solución paso a paso

Lema de handshaking: suma de grados = 2·|A|. Suma = 6·4 = 24 → aristas = 12.
Circuito euleriano (recorre cada arista una vez y vuelve al inicio): conexo y TODOS los grados pares. Con 4-regular: si, existe.
Si un vertice baja a grado 3, la suma pasa a 23: imposible (debe ser par). Los grados siempre "casan" de dos en dos: no existe un grafo con exactamente un vertice de grado impar.

Problema 9 (aritmética modular). Halla el ultimo digito de 3^20 (es decir 3^20 mod 10... y de paso 3^20 mod 7).

Solución paso a paso

Mod 10: potencias de 3: 3, 9, 27→7, 81→1, 3, ... ciclo de longitud 4: (3, 9, 7, 1).
20 es multiplo de 4, o sea cae en la posicion 4 del ciclo: ultimo digito = 1.
Mod 7: por Fermat, 3^6 ≡ 1 (mod 7). Entonces 3^20 = (3^6)^3 · 3^2 ≡ 1·9 ≡ 2 (mod 7).
Aplicacion: estos ciclos son la base de hashing y de RSA: trabajar con residuos mantiene los numeros pequenos a costo cero.

Mapa de estrategias

Como atacar cada problema

Autoexamen cronometrado (15 minutos)

¿Cuantas comisiones de 2 se forman entre 6 personas? (C(6,2))

¿Cuantas aristas tiene K5 (grafo completo de 5 vertices)?

¿Cual es la negacion de "todos los dias llueve"?

Si un grafo conexo tiene exactamente dos vertices de grado impar, admite un recorrido euleriano (abierto, de uno a otro).

Halla el ultimo digito de 7^4. (7^4 mod 10)

En 11!/(4!·4!·2!) se cuentan las palabras de (palabra de 11 letras).

Video de repaso

Para profundizar

Khan Academy: criptografia y modular
Donde la aritmetica modular del problema 9 se vuelve RSA de verdad.

MIT OCW: Mathematics for CS (abierto)
Apuntes completos y gratuitos: el curso de discreta del MIT con material de sobra.

El conteo y la probabilidad son dos caras de la misma moneda: C(9,3) fue a la vez un conteo y un espacio muestral. Cuando veas una formula de probabilidad en adelante, preguntate cuantos casos cuenta cada factorial.