Olimpiadas de Matemáticas Chile

Cheatsheet Content

Teoría de Números Divisibilidad y Algoritmo de Euclides Un entero $a$ es divisible por $b$ (o $b$ divide a $a$), si existe un entero $k$ tal que $a = bk$. Se denota $b|a$. Propiedades: Si $a|b$ y $b|c$, entonces $a|c$. Si $a|b$ y $a|c$, entonces $a|(bx+cy)$ para cualesquiera enteros $x,y$. Si $a|b$ y $b|a$, entonces $a = \pm b$. Algoritmo de Euclides: Para encontrar el Máximo Común Divisor (MCD) de dos enteros $a, b$. $a = q_1 b + r_1$, $0 \leq r_1 $b = q_2 r_1 + r_2$, $0 \leq r_2 ... $r_{k-1} = q_{k+1} r_k + 0$ El MCD es el último resto no nulo, $r_k$. Identidad de Bezout: Para enteros $a, b$ no ambos cero, existen enteros $x, y$ tales que $ax + by = \text{mcd}(a, b)$. Números Primos y Factorización Única Un entero $p > 1$ es primo si sus únicos divisores positivos son $1$ y $p$. Teorema Fundamental de la Aritmética: Todo entero $n > 1$ puede escribirse de forma única (salvo el orden de los factores) como un producto de números primos: $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Número de divisores: Si $n = p_1^{a_1} \cdots p_k^{a_k}$, el número de divisores de $n$, $\tau(n)$, es $(a_1+1)(a_2+1)\cdots(a_k+1)$. Suma de divisores: $\sigma(n) = \left(\frac{p_1^{a_1+1}-1}{p_1-1}\right) \cdots \left(\frac{p_k^{a_k+1}-1}{p_k-1}\right)$. Congruencias $a \equiv b \pmod{m}$ significa que $m | (a-b)$. Propiedades: Si $a \equiv b \pmod{m}$ y $c \equiv d \pmod{m}$, entonces $a+c \equiv b+d \pmod{m}$ y $ac \equiv bd \pmod{m}$. Si $ac \equiv bc \pmod{m}$ y $\text{mcd}(c, m) = 1$, entonces $a \equiv b \pmod{m}$. Pequeño Teorema de Fermat: Si $p$ es un número primo, entonces para cualquier entero $a$ no divisible por $p$, se cumple $a^{p-1} \equiv 1 \pmod{p}$. También, $a^p \equiv a \pmod{p}$ para todo entero $a$. Teorema de Euler: Si $\text{mcd}(a, n) = 1$, entonces $a^{\phi(n)} \equiv 1 \pmod{n}$, donde $\phi(n)$ es la función totiente de Euler (cuenta los enteros positivos menores o iguales a $n$ que son coprimos con $n$). Si $n = p_1^{a_1} \cdots p_k^{a_k}$, entonces $\phi(n) = n \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_k}\right)$. Teorema Chino del Resto: Si $m_1, m_2, \ldots, m_k$ son coprimos dos a dos, entonces el sistema de congruencias: $x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$ ... $x \equiv a_k \pmod{m_k}$ tiene una solución única módulo $M = m_1 m_2 \cdots m_k$. Problemas de Teoría de Números Encuentra el último dígito de $7^{2023}$. Demuestra que si $n$ es un entero positivo, entonces $n^3 - n$ es divisible por $6$. Encuentra todos los enteros positivos $x, y$ tales que $x^2 - y^2 = 31$. Determina si $2^{2023} + 1$ es divisible por $3$. Encuentra el menor entero positivo $n$ tal que $n \equiv 2 \pmod{3}$, $n \equiv 3 \pmod{5}$ y $n \equiv 4 \pmod{7}$. Álgebra Polinomios Raíces y factores: Si $P(x)$ es un polinomio y $r$ es una raíz (es decir, $P(r)=0$), entonces $(x-r)$ es un factor de $P(x)$. Teorema de las Raíces Racionales: Si $P(x) = a_n x^n + \dots + a_1 x + a_0$ tiene coeficientes enteros, y $p/q$ es una raíz racional (en forma reducida), entonces $p$ divide a $a_0$ y $q$ divide a $a_n$. Fórmulas de Vieta: Para un polinomio $P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$ con raíces $r_1, r_2, \dots, r_n$: Suma de raíces: $\sum r_i = -\frac{a_{n-1}}{a_n}$ Suma de productos de raíces tomadas de dos en dos: $\sum_{i Producto de raíces: $r_1 r_2 \cdots r_n = (-1)^n \frac{a_0}{a_n}$ Desigualdades AM-GM (Media Aritmética - Media Geométrica): Para números reales no negativos $x_1, x_2, \dots, x_n$: $\frac{x_1 + x_2 + \dots + x_n}{n} \geq \sqrt[n]{x_1 x_2 \dots x_n}$ La igualdad se cumple si y solo si $x_1 = x_2 = \dots = x_n$. Cauchy-Schwarz: Para números reales $a_1, \dots, a_n$ y $b_1, \dots, b_n$: $(a_1 b_1 + a_2 b_2 + \dots + a_n b_n)^2 \leq (a_1^2 + a_2^2 + \dots + a_n^2)(b_1^2 + b_2^2 + \dots + b_n^2)$ La igualdad se cumple si y solo si existe una constante $k$ tal que $a_i = k b_i$ para todo $i$, o si todos los $a_i$ o todos los $b_i$ son cero. Rearreglo: Para dos secuencias de números reales $a_1 \leq a_2 \leq \dots \leq a_n$ y $b_1 \leq b_2 \leq \dots \leq b_n$: $a_1 b_n + a_2 b_{n-1} + \dots + a_n b_1 \leq a_1 b_{\sigma(1)} + \dots + a_n b_{\sigma(n)} \leq a_1 b_1 + a_2 b_2 + \dots + a_n b_n$ para cualquier permutación $\sigma$ de $\{1, \dots, n\}$. Funciones y Ecuaciones Funcionales Inyectividad: Una función $f$ es inyectiva si $f(x_1) = f(x_2) \implies x_1 = x_2$. Sobreyectividad: Una función $f$ es sobreyectiva si para todo $y$ en el codominio, existe un $x$ en el dominio tal que $f(x) = y$. Biyectividad: Una función es biyectiva si es inyectiva y sobreyectiva. Problemas de Álgebra Si $a, b, c$ son las raíces del polinomio $x^3 - 6x^2 + 11x - 6 = 0$, calcula el valor de $a^2+b^2+c^2$. Encuentra todas las soluciones reales de la ecuación $\sqrt{x+1} + \sqrt{x-1} = \sqrt{2x+1}$. Demuestra que para números reales positivos $a, b, c$: $(a+b)(b+c)(c+a) \geq 8abc$. Encuentra los valores de $x$ para los cuales $\frac{x^2-3x+2}{x^2-4} \geq 0$. Determina todas las funciones $f: \mathbb{R} \to \mathbb{R}$ tales que $f(x^2 - y^2) = (x-y)(f(x)+f(y))$ para todo $x, y \in \mathbb{R}$. Combinatoria Principios Básicos de Conteo Principio de la Suma: Si una tarea puede realizarse de $m$ maneras y otra tarea independiente puede realizarse de $n$ maneras, entonces hay $m+n$ maneras de realizar una de las dos tareas. Principio del Producto: Si una tarea se puede descomponer en $k$ etapas, y la primera etapa tiene $n_1$ resultados, la segunda $n_2$, ..., la $k$-ésima $n_k$, entonces el número total de resultados es $n_1 \times n_2 \times \dots \times n_k$. Permutaciones: Arreglos ordenados de objetos. De $n$ objetos distintos: $n!$ De $n$ objetos con repeticiones ($n_1$ idénticos de tipo 1, ..., $n_k$ idénticos de tipo k): $\frac{n!}{n_1! n_2! \cdots n_k!}$ De $k$ objetos tomados de $n$ distintos: $P(n, k) = \frac{n!}{(n-k)!}$ Combinaciones: Selecciones no ordenadas de objetos. De $k$ objetos tomados de $n$ distintos: $C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$ Identidades: $\binom{n}{k} = \binom{n}{n-k}$, $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$ (Identidad de Pascal). Principio de Inclusión-Exclusión Para dos conjuntos $A, B$: $|A \cup B| = |A| + |B| - |A \cap B|$. Para tres conjuntos $A, B, C$: $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$. Generalización: $|\bigcup_{i=1}^n A_i| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|$. Principio del Palomar (Pigeonhole Principle) Si se distribuyen $N$ objetos en $K$ cajas, entonces al menos una caja contiene $\lceil N/K \rceil$ objetos. Una versión simple: Si se tienen $N$ objetos y $K$ cajas y $N > K$, entonces al menos una caja contiene más de un objeto. Problemas de Combinatoria ¿De cuántas maneras se pueden sentar $5$ personas en una fila de $5$ asientos si dos de ellas insisten en sentarse juntas? Un comité de $5$ personas debe ser elegido de un grupo de $7$ hombres y $6$ mujeres. ¿Cuántos comités diferentes se pueden formar si debe haber al menos $3$ mujeres? En una fiesta, hay $10$ personas. Si cada persona saluda a todas las demás exactamente una vez, ¿cuántos saludos se realizan en total? En un cajón hay calcetines de $3$ colores diferentes (rojo, azul, verde). ¿Cuántos calcetines debes sacar, como mínimo y sin mirar, para asegurarte de tener un par del mismo color? ¿Cuántos números enteros entre $1$ y $1000$ son divisibles por $3$ o por $5$? Respuestas a los Problemas Teoría de Números Para el último dígito, trabajamos módulo $10$. $7^1 \equiv 7 \pmod{10}$ $7^2 \equiv 49 \equiv 9 \pmod{10}$ $7^3 \equiv 9 \times 7 = 63 \equiv 3 \pmod{10}$ $7^4 \equiv 3 \times 7 = 21 \equiv 1 \pmod{10}$ El ciclo de los últimos dígitos es $7, 9, 3, 1$ y tiene longitud $4$. $2023 \div 4 = 505$ con resto $3$. Entonces, $7^{2023} \equiv 7^3 \equiv 3 \pmod{10}$. El último dígito es $3$. Debemos demostrar que $n^3 - n$ es divisible por $2$ y por $3$. $n^3 - n = n(n^2 - 1) = n(n-1)(n+1)$. Este es el producto de tres enteros consecutivos. Divisibilidad por $2$: Entre dos enteros consecutivos, uno es par. Entre tres enteros consecutivos, al menos uno es par. Por lo tanto, el producto es divisible por $2$. Divisibilidad por $3$: Entre tres enteros consecutivos, uno debe ser divisible por $3$. Por lo tanto, el producto es divisible por $3$. Como es divisible por $2$ y por $3$, y $\text{mcd}(2,3)=1$, entonces es divisible por $2 \times 3 = 6$. La ecuación es $x^2 - y^2 = 31$, que se factoriza como $(x-y)(x+y) = 31$. Como $x, y$ son enteros positivos, $x+y$ debe ser un entero positivo. Además, $x+y > x-y$. Dado que $31$ es un número primo, sus únicos factores positivos son $1$ y $31$. Por lo tanto, tenemos el sistema de ecuaciones: $x-y = 1$ $x+y = 31$ Sumando ambas ecuaciones: $(x-y) + (x+y) = 1+31 \implies 2x = 32 \implies x = 16$. Sustituyendo $x=16$ en $x-y=1$: $16-y=1 \implies y=15$. La única solución en enteros positivos es $(x,y) = (16,15)$. Para determinar si $2^{2023} + 1$ es divisible por $3$, trabajamos módulo $3$. $2 \equiv -1 \pmod{3}$. Entonces, $2^{2023} + 1 \equiv (-1)^{2023} + 1 \pmod{3}$. Como $2023$ es impar, $(-1)^{2023} = -1$. Así, $2^{2023} + 1 \equiv -1 + 1 \equiv 0 \pmod{3}$. Por lo tanto, $2^{2023} + 1$ es divisible por $3$. Tenemos el sistema de congruencias: $n \equiv 2 \pmod{3}$ $n \equiv 3 \pmod{5}$ $n \equiv 4 \pmod{7}$ De $n \equiv 2 \pmod{3}$, tenemos $n = 3k+2$ para algún entero $k$. Sustituimos en la segunda congruencia: $3k+2 \equiv 3 \pmod{5}$ $3k \equiv 1 \pmod{5}$ Para encontrar el inverso de $3$ módulo $5$: $3 \times 2 = 6 \equiv 1 \pmod{5}$. Así, $3^{-1} \equiv 2 \pmod{5}$. Multiplicando por $2$: $2 \times 3k \equiv 2 \times 1 \pmod{5} \implies 6k \equiv 2 \pmod{5} \implies k \equiv 2 \pmod{5}$. Entonces $k = 5j+2$ para algún entero $j$. Sustituimos $k$ de nuevo en la expresión para $n$: $n = 3(5j+2) + 2 = 15j + 6 + 2 = 15j + 8$. Ahora sustituimos en la tercera congruencia: $15j + 8 \equiv 4 \pmod{7}$ $15j \equiv -4 \pmod{7}$ $15 \equiv 1 \pmod{7}$ y $-4 \equiv 3 \pmod{7}$. Entonces, $j \equiv 3 \pmod{7}$. Así, $j = 7m+3$ para algún entero $m$. Sustituimos $j$ de nuevo en la expresión para $n$: $n = 15(7m+3) + 8 = 105m + 45 + 8 = 105m + 53$. El menor entero positivo $n$ se obtiene cuando $m=0$, lo que da $n=53$. Álgebra Para el polinomio $x^3 - 6x^2 + 11x - 6 = 0$, las raíces son $a, b, c$. Por las Fórmulas de Vieta: $a+b+c = -(-6)/1 = 6$ $ab+ac+bc = 11/1 = 11$ $abc = -(-6)/1 = 6$ Queremos calcular $a^2+b^2+c^2$. Sabemos que $(a+b+c)^2 = a^2+b^2+c^2 + 2(ab+ac+bc)$. Despejando $a^2+b^2+c^2$: $a^2+b^2+c^2 = (a+b+c)^2 - 2(ab+ac+bc)$ $a^2+b^2+c^2 = (6)^2 - 2(11)$ $a^2+b^2+c^2 = 36 - 22 = 14$. $\sqrt{x+1} + \sqrt{x-1} = \sqrt{2x+1}$ Dominio: $x+1 \geq 0 \implies x \geq -1$; $x-1 \geq 0 \implies x \geq 1$; $2x+1 \geq 0 \implies x \geq -1/2$. Así, el dominio de la ecuación es $x \geq 1$. Elevamos al cuadrado ambos lados: $(\sqrt{x+1} + \sqrt{x-1})^2 = (\sqrt{2x+1})^2$ $(x+1) + (x-1) + 2\sqrt{(x+1)(x-1)} = 2x+1$ $2x + 2\sqrt{x^2-1} = 2x+1$ $2\sqrt{x^2-1} = 1$ Elevamos al cuadrado de nuevo: $(2\sqrt{x^2-1})^2 = 1^2$ $4(x^2-1) = 1$ $4x^2 - 4 = 1$ $4x^2 = 5$ $x^2 = \frac{5}{4}$ $x = \pm \sqrt{\frac{5}{4}} = \pm \frac{\sqrt{5}}{2}$. Como $x \geq 1$, la única solución válida es $x = \frac{\sqrt{5}}{2}$. Verificamos: $\frac{\sqrt{5}}{2} \approx \frac{2.236}{2} = 1.118$, que es mayor que $1$. Demostrar $(a+b)(b+c)(c+a) \geq 8abc$ para $a, b, c > 0$. Aplicamos la desigualdad AM-GM: $a+b \geq 2\sqrt{ab}$ $b+c \geq 2\sqrt{bc}$ $c+a \geq 2\sqrt{ca}$ Multiplicando las tres desigualdades (todos los términos son positivos): $(a+b)(b+c)(c+a) \geq (2\sqrt{ab})(2\sqrt{bc})(2\sqrt{ca})$ $(a+b)(b+c)(c+a) \geq 8 \sqrt{ab \cdot bc \cdot ca}$ $(a+b)(b+c)(c+a) \geq 8 \sqrt{a^2 b^2 c^2}$ $(a+b)(b+c)(c+a) \geq 8 |abc|$ Como $a, b, c > 0$, entonces $abc > 0$, así que $|abc| = abc$. $(a+b)(b+c)(c+a) \geq 8abc$. La igualdad se cumple cuando $a=b$, $b=c$, $c=a$, es decir, cuando $a=b=c$. Queremos resolver $\frac{x^2-3x+2}{x^2-4} \geq 0$. Primero, factorizamos el numerador y el denominador: $x^2-3x+2 = (x-1)(x-2)$ $x^2-4 = (x-2)(x+2)$ La expresión se convierte en $\frac{(x-1)(x-2)}{(x-2)(x+2)} \geq 0$. Notamos que $x \neq 2$ y $x \neq -2$ para que el denominador no sea cero. Si $x \neq 2$, podemos simplificar $(x-2)$: $\frac{x-1}{x+2} \geq 0$. Ahora analizamos los signos de $(x-1)$ y $(x+2)$: \begin{tabular}{|c|c|c|c|} \hline Intervalo & $x-1$ & $x+2$ & $\frac{x-1}{x+2}$ \\ \hline $x 1$ & $+$ & $+$ & $+$ \\ \hline \end{tabular} Queremos que la expresión sea $\geq 0$. Esto ocurre cuando $x La ecuación funcional es $f(x^2 - y^2) = (x-y)(f(x)+f(y))$. Paso 1: Sea $x=y$. $f(x^2-x^2) = (x-x)(f(x)+f(x))$ $f(0) = 0 \times (2f(x))$ $f(0) = 0$. Paso 2: Sea $y=0$. $f(x^2 - 0^2) = (x-0)(f(x)+f(0))$ $f(x^2) = x(f(x)+0)$ $f(x^2) = xf(x)$. Paso 3: Sustituye $x=0$ en $f(x^2)=xf(x)$. $f(0^2) = 0 \times f(0) \implies f(0)=0$, lo cual ya sabíamos. Paso 4: De $f(x^2)=xf(x)$, si $x=1$, $f(1)=f(1)$, no da información. Si $x=-1$, $f(1)=-f(-1)$. Paso 5: Sea $x=0$ en la original, $f(-y^2) = -y f(y)$. Comparamos $f(x^2)=xf(x)$ y $f(-y^2)=-yf(y)$. Si $x^2 = A$, entonces $f(A) = \pm \sqrt{A} f(\pm \sqrt{A})$. Si $-y^2 = B$, entonces $f(B) = \pm \sqrt{-B} f(\pm \sqrt{-B})$. Sabemos que $f(x^2)=xf(x)$. También, $f(y^2)=yf(y)$. Reemplazando $y$ por $-y$ en $f(x^2-y^2)=(x-y)(f(x)+f(y))$: $f(x^2-(-y)^2) = (x-(-y))(f(x)+f(-y))$ $f(x^2-y^2) = (x+y)(f(x)+f(-y))$. Así, $(x-y)(f(x)+f(y)) = (x+y)(f(x)+f(-y))$. De $f(x^2)=xf(x)$, tenemos $f((-x)^2) = (-x)f(-x) \implies f(x^2) = -xf(-x)$. Por lo tanto, $xf(x) = -xf(-x)$. Si $x \neq 0$, entonces $f(x) = -f(-x)$, lo que significa que $f$ es una función impar para $x \neq 0$. Como $f(0)=0$, $f$ es impar para todo $x$. Entonces $f(-y) = -f(y)$. Sustituyendo esto en la ecuación original: $f(x^2-y^2) = (x-y)(f(x)+f(y))$. Ahora usamos la propiedad de ser impar: $f(x^2-y^2) = f(x^2) - f(y^2)$ es una posible candidata. Si $f(x)=cx$ para alguna constante $c$. $c(x^2-y^2) = (x-y)(cx+cy)$ $c(x-y)(x+y) = (x-y)c(x+y)$ Esto se cumple. Probemos $f(x)=cx$. $f(x^2)=cx^2$ y $xf(x)=x(cx)=cx^2$. Esto es consistente. $f(-y^2)=c(-y^2)=-cy^2$ y $-yf(y)=-y(cy)=-cy^2$. Esto es consistente. Por lo tanto, $f(x)=cx$ es una familia de soluciones. Combinatoria Consideremos a las dos personas que insisten en sentarse juntas como una sola "unidad". Ahora tenemos $4$ unidades para sentar (las $3$ personas restantes y la pareja). Estas $4$ unidades se pueden sentar de $4!$ maneras. Además, las dos personas dentro de la "unidad" pueden intercambiar sus posiciones de $2!$ maneras. Número total de maneras = $4! \times 2! = (4 \times 3 \times 2 \times 1) \times (2 \times 1) = 24 \times 2 = 48$. El comité debe tener $5$ personas de un total de $7$ hombres y $6$ mujeres. Debe haber al menos $3$ mujeres. Esto significa que podemos tener los siguientes casos: 3 mujeres y 2 hombres: $\binom{6}{3} \times \binom{7}{2} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} \times \frac{7 \times 6}{2 \times 1} = 20 \times 21 = 420$. 4 mujeres y 1 hombre: $\binom{6}{4} \times \binom{7}{1} = \binom{6}{2} \times 7 = \frac{6 \times 5}{2 \times 1} \times 7 = 15 \times 7 = 105$. 5 mujeres y 0 hombres: $\binom{6}{5} \times \binom{7}{0} = \binom{6}{1} \times 1 = 6 \times 1 = 6$. Sumando los casos posibles: $420 + 105 + 6 = 531$. Se pueden formar $531$ comités diferentes. Cada saludo involucra a $2$ personas. Si hay $10$ personas y cada una saluda a todas las demás una vez, esto es equivalente a elegir $2$ personas de $10$ sin importar el orden. Esto es una combinación: $\binom{10}{2}$. $\binom{10}{2} = \frac{10!}{2!(10-2)!} = \frac{10!}{2!8!} = \frac{10 \times 9}{2 \times 1} = 45$. Se realizan $45$ saludos en total. Tenemos $3$ colores de calcetines. Queremos asegurarnos de tener un par del mismo color. Aplicamos el Principio del Palomar. Las "cajas" son los colores (3 cajas). Si sacamos $1$ calcetín, puede ser de un color. Si sacamos $2$ calcetines, pueden ser de dos colores diferentes. Si sacamos $3$ calcetines, pueden ser de tres colores diferentes. Si sacamos $4$ calcetines, por el Principio del Palomar, al menos uno de los colores debe repetirse, garantizando un par. Necesitas sacar $3+1 = 4$ calcetines. Queremos encontrar cuántos números entre $1$ y $1000$ (inclusive) son divisibles por $3$ o por $5$. Sea $A$ el conjunto de números divisibles por $3$. $|A| = \lfloor 1000/3 \rfloor = 333$. Sea $B$ el conjunto de números divisibles por $5$. $|B| = \lfloor 1000/5 \rfloor = 200$. El conjunto de números divisibles por $3$ y por $5$ (es decir, por $15$) es $A \cap B$. $|A \cap B| = \lfloor 1000/15 \rfloor = 66$. Usando el Principio de Inclusión-Exclusión: $|A \cup B| = |A| + |B| - |A \cap B|$ $|A \cup B| = 333 + 200 - 66 = 533 - 66 = 467$. Hay $467$ números entre $1$ y $1000$ que son divisibles por $3$ o por $5$.