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
¿Es (q → r) ∧ (q ∧ ¬r) una tautología, una contradicción o una contingencia? Haz clic en tu respuesta.
(q → r) ∧ (q ∧ ¬r)
1tautología
2contradicción
3contingencia
2.Lógica proposicional y demostracionesDifícil
¿Cuántas de las 16 filas de la tabla de verdad hacen verdadera ((s ∧ r) ∨ (¬q → p)) ∨ ¬(s ∨ (r ∨ p))? Llama a ese número N.
((s ∧ r) ∨ (¬q → p)) ∨ ¬(s ∨ (r ∨ p))
N =
3.Conjuntos, relaciones y funcionesMedia
La relación R en {1, 2, 3, 4} se dibuja como un grafo dirigido (un lazo significa (x, x) ∈ R). Se cumple exactamente una de las cuatro propiedades. Haz clic en ella.
¿Cuántos circuitos de Hamilton distintos, H, tiene el grafo completo K8? Los circuitos que solo difieren en el vértice inicial o en el sentido cuentan como el mismo.
K8
H =
6.Teoría de grafosDifícil
¿Cuántos recorridos de longitud 2 van de C a E? Un recorrido puede repetir vértices y aristas. Llama al número N.
M = matriz de adyacenciaL = 2
N =
7.Teoría de números y aritmética modularMedia
Resuelve 12x ≡ 14 (mod 19). Da la solución x con 0 < x < 19.
12x ≡ 14 (mod 19)
x =
8.Teoría de números y aritmética modularDifícil
Usa el cuadrado repetido para hallar 59187 mod 73.
a = 59k = 187n = 73
59187 mod 73 =
3Disoluciones
1.Lógica proposicional y demostraciones
Respuesta: contradicción
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).
Tablas de verdad: una fórmula con n variables distintas tiene 2ⁿ filas, una por cada combinación de valores de verdad (1 = verdadero, 0 = falso). Trabaja de dentro hacia fuera y dale a cada subfórmula su propia columna. ¬a invierte el valor; a ∧ b vale 1 solo cuando ambos son 1; a ∨ b vale 0 solo cuando ambos son 0; a → b vale 0 solo cuando a = 1 y b = 0; a ↔ b vale 1 cuando ambos lados son iguales.
Columnas
s ∧ r; ¬q; ¬q → p; (s ∧ r) ∨ (¬q → p); r ∨ p; s ∨ (r ∨ p); ¬(s ∨ (r ∨ p)); ((s ∧ r) ∨ (¬q → p)) ∨ ¬(s ∨ (r ∨ p))
Divide según p
p = 1: 8
p = 0: 6
N = 8 + 6 = 14
Respuesta
N = 14
3.Conjuntos, relaciones y funciones
Respuesta: reflexiva
Relaciones: una relación R en un conjunto X es un conjunto de pares ordenados (x, y). R es reflexiva cuando (x, x) ∈ R para todo x de X; simétrica cuando (x, y) ∈ R siempre va acompañado de (y, x) ∈ R; antisimétrica cuando (x, y) y (y, x) están ambos en R solo si x = y; y transitiva cuando (x, y) y (y, z) en R obligan a que (x, z) ∈ R. Una relación de equivalencia es reflexiva, simétrica y transitiva, y divide X en clases disjuntas.
reflexiva
se cumple
simétrica
falla: (3, 1) ∈ R, (1, 3) ∉ R
antisimétrica
falla: (2, 4), (4, 2) ∈ R
transitiva
falla: (2, 4), (4, 1) ∈ R, (2, 1) ∉ R
Respuesta
reflexiva
4.Conjuntos, relaciones y funciones
Respuesta: (g ∘ f)(2) = 2
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.
Función interior
f(2) = 3
Función exterior
g(3) = 2
(g ∘ f)(2) = 2
Respuesta
(g ∘ f)(2) = 2
5.Teoría de grafos
Respuesta: H = 2520
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 = (8 − 1)!/2 = 5040/2 = 2520
Respuesta
H = 2520
6.Teoría de grafos
Respuesta: N = 1
Grados: el grado de un vértice es el número de aristas que inciden en él. Cada arista tiene dos extremos, así que los grados suman el doble del número de aristas: Σ gr(v) = 2|E| (el lema del apretón de manos). Por tanto, el número de vértices de grado impar es par. Kn tiene n(n − 1)/2 aristas, un grafo k-regular de n vértices tiene nk/2, y un árbol de n vértices tiene n − 1 aristas.
Matriz de adyacencia
A: 0 1 0 0 0
B: 1 0 1 1 1
C: 0 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0
Vecinos comunes
(M²)CE = 0·0 + 1·1 + 0·1 + 0·1 + 1·0 = 1
Respuesta
N = 1
7.Teoría de números y aritmética modular
Respuesta: x = 17
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).
Inverso de 12
r = 19, t = 0
r = 12, q = 1, t = 1
r = 7, q = 1, t = −1
r = 5, q = 1, t = 2
r = 2, q = 2, t = −3
r = 1, q = 2, t = 8
12−1 ≡ 8 (mod 19)
Resuelve
x ≡ 8·14 = 112 ≡ 17 (mod 19)
comprobación: 12·17 = 204 ≡ 14 (mod 19)
Respuesta
x = 17
8.Teoría de números y aritmética modular
Respuesta: 59187 mod 73 = 44
Potencias modulares y RSA: calcula aᵏ mod n por cuadrado repetido: escribe k en binario, eleva al cuadrado, reduce después de cada paso y multiplica las potencias cuyo bit es 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) para un primo p que no divide a a, así que el exponente se puede reducir módulo p − 1. RSA: elige los primos p y q, n = p·q y φ(n) = (p − 1)(q − 1); el exponente público e es coprimo con φ(n), y el exponente privado es d = e⁻¹ mod φ(n). Cifra con c = mᵉ mod n y descifra con m = cᵈ mod n.