Dibuja un diagrama de Venn y decide región por región qué pertenece a la expresión de conjuntos.
En los problemas de recuento, rellena las regiones desde el centro hacia fuera: primero todos los conjuntos, luego los pares, después los conjuntos sueltos y por último el exterior.
Usa la inclusión–exclusión como comprobación: |A ∪ B| = |A| + |B| − |A ∩ B|.
En una relación, comprueba cada propiedad en todos los pares y da un contraejemplo cuando falle.
En una función, cuenta las flechas que llegan a cada elemento de B: como mucho una significa inyectiva, al menos una, sobreyectiva.
Teoría de grafos
Lema del apretón de manos
Σ deg(v) = 2|E|
Grafos completos
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Grafo regular
|E| = n·k/2
Árbol y bosque
|E| = n − 1, |E| = n − c
Hojas de un árbol
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
circuito: todos los grados pares; camino: exactamente 2 grados impares
Circuitos de Hamilton en Kn
(n − 1)!/2
Actualización de Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Recorridos de longitud L
(Mᴸ)ij
Método
Anota el grado de cada vértice; los grados suman el doble del número de aristas.
En las preguntas de Euler, comprueba que el grafo sea conexo y cuenta los vértices de grado impar.
En los árboles, usa n − 1 aristas y el lema del apretón de manos.
En Dijkstra, lleva una tabla de distancias provisionales y fija en cada ronda el vértice no fijado de menor distancia.
Para un árbol generador mínimo, ordena las aristas por peso y descarta toda arista que cierre un ciclo (Kruskal), o haz crecer un único árbol desde un vértice inicial (Prim).
Teoría de números y aritmética modular
División con resto
a = q·n + r, 0 ≤ r < n
Euclides
gcd(a, b) = gcd(b, a mod b)
Mínimo común múltiplo
lcm(a, b) = a·b/gcd(a, b)
Inversa
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Congruencia lineal
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Función φ de Euler
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Método
Reduce primero cada número módulo n; los restos están entre 0 y n − 1.
Para un mcd, divide repetidamente con el algoritmo de Euclides; el último resto distinto de cero es el mcd.
Para un inverso, aplica el algoritmo extendido y quédate con el coeficiente de a; suma n si es negativo.
Resuelve a·x ≡ b multiplicando por a⁻¹; combina dos congruencias escribiendo x = r₁ + m₁k.
Para las potencias, escribe el exponente en binario y eleva al cuadrado repetidamente; en RSA, d = e⁻¹ mod φ(n) con φ(n) = (p − 1)(q − 1).
2Problemas de práctica
1.Lógica proposicional y demostracionesMedia
Quieres demostrar (q ∨ p) → ¬r por reducción al absurdo. ¿Qué enunciado supones al principio? Haz clic en él.
(q ∨ p) → ¬r
1¬(q ∨ p) ∧ ¬r
2¬(q ∨ p) ∧ ¬¬r
3(q ∨ p) ∧ ¬¬r
4¬(q ∨ p) → ¬¬r
2.Lógica proposicional y demostracionesDifícil
El argumento con premisas p → r; ¬p y conclusión ¬r no es válido. Haz clic en la fila de la tabla de verdad que es un contraejemplo.
p → r¬p∴ ¬r
1p = 1, r = 1
2p = 1, r = 0
3p = 0, r = 1
4p = 0, r = 0
3.Conjuntos, relaciones y funcionesMedia
Una encuesta a 60 personas revela que 30 tienen un portátil (L), 35 una tableta (T) y 30 un reloj inteligente (W). 11 tienen L y T, 18 tienen L y W, 16 tienen T y W, y 6 tienen los tres. ¿Cuántos están en exactamente dos de los tres conjuntos? Llama al número n.
|U| = 60
n =
4.Conjuntos, relaciones y funcionesDifícil
El diagrama de flechas muestra una función f: A → B con A = {1, 2, 3, 4} y B = {a, b, c, d}. Haz clic en la descripción que corresponde a f.
f = {(1, d), (2, b), (3, d), (4, c)}
1inyectiva, no sobreyectiva
2sobreyectiva, no inyectiva
3biyectiva
4ninguna de las dos
5.Teoría de grafosMedia
¿Cuántos circuitos de Hamilton distintos, H, tiene el grafo completo K5? Los circuitos que solo difieren en el vértice inicial o en el sentido cuentan como el mismo.
K5
H =
6.Teoría de grafosDifícil
El algoritmo de Kruskal construye un árbol generador mínimo. Haz clic en la arista que añade como arista número 4; las aristas descartadas no cuentan.
k = 4
1arista AB
2arista AC
3arista BC
4arista BD
5arista CE
6arista DE
7arista BE
7.Teoría de números y aritmética modularMedia
Halla el menor entero positivo x con x ≡ 6 (mod 8) y x ≡ 10 (mod 13).
x ≡ 6 (mod 8)x ≡ 10 (mod 13)
x =
8.Teoría de números y aritmética modularDifícil
¿Cuántas soluciones, N, tiene 26x ≡ 12 (mod 34) en {0, 1, …, 33}?
26x ≡ 12 (mod 34)
N =
3Disoluciones
1.Lógica proposicional y demostraciones
Respuesta: (q ∨ p) ∧ ¬¬r
Equivalencia lógica: dos fórmulas son equivalentes (≡) cuando tienen el mismo valor en todas las filas de la tabla de verdad. Una tautología vale 1 en todas las filas, una contradicción vale 0 en todas las filas, y una contingencia no es ninguna de las dos. Leyes útiles: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b y ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrarrecíproca); ¬(a → b) ≡ a ∧ ¬b; y las leyes distributivas, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Partes de la implicación
a = q ∨ p, b = ¬r
Negación de la implicación
¬(a → b) ≡ a ∧ ¬b = (q ∨ p) ∧ ¬¬r
Respuesta
(q ∨ p) ∧ ¬¬r
Si la suposición lleva a una contradicción, la implicación tiene que ser verdadera.
2.Lógica proposicional y demostraciones
Respuesta: p = 0, r = 1
Cuantificadores y argumentos: ¬∀x P(x) ≡ ∃x ¬P(x) y ¬∃x P(x) ≡ ∀x ¬P(x). Desplaza la negación hacia dentro, intercambia cada cuantificador que atraviesa y niega la fórmula interior con las leyes proposicionales, como ¬(a → b) ≡ a ∧ ¬b. Un argumento es válido cuando la conclusión vale 1 en todas las filas en las que todas las premisas valen 1. Una sola fila con premisas verdaderas y conclusión falsa es un contraejemplo y demuestra que el argumento no es válido.
Premisas y conclusión fila por fila
p = 1, r = 1: 1 0 | 0
p = 1, r = 0: 0 0 | 1
p = 0, r = 1: 1 1 | 0
p = 0, r = 0: 1 1 | 1
Contraejemplo
p = 0, r = 1
Respuesta
p = 0, r = 1
Un argumento con esta forma parece una regla válida, pero una sola fila basta para demostrar que no lo es.
3.Conjuntos, relaciones y funciones
Respuesta: n = 27
Conjuntos y diagramas de Venn: A ∪ B contiene los elementos que están en A o en B (o en ambos), A ∩ B los elementos que están en ambos, A − B los elementos de A que no están en B, y el complemento A′ todo lo de U que no está en A. En un diagrama de Venn toda expresión de conjuntos es una unión de regiones, así que cuéntala región por región. Inclusión–exclusión: |A ∪ B| = |A| + |B| − |A ∩ B|, y |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Centro y pares
L ∩ T ∩ W: 6
L ∩ T solo: 11 − 6 = 5
L ∩ W solo: 18 − 6 = 12
T ∩ W solo: 16 − 6 = 10
Conjuntos sueltos
L solo: 30 − 5 − 12 − 6 = 7
T solo: 35 − 5 − 10 − 6 = 14
W solo: 30 − 12 − 10 − 6 = 2
Respuesta
5 + 12 + 10 = 27
Respuesta
n = 27
4.Conjuntos, relaciones y funciones
Respuesta: ninguna de las dos
Funciones y recuento: una función f: A → B da a cada elemento de A exactamente una imagen en B. f es inyectiva (uno a uno) cuando elementos distintos tienen imágenes distintas, sobreyectiva cuando todo elemento de B es una imagen, y biyectiva cuando se cumplen ambas. Con |A| = m y |B| = n hay nᵐ funciones, n!/(n − m)! inyectivas (m ≤ n) y, por inclusión–exclusión, Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ sobreyectivas. |𝒫(A)| = 2ᵐ y |A × B| = m·n.
¿Inyectiva?
f(1) = f(3) = d → no inyectiva
¿Sobreyectiva?
a no recibe ninguna flecha → no sobreyectiva
Respuesta
ninguna de las dos
Respuesta
ninguna de las dos
5.Teoría de grafos
Respuesta: H = 12
Euler, Hamilton y árboles: un grafo conexo tiene un circuito euleriano (cada arista una vez, volviendo al inicio) cuando todos los vértices tienen grado par, y un camino euleriano que no es un circuito cuando exactamente dos vértices tienen grado impar; entonces el camino va de un vértice impar al otro. Un circuito hamiltoniano visita cada vértice una vez; Kn tiene (n − 1)!/2 de ellos. Un árbol de n vértices tiene n − 1 aristas, y un grafo conexo con m aristas conserva un árbol generador tras quitarle m − n + 1 aristas.
Contar
H = (5 − 1)!/2 = 24/2 = 12
Respuesta
H = 12
6.Teoría de grafos
Respuesta: arista AC
Caminos mínimos y árboles generadores: el algoritmo de Dijkstra fija un vértice por ronda: el vértice no fijado con la menor distancia provisional. Su distancia es entonces definitiva, y cada vecino v recibe d(v) = min(d(v), d(u) + w(u, v)). El algoritmo de Kruskal construye un árbol generador mínimo tomando las aristas de la más ligera a la más pesada y descartando toda arista que cierre un ciclo; el algoritmo de Prim hace crecer un único árbol desde un vértice inicial añadiendo siempre la arista más ligera que sale de él. Un árbol generador de n vértices tiene n − 1 aristas.
Algoritmo de Kruskal
1. BD (4)
2. BE (10)
3. BC (11)
4. AC (16)
arista número 4
AC
Respuesta
arista AC
7.Teoría de números y aritmética modular
Respuesta: x = 62
Inversos y congruencias: a tiene inverso módulo n exactamente cuando mcd(a, n) = 1. El algoritmo de Euclides extendido escribe 1 = s·n + t·a, y entonces a⁻¹ ≡ t (mod n). Una congruencia a·x ≡ b (mod n) con mcd(a, n) = 1 tiene la solución x ≡ a⁻¹·b. Dos congruencias x ≡ r₁ (mod m₁) y x ≡ r₂ (mod m₂) con módulos coprimos tienen una solución módulo m₁·m₂ (teorema chino del resto). La φ(n) de Euler cuenta los números de 1 a n que son coprimos con n: φ(n) = n·∏(1 − 1/p).
Primera congruencia
x = 6 + 8k
Segunda congruencia
6 + 8k ≡ 10 (mod 13) → 8k ≡ 4 (mod 13)
k ≡ 5·4 ≡ 7 (mod 13)
Resultado
x = 6 + 8·7 = 62
x = 62
comprobación: 62 mod 8 = 6, 62 mod 13 = 10
Respuesta
x = 62
8.Teoría de números y aritmética modular
Respuesta: N = 2
Inversos y congruencias: a tiene inverso módulo n exactamente cuando mcd(a, n) = 1. El algoritmo de Euclides extendido escribe 1 = s·n + t·a, y entonces a⁻¹ ≡ t (mod n). Una congruencia a·x ≡ b (mod n) con mcd(a, n) = 1 tiene la solución x ≡ a⁻¹·b. Dos congruencias x ≡ r₁ (mod m₁) y x ≡ r₂ (mod m₂) con módulos coprimos tienen una solución módulo m₁·m₂ (teorema chino del resto). La φ(n) de Euler cuenta los números de 1 a n que son coprimos con n: φ(n) = n·∏(1 − 1/p).