Resumen Métodos y Técnicas de Examen (PDF)

# Resumen Completo de Métodos y Técnicas para Ejercicios de Examen - Este resumen incluye todos los métodos explicados en este chat que podrás usar en ejercicios de examen, divididos en áreas clave. - La información es condensada para su rápida consulta, pero manteniendo rigor y detalle. ## 1. Com...

# Resumen Completo de Métodos y Técnicas para Ejercicios de Examen - Este resumen incluye todos los métodos explicados en este chat que podrás usar en ejercicios de examen, divididos en áreas clave. - La información es condensada para su rápida consulta, pero manteniendo rigor y detalle. ## 1. Combinatoria ### Principios Fundamentales 1. **Principio de Adición**: Si una tarea puede realizarse de $n_1$ formas y otra de $n_2$ formas, y ambas son excluyentes, el total es: $n_1 + n_2$. 2. **Principio de Multiplicación**: Si una tarea se descompone en etapas sucesivas que pueden realizarse de $n_1$, $n_2$,..., $n_k$ formas, el total es: $n_1n_2...n_k$. 3. **Principio de Distribución**: Dados $m$ elementos y $n$ cajas, si: * Suma de elementos en las cajas > $p$, entonces al menos una caja tendrá más de p elementos. ### Permutaciones, Variaciones y Combinaciones 1. **Permutaciones**: * $P(n) = n!$. * Permutaciones de $n$ elementos sin repetición. 2. **Variaciones**: * $V(n,r) = \frac{n!}{(n-r)!}$. * Ordena $r$ elementos de un conjunto de $n$. 3. **Combinaciones**: * $C(n,r)= \frac{n!}{r!(n-r)!}$. * Selecciona $r$ elementos de un conjunto de $n$, sin importar el orden. 4. **Combinaciones con repetición**: * $C'(n,r) = C(n+r-1,r)$. ### Teorema del Binomio $(a + b)^n = \sum_{k=0}^n C(n,k) \cdot a^{n-k} \cdot b^k$. ### Principio de Inclusión-Exclusión Para contar elementos en la unión de conjuntos: $|S_1 \cup S_2 \cup ... \cup S_n| = \sum_{i=1}^n|S_i| - \sum_{1 \le i < j \le n}|S_i \cap S_j| + ... + (-1)^{n-1} |S_1 \cap S_2 \cap ... \cap S_n|$. ## 2. Teoría de Grafos ### Conceptos Fundamentales - Grado de un vértice: Número de aristas incidentes en el vértice. - Ciclo: Secuencia cerrada de aristas que no se repite. - Conexo: Si existe un camino entre cualquier par de vértices. ### Grafos Eulerianos y Hamiltonianos 1. **Grafo Euleriano**: * Contiene un ciclo que visita cada arista exactamente una vez. * Condición: Todos los vértices tienen grado par. 2. **Grafo Hamiltoniano**: * Contiene un ciclo que visita cada vértice exactamente una vez. * No existe un criterio general, pero se estudian condiciones específicas como la de Ore. ### Representación de Grafos por Matrices 1. **Matriz de Adyacencia**: * $A[i][j] = \left\{\begin{array}{ll} 1 & \text{ si hay arista entre }$v_i$ y $v_j$, \\ 0 & \text{ en caso contrario. }\end{array}\right.$ 2. **Matriz de Pesos**: Si el grafo es ponderado, $W[i][j]$ almacena el peso de la arista entre $v_i$ y $v_j$, o $\infty$ si no existe. ### Algoritmo de Dijkstra Encuentra el camino más corto entre un vértice origen y los demás: 1. Inicializa distancias a infinito ($\infty$) excepto el origen (0). 2. Selecciona el vértice de menor distancia aún no procesado. 3. Actualiza las distancias a los vecinos: $d(v) = min(d(v), d(u) + w(u, v))$. 4. Repite hasta procesar todos los vértices. ### Coloración de Grafos - Número Cromático ($\chi(G)$): Mínimo número de colores necesarios para colorear los vértices de un grafo. - Teorema de los Cuatro Colores: Todo grafo plano es coloreable con a lo sumo 4 colores. ## 3. Teoría de Números ### Algoritmo de Euclides Para calcular el $gcd(a, b)$: 1. Divide $a$ entre $b$ para obtener el residuo $r_1$. 2. Repite con $b$ y $r_1$. 3. Termina cuando el residuo es 0. El último residuo no nulo es $gcd(a, b)$. ### Teorema Fundamental de la Aritmética Todo número entero positivo puede descomponerse de forma única como un producto de números primos: $n = p_1^{e_1} p_2^{e_2} ... p_k^{e_k}$. ### Congruencias 1. Definición: $a = b \pmod{m}$ sim $| (a - b)$. 2. Operaciones: * Suma: $a + c = b + d \pmod{m}$. * Multiplicación: $ac=bd \pmod{m}$. 3. Teorema Chino del Resto: Para resolver sistemas de congruencias: * $x \equiv a_1 \pmod{m_1}$, $x \equiv a_2 \pmod{m_2}$, .... Si $m_1$, $m_2$,... son coprimos, hay una solución única $\pmod{M}$, donde $M = m_1 m_2 ... m_k$. ### Criterios de Divisibilidad 1. Representación: * $n = \sum_{i=0}^{t} a_i \cdot 10^i$. * Usar $10^i \pmod{k}$ para simplificar. 2. Ejemplos: * Por 3: $n$ es divisible por 3 si $\sum a_i = 0 \pmod{3}$. * Por 11: Alternar suma y resta de dígitos: ($a_0 - a_1 + a_2 - ...$) $\pmod{11}$. ## 4. Resolución de Ecuaciones Diofánticas ### Ecuaciones Lineales Resolver $ax + by = c$: 1. Calcular $gcd(a, b)$. 2. Si $gcd(a, b) | c$, parametrizar las soluciones: * $x = x_0 + k \frac{b}{gcd(a, b)}$, $y = y_0 - k \frac{a}{gcd(a, b)}$.