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).
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
Paso 1 · Simbolizar
Atomicemos: p = "estudio", q = "repaso", r = "apruebo". La frase es (p ∧ q) → r.Paso 2 · Dimensionar
Con 3 variables hay 2^3 = 8 filas. La conjuncion p ∧ q solo es V cuando ambas son V.Paso 3 · Regla de oro
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.Paso 4 · Concluir
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.
Paso 1 de 4
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
Paso 1 · Formalizar
Simbolos: ∀x ∃y A(x,y).Paso 2 · Girar cuantificadores
Regla de negacion en cascada: ¬∀ = ∃; ¬∃ = ∀; y la predicacion final se niega: ¬∀x ∃y A ≡ ∃x ∀y ¬A.Paso 3 · Traducir
En español: "Existe al menos un estudiante que no aprueba NINGUN curso" (es decir, todos los cursos se le niegan).Paso 4 · Precision
Ojo con la trampa: "no todos aprueban todo" NO significa "nadie aprueba nada". La negacion solo toca el primer cuantificador que encuentra.
Paso 1 de 4
Problema 3. Demuestra por induccion que 1 + 2 + ... + n = n(n + 1)/2 para todo n ≥ 1.
Solución paso a paso
Paso 1 · Base
Caso base (n = 1): izquierda = 1; derecha = 1·2/2 = 1. Cierto.Paso 2 · Hipotesis
Hipotesis inductiva: supongamos la formula cierte para n = k, o sea 1 + ... + k = k(k+1)/2.Paso 3 · Sumar el siguiente
Paso inductivo: 1 + ... + k + (k+1) = k(k+1)/2 + (k+1) por la hipotesis.Paso 4 · Cerrar
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.
Paso 1 de 4
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
Paso 1 · Formula
Inclusion-exclusion: |F ∪ B| = |F| + |B| − |F ∩ B| = 18 + 15 − 7 = 26.Paso 2 · Restar
Complemento: 30 − 26 = 4 estudiantes no juegan nada.Paso 3 · Verificar
Lee el diagrama de Venn: solo futbol = 11, solo basket = 8, ambos = 7; suma 26. La interseccion se resta porque se conto dos veces.
Paso 1 de 3
Problema 5. ¿Cuantas palabras distintas (con o sin sentido) se forman reordenando las letras de MISSISSIPPI?
Solución paso a paso
Paso 1 · Inventario
Cuenta las letras: 11 total: M(1), I(4), S(4), P(2).Paso 2 · Formula
Permutaciones con repeticion: 11!/(1!·4!·4!·2!).Paso 3 · Aritmetica
Calcula: 39,916,800 / (24·24·2) = 39,916,800 / 1152 = 34,650 palabras.Paso 4 · Intuicion
La idea: si las 4 I fueran distinguibles, cada palabra apareceriria 4 veces; dividir por 4! colapsa los duplicados.
Paso 1 de 4
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
Paso 1 · Total
Espacio muestral: C(9,3) = 84 comites posibles (no importa el orden).Paso 2 · Casos favorables
Comites todo-mujeres: C(5,3) = 10. Probabilidad: 10/84 ≈ 0.119.Paso 3 · Complemento
"Al menos un hombre" es el complemento de "ningun hombre": 1 − 10/84 = 74/84 ≈ 0.881.Paso 4 · Estrategia
Patron: ante "al menos", cuenta el cero. Contar directamente los comites con 1, 2 o 3 hombres exige tres calculos; el complemento, uno.
Paso 1 de 4
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
Paso 1 · Iterar
Desenrolla: a(n) = a(0) + suma de 2k para k de 1 a n = 1 + 2·(1 + 2 + ... + n).Paso 2 · Suma
Usa Gauss: 1 + ... + n = n(n+1)/2. Entonces a(n) = 1 + 2·n(n+1)/2 = 1 + n(n+1).Paso 3 · Chequeo
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 ✓.
Paso 1 de 3
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
Paso 1 · Contar aristas
Lema de handshaking: suma de grados = 2·|A|. Suma = 6·4 = 24 → aristas = 12.Paso 2 · Euler
Circuito euleriano (recorre cada arista una vez y vuelve al inicio): conexo y TODOS los grados pares. Con 4-regular: si, existe.Paso 3 · Paridad
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.
Paso 1 de 3
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
Paso 1 · Ciclos
Mod 10: potencias de 3: 3, 9, 27→7, 81→1, 3, ... ciclo de longitud 4: (3, 9, 7, 1).Paso 2 · Posicionar
20 es multiplo de 4, o sea cae en la posicion 4 del ciclo: ultimo digito = 1.Paso 3 · Pequeño de Fermat
Mod 7: por Fermat, 3^6 ≡ 1 (mod 7). Entonces 3^20 = (3^6)^3 · 3^2 ≡ 1·9 ≡ 2 (mod 7).Paso 4 · Conectar
Aplicacion: estos ciclos son la base de hashing y de RSA: trabajar con residuos mantiene los numeros pequenos a costo cero.
Paso 1 de 4
Mapa de estrategias
Como atacar cada problema
- Discretas
- Logica
- Tablas: 2^n filas
- Implicacion falsa solo V→F
- Negar: girar cuantificadores
- Conteo
- Orden? permutaciones
- Sin orden? combinaciones
- Repetidos? dividir por factoriales
- "Al menos": complemento
- Grafos
- Handshaking: grados = 2 aristas
- Euler: grados pares
- Hamilton: sin criterio simple
- Modular
- Buscar el ciclo
- Fermat: a^(p−1) ≡ 1
- Logica
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).
Para profundizar
Khan Academy: criptografia y modularDonde 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.
Tu texto se guarda sólo en este dispositivo.
Comentarios
Inicia sesión para comentar.
Todavía no hay comentarios. Sé la primera persona en opinar.