Se aprende a resolver problemas principalmente resolviendo problemas. Muchos problemas. En primer lugar, por el mismo motivo por el que se requiere mucha práctica para tocar un instrumento o para escribir bien. Por esto mismo si a uno no le sale un problema al principio no debe desanimarse sino seguir practicando y aprendiendo. En segundo lugar, es útil practicar porque hay ideas que se repiten; cuantos más problemas uno haya resuelto, más probable es que en una prueba reaparezca una idea que uno ya conoce. En tercer lugar, las pruebas exigen no sólo resolver problemas sino resolverlos rápido, y la práctica ayuda también con eso. (Anécdota: hay un problema de olimpíadas que me tomó 10 años resolverlo; eso en una competencia de 4 horas no sirve.)
Primero que nada, siempre es mejor resolver los problemas nosotros mismos. Uno puede leer una solución y sentir que la entiende, pero es muy distinto el aprendizaje que da resolver el problema uno mismo. El consejo es, por lo tanto, no “quemarse” problemas. Es buena idea pasar mucho tiempo, horas, días, pensando un problema. No es una pérdida de tiempo: todo lo contrario. Uno incluso puede mantener una lista de problemas que no le salieron, y volver a ellos cada tanto, a ver si surge alguna idea nueva que permita avanzar. (Puede pasar que un problema no salga porque a uno le falta alguna herramienta; sobre eso hablo más adelante, pero este consejo vale incluso en esos casos.) Cuando uno resuelve problemas difíciles la mayor parte del tiempo está trabado, no avanza, y está bien que sea así. Los mejores problemas, los que hacen que las olimpíadas matemáticas (y la matemática en general) valgan la pena son los que requieren una idea nueva. No hay una receta para resolverlos: por eso son interesantes. Resisten el uso de cualquier herramienta de la que uno disponga. Requieren creatividad. Romperse la cabeza, intentar muchas cosas que fallan hasta encontrar la idea que funciona.
Cuando uno está en una competencia tiene la presión del tiempo, y por lo tanto parece mala idea “desperdiciarlo” simplemente pensando. Pero hay que hacerlo. Cuando uno aprendió unas cuantas herramientas surge la tentación de “atacar” los problemas con todo el arsenal del que uno dispone, sin detenerse demasiado a pensar. Eso tiene cierto sentido, pero es importante desarrollar la intuición (que se gana con la experiencia, resolviendo muchos problemas) que nos dice qué herramientas pueden servir en un problema determinado. Qué caminos tienen una chance de llegar a destino y cuáles van a fracasar seguro y son una pérdida de tiempo. El consejo es tratar de pensar un poco antes de actuar.
Una práctica que es útil en muchos casos es la de considerar “casos chicos” o, en general, una versión simplificada, “de juguete”, del problema. Por ejemplo, si un problema habla de un tablero de \(100\times 100\), tiene sentido pensar primero ese problema en un tablero de \(2\times 2\), o de \(4\times 4\), que uno tiene la posibilidad de visualizar. Estos “casos chicos” es más fácil que nos salgan, y que de ahí surja la idea para resolver el caso más difícil. Una anécdota: el problema 6 del tercer nivel del nacional de OMA 2008 me salió, pero mi solución era horrible, y no quedó del todo bien escrita. Al finalizar la prueba hablé con Lucas Andisco (ex-olímpico), que contó una solución muy elegante. Le pregunté cómo se le ocurrió. Me dijo que se le ocurrió rápidamente mirando el caso \(2\times 2\). Yo le dije “ah pero el caso \(2\times 2\) sale mucho más fácil: es un sistema de ecuaciones lineales, lo resolvés y listo”. Me dijo: “sí, obvio, me di cuenta de eso, pero también me di cuenta de que esa idea no iba a servir para resolver los casos grandes, entonces seguí pensando el caso \(2\times 2\) hasta que tuve esa otra idea, que sí sirve en general”. Moraleja, si se me permite: no sólo pensar casos chicos, sino repensarlos hasta encontrar la manera de resolverlos.
Algo que suele pasar en competencias matemáticas, y que corregirlo también requiere práctica, es dar argumentos que están mal. Cometer errores lógicos. A mí me pasa todo el tiempo. Por eso es importante revisar muchas veces todo lo que uno escribe, tanto las cuentas como los argumentos. Un error común es olvidarse algún caso, alguna situación en la que un argumento falla, en la que algo que decimos que se puede hacer en realidad no se puede. Hay que estar muy atentos a eso, desconfiar de nuestros propios argumentos. También es común cometer errores algebraicos, cosa que se cura con práctica pero también entendiendo la lógica detrás de las manipulaciones algebraicas: en última instancia (no lo considero necesario ni mucho menos) ser capaz de demostrar cualquier manipulación que uno haga a partir de los axiomas (me refiero a los axiomas de cuerpo ordenado de los reales).
Matías Saucedo compiló acá una lista de 10 consejos para competencias que me parecen muy buenos. Agrego uno: entregar todo lo que uno escribe. La mitad de una solución para uno puede no servir de nada, pero puede sumar para el que corrige. Algo que para uno está mal quizás está casi bien (y uno no lo sabe), así que por las dudas conviene entregarlo. Por otro lado, dibujos, cuentas, argumentos que para uno son redundantes o inútiles pueden aclarar una solución que no convence al jurado. Insisto en algo que dice Matías respecto a la claridad: una solución a un problema de matemática es un argumento que intenta convencer al lector de algo (si el problema pide hallar X, busca convencer al lector de que X vale lo que uno afirma que vale; si el problema pide demostrar P, la solución busca convencer al lector de que P es verdad). Es un texto escrito en español. Una sucesión de fórmulas y dibujos (por más coherencia y sentido que tengan para uno) no es una solución. Estrictamente una solución sólo debe contener los pasos lógicos necesarios para derivar la conclusión, pero ayuda al lector agregar el razonamiento detrás de la derivación lógica, el relato de cómo van surgiendo las ideas. Esto también lo ayuda a uno a verificar si el argumento es correcto.
Para resolver problemas de olimpíadas matemáticas a partir de cierto nivel se espera que uno maneje cierto conjunto de herramientas matemáticas. Por ejemplo, en las primeras pruebas de OMA se espera que uno conozca el teorema de Pitágoras, la igualdad de ángulos entre rectas paralelas, el teorema de Thales y la fórmula del área del triángulo y el círculo. A partir de ciertas pruebas se espera que, además de eso, uno conozca los criterios de congruencia y de semejanza de triángulos, lo que implica el llamado “arco capaz”, y que sepa hacer construcciones con regla y compás básicas.
De todas maneras creo que no hay un “programa” en el que se especifica la lista de herramientas que un competidor debe conocer para poder resolver los problemas de una olimpíada. Las herramientas, por otra parte, son eso: herramientas, que uno las adquiere en caso de querer resolver problemas que sin ellas son imposibles o extremadamente difíciles. Son un medio, no un fin. En olimpíadas hay un incentivo a que uno maneje por lo menos las herramientas básicas de cada tipo de problema (geometría, combinatoria, teoría de números, álgebra), y es bueno tener una guía de qué herramientas conviene aprender en cada momento, pero en última instancia esto responde (y está bien que así sea) al interés y las ganas del que compite. Dicho rápido: mi intención no es mandar a estudiar a nadie. Te puede ir bien sin estudiar: ingenio mata estudio en olimpíadas matemáticas. Ahora bien, estudiar determinados temas (y no otros) es útil, y para resolver algunos problemas es casi indispensable.
Doy a continuación una lista de herramientas útiles.
Combinatoria enumerativa básica. Esto es lo más urgente. Sobre todo 1-3. Lo siguiente no es tan importante. (Esto lo aprendí con este apunte.)
Multiplicación: si me tengo que poner una remera y un pantalón y tengo \(A\) remeras y \(B\) pantalones, la cantidad de maneras de vestirme es \(A\cdot B\).
Permutaciones: la cantidad de maneras de ordenar \(N\) números distintos es \(N!\). Se deduce del principio de multiplicación: hay \(N\) posibilidades para el primer número, \(N-1\) para el segundo, \(N-2\) para el tercero, etc, por lo que en total hay \(N\cdot(N-1)\cdot(N-2)\cdot\ldots\cdot1=N!\) maneras.
Números combinatorios: la cantidad de subconjuntos de \(k\) elementos de un conjunto de \(n\) elementos es \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\). ¿Por qué? Si me importara el orden de los \(k\) elementos, contaría cada subconjunto \(k!\) veces (una por cada manera de ordenarlo), y habría \(\frac{n!}{(n-k)!}\) maneras de tomar los \(k\) elementos, ya que habría \(n\) maneras para el primero, \(n-1\) maneras para el segundo, etc, hasta \(n-k+1\) maneras para el \(k\)-ésimo; es decir, \(n\cdot (n-1) \cdot \ldots \cdot (n-k+1)\) maneras, que es \(\frac{n\cdot (n-1) \cdot \ldots \cdot (n-k+1) \cdot (n-k) \cdot \ldots \cdot 1}{(n-k) \cdot \ldots \cdot 1} = \frac{n!}{(n-k)!}\), como dije. Entonces tenemos que \(\binom{n}{k} k! = \frac{n!}{(n-k)!}\), y despejando obtenemos \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\).
Cantidad de subconjuntos de un conjunto de \(n\) elementos: cada subconjunto está determinado por la pertenencia o no de cada uno de los \(n\) elementos; hay dos posibilidades para el primer elemento (pertenece o no pertenece), dos para el segundo, etc; en total hay \(\underbrace{2\cdot 2 \cdot \ldots \cdot 2}_{n\text{ veces}}\), es decir, \(2^n\).
Cantidad de permutaciones de una secuencia: por ejemplo, cuántas palabras distintas se puede formar con las letras de la palabra BANANA; hay una B, tres A y dos N; hay \(6\) lugares donde puede ir la B, luego las A ocupan un subconjunto de \(3\) elementos entre los \(5\) lugares restantes, y por lo tanto hay \(\binom{5}{3}\) lugares para ellas; luego quedan 2 lugares libres y ahí deben ir las N (no hay opción); en total hay, pues, \(6 \cdot \binom{5}{3}\) palabras. En general si hay \(k\) letras distintas y la letra \(i\) figura \(n_i\) veces, se pueden formar \(\frac{(n_1+\cdots+n_k)!}{n_1!\ldots n_k!}\) palabras distintas con esas letras (esta fórmula surge del mismo razonamiento). En el caso de BANANA esto da \(\frac{(1+3+2)!}{1!3!2!}\), que por supuesto es igual a \(6 \cdot \binom{5}{3}\).
Cantidad de maneras de distribuir \(n\) bolitas en \(k\) cajas numeradas: la idea es pensar esto como una palabra de la forma BB|BBB||B, que quiere decir: 2 bolitas en la primera caja, 3 bolitas en la segunda, 0 en la tercera, y 1 en la cuarta (B representa una bolita, y | es un separador entre cajas); en general, uno tiene \(n\) bolitas B y \(k-1\) separadores |, por lo que la cantidad de asignaciones de \(n\) bolitas a \(k\) cajas es \(\frac{(n+k-1)!}{n!(k-1)!}\).
Aplicación: problema 2 del certamen regional de OMA, año 2004, primer nivel.
Nico debe elegir tres números enteros distintos entre 1 y 20 inclusive de modo que al multiplicar los tres números se obtenga un múltuplo de 4. Calcular cuántas maneras tiene Nico de elegir sus tres números.
ACLARACIÓN: Dos elecciones que tienen los mismos tres números no importa en qué orden, son iguales.
Hay algunas cosas más avanzadas de combinatoria enumerativa útiles en olimpíadas, pero se puede vivir sin ellas. Se me ocurren: números de Catalan, lema de Burnside, funciones generatrices. Comentario anecdótico: el lema de Burnside (explicado rápido en wikipedia) es un resultado muy básico de teoría de grupos; no es nada muy sofisticado pero es, digamos, “matemática de universidad”; ahora, este problema de Ñandú (problema 3 de nacional, 3er nivel, 2002) sale con eso (y sin eso sólo sale enumerando a mano, que yo sepa):
En el parque de diversiones van a pintar los 6 autitos de la calesita. Cada autito se pintará de un solo color. Se pueden usar todos o algunos de los siguientes colores: rojo, negro, blanco, verde. ¿De cuántas maneras se pueden pintar los 6 autitos, con la condición de que autitos vecinos queden de distinto color?
Geometría. Un gran material para esto es este excelente apunte de Lucas Andisco. Es demasiado como para leerlo de un tirón, pero se puede ir leyendo de a poquito.
En un trapecio ABCD de base mayor AB, base menor DC y lados no paralelos BC y DA, sea K el punto del lado BC tal que BK = 1/3 BC. Se traza por K la recta paralela a DA que corta a AB en L.
Si BL = CD y el área del trapecio ABCD es 20, calcular el área del triángulo ADL.
Construcciones con regla y compás. Este apunte está bueno.
“Arco capaz”. Está en el apunte de Lucas. A partir de segundo nivel de OMA se supone que uno sabe esto. Potencia de un punto.
Teorema del seno y teorema del coseno. Teorema de la bisectriz.
A partir de acá hay mucho más, empezando por: teorema de Ceva, de Menelao, de Pappus, de Pascal, de Brianchon, de Desargues (todo esto está en “El Retorno”); cuadriláteros armónicos; inversión (también está en El Retorno); razones dobles. Transcribí algo que me contó Lucas Andisco sobre “rotohomotecias” (rotación seguida de homotecia) que es muy elemental pero muy fuerte; me lo pueden pedir. Está también el apunte de Kedlaya, que incluye todas estas cosas y unas cuantas más (como números complejos, desigualdades, transformaciones afines). Y hay muchas más cosas dando vueltas en internet. Pero creo que todos los problemas de IMO deberían salir usando lo que listé hasta inversión y no más que eso.
En geometría, como ven, hay mucha teoría para aprender. Aprender teoría ayuda pero no es indispensable. Por ejemplo, cuando quedé seleccionado para la IMO, en la prueba de selección el problema 2 salía en cinco minutos usando razones dobles, cosa que sólo yo sabía entre los que participamos, así que fue una ventaja para mí. Pero, por supuesto, el problema también salía sin usar razones dobles, sólo que se volvía bastante más difícil. (Razones dobles no es nada muy sofisticado, se puede explicar en dos minutos usando el teorema del seno, pero en este caso saberlo hacía la diferencia.) En balance yo creo que en geometría no es bueno obsesionarse aprendiendo teoría (a pesar de que están los incentivos y la tentación de hacerlo); es mejor saber usar bien las herramientas más elementales, para lo cual hay que resolver muchos problemas.
Teoría de números. Este apunte está bueno. Eso es lo básico, y si uno quiere participar en IMO tiene que saberlo. Para OMA alcanza con ir de a poco.
Teorema de la división. Dice que si \(a,b\) son enteros con \(b\) positivo entonces existen únicos enteros \(q\) y \(r\) tales que \(a=qb+r\) y \(0\leqq r<b\); \(r\) es el resto de dividir \(a\) por \(b\). Esto es la base de toda la teoría de números.
Descomposición en primos (o Teorema Fundamental de la Aritmética, TFA). Un entero positivo \(n\) se puede escribir de manera única (salvo permutación de los factores) como producto de números primos.
Divisibilidad. Si \(a,b\) son enteros decimos que \(a\mid b\) si existe un entero \(c\) tal que \(b=ac\) (se lee “\(a\) divide a \(b\)”, o “\(b\) es múltiplo de \(a\)”). Tenemos que \(a\mid b\) implica \(|a|\leqq |b|\) si \(b\neq 0\); si \(a\mid b\) y \(b\mid c\) entonces \(a\mid c\); si \(a\mid b\) entonces \(a\mid -b\); si \(a\mid b\) y \(a\mid c\) entonces \(a\mid b+c\); si \(a\mid b\) y \(c\) es entero entonces \(a\mid bc\). (Todas estas propiedades son obvias.) Si \(p\) es primo y \(p\mid ab\) entonces \(p\mid a\) o \(p\mid b\). Si \(a\) y \(b\) son coprimos (su máximo común divisor es \(1\)) y \(a\mid bc\) entonces \(a\mid c\). (Estas dos últimas se deducen fácilmente del TFA, pero es hacer trampa, ya que se usan en la demostración del TFA; salen usando el algoritmo de Euclides; ver más abajo.)
Congruencias.
Decimos que \(a\equiv b\,(\text{mód
}n)\) o, más simple, \(a\equiv
b\,(n)\), que se lee “\(a\) es
congruente a \(b\) módulo \(n\)” si y sólo si \(n \mid a-b\) o, lo que es lo mismo, si y
sólo si \(a\) y \(b\) tienen el mismo resto en la división
por \(n\), donde \(a,b,n\) son enteros, \(n\) positivo. Notar que \(a\equiv r\,(n)\) si \(r\) es el resto de dividir \(a\) por \(n\), y \(a\equiv
0\,(n)\) si y sólo si \(n\mid
a\).
La utilidad de esto (que en principio es sólo una
notación) es que se cumplen las siguientes propiedades (muy fáciles de
demostrar): \(a\equiv a\,(n)\); si
\(a\equiv b\,(n)\) y \(b\equiv c\,(n)\) entonces \(a\equiv c\,(n)\); si \(a\equiv b\, (n)\) y \(c\equiv d\, (n)\) entonces \(a+c \equiv b+d \, (n)\), \(a-c \equiv b-d\, (n)\) y \(ac \equiv bd \, (n)\); además \(a\equiv b\, (n)\) implica \(a^k\equiv b^k \, (n)\) si \(k\) es entero positivo.
Un ejemplo de
aplicación de esto es el criterio de divisibilidad por \(9\): un número cuyos dígitos son \(a_ka_{k-1}\ldots a_1a_0\) es divisible por
\(9\) si y sólo si la suma de sus
dígitos \(a_k+a_{k-1}+\cdots+a_1+a_0\)
es divisible por \(9\). ¿Por qué?
Porque \(10\equiv 1\,(9)\), y por lo
tanto \(10^k \equiv 1^k \equiv 1 \,
(9)\), pero el número es \(10^ka_k +
\cdots+ 10a_1+a_0 \equiv a_k+\cdots+a_0 \, (9)\). Es decir, el
número y la suma de sus dígitos tienen el mismo resto en la división por
\(9\).
Algoritmo de
Euclides. Si \(a,b\) son enteros,
su máximo común divisor, \((a:b)\), se
define como el máximo entero positivo que divide a ambos. El algoritmo
de Euclides dice que existen enteros \(x,y\) tales que \(ax+by=(a:b)\), y dice cómo
encontrarlos.
Aplicación: \(a\) y
\(n\) (enteros con \(n>0\)) se dicen coprimos si \((a:n)=1\); en ese caso hay enteros \(x,y\) con \(ax+ny=1\); tomando congruencias, \(1 = ax+ny \equiv ax+0y \equiv ax\,(n)\). Es
decir, existe un entero \(x\) tal que
\(ax \equiv 1 \, (n)\). A \(x\) se lo llama el inverso
(multiplicativo) de \(a\) módulo \(n\), y sólo existe si \(a\) y \(n\) son coprimos (ejercicio: verificar
esto).
Aplicación: podemos demostrar “sin trampa” que si \(a\mid bc\) y \((a:b)=1\) entonces \(a\mid c\); en efecto, sea \(x\) el inverso de \(b\) módulo \(a\); tenemos \(bc\equiv 0\,(a)\), luego multiplicando por
\(x\) tenemos \(bcx\equiv 0\cdot x\equiv 0\,(a)\), pero
\(bcx\equiv bxc\equiv 1\cdot c\equiv
c\,(a)\), luego \(c\equiv
0\,(a)\) y \(a\mid c\), como
queríamos. Con esto también podemos demostrar que si \(p\) es primo y \(p\mid ab\) entonces \(p\mid a\) o \(p\mid b\); en efecto, si \(p\nmid a\) entonces \((p:a)=1\) (¿por qué?) y por lo tanto \(p\mid b\).
Para el regional con saber 1-2 alcanza. Para el nacional conviene
saber congruencias (punto 4). A partir de acá: el pequeño teorema
de Fermat, el concepto de orden módulo \(n\) (*), el teorema chino del
resto, la función
\(\varphi\) de Euler, el teorema de
Fermat-Euler, el lema de
Hensel, raíces
primitivas, ternas
pitagóricas, el “truco
de la cuadrática”. Hay un par de apuntes de Carlos di Fiore de
teoría de números excelentes que puedo conseguir si me los piden, que
tratan algunos de estos temas y otros más avanzados.
(*) Si \(b\) es
coprimo con \(n\) entonces existe \(k\) positivo tal que \(b^k \equiv 1\, (n)\), ya que \(b,b^2,b^3,\ldots\) en algún momento se
repite módulo \(n\) (sólo hay \(n\) restos), es decir \(b^r\equiv b^s\, (n)\) con \(r<s\), luego \(n\mid b^s-b^r=b^r(b^{s-r}-1)\), pero como
\((n:b)=1\), \((n:b^r)=1\) y \(n\mid b^{s-r}-1\), por lo que \(b^{s-r}\equiv 1\,(n)\). El orden de \(b\) mód \(n\) se define como el mínimo \(k\) entero positivo tal que \(b^k \equiv 1 \, (n)\). Tenemos que \(b^t \equiv 1\, (n)\) si y sólo si \(k \mid t\) (¿por qué?).
Combinatoria. No es sólo contar cosas sino más en general estudiar estructuras discretas. Los problemas de combinatoria en este sentido amplio son los que menos se parecen a la matemática que se enseña en la secundaria (al principio ni siquiera parecen problemas de matemática, sino más bien de “ingenio” o de “lógica”), pero son los problemas que tienen un vínculo más estrecho con la matemática que producen los matemáticos hoy en día. En OMA, en los certámenes nacionales y en los selectivos, hay una tradición de problemas de combinatoria muy rica (problemas buenos y difíciles). No hay mucha teoría en forma de teoremas que sirva para resolver problemas de combinatoria, pero sí hay algunas ideas. Lucas Andisco escribió este excelente apunte que sirve de introducción; lo recomiendo mucho.
Nico ordena los números enteros del 1 al 21 inclusive y luego Pablo elige 4 números que estén consecutivos de la lista de Nico. Nico debe pagarle a Pablo una cantidad de pesos igual a la suma de los 4 números que eligió Pablo. Determinar la menor cantidad de dinero que deberá pagar Nico y cómo debe ordenar los números para no tener que pagar más.
ACLARACIÓN: El objetivo de Pablo es cobrar lo más posible y el de Nico es pagar lo menos posible.
Sean \(a_1,\ldots,a_{21}\) los
números del 1 al 21 ordenados por Nico. Pablo puede elegir (entre otros
conjuntos) \(a_1,a_2,a_3,a_4\), o los
siguientes cuatro, etc, hasta \(a_{17},a_{18},a_{19},a_{20}\). Son 5
conjuntos cuya suma total es \(a_1+\cdots+a_{20}\); alguno de ellos va a
sumar al menos el promedio: \(\frac{a_1+\cdots+a_{20}}{5}\). Ahora \(a_1+\cdots+a_{20} =
a_1+\cdots+a_{20}+a_{21}-a_{21}\). Como \(a_1,\ldots,a_{21}\) es una permutación de
\(1,\ldots,21\), su suma es \(1+\cdots+21 = \frac{21\cdot 22}2 = 231\).
Entonces \(a_1+\cdots+a_{20} =
231-a_{21}\). Como \(a_{21}\leqq
21\), tenemos que \(a_1+\cdots+a_{20} =
231-a_{21} \geqq 231-21=210\). Luego entre los 5 conjuntos de 4
números consecutivos que consideramos, alguno suma al menos \(\frac{a_1+\cdots+a_{20}}{5} \geqq
\frac{210}5=42\). ¿Puede ser \(42\) la suma máxima? Para eso los \(\geqq\) deben ser \(=\), las 5 sumas deben ser iguales (única
manera de que la mayor sea igual al promedio) y \(a_{21}=21\); pero entonces \(a_{17}+a_{18}+a_{19}+a_{20}=42\) y \(a_{18}+a_{19}+a_{20}+a_{21}\leqq 42\), lo
que implica que \(21=a_{21}\leqq
42-(a_{18}+a_{19}+a_{20}) = a_{17}\), y por tanto \(21\leqq a_{17}\), pero \(a_{17}\leqq 21\), luego \(a_{17}=a_{21}\), absurdo ya que todos los
números son distintos. Entonces la máxima suma de 4 números consecutivos
debe ser por lo menos \(43\). Con esto
demostramos que, sin importar cómo ordene los números Nico, Pablo
siempre puede ganar \(43\) pesos. El
problema pide determinar la menor cantidad de dinero que deberá pagar
Nico. Demostramos que deberá pagar por lo menos \(43\) pesos. ¿Puede lograr pagar exactamente
\(43\) pesos (y no más que eso)? La
respuesta es sí, y para eso hay que mostrar cómo. Sugiero que el lector
lo intente por su cuenta. Por si no le sale, esta es la solución:
16 10 11 5 17 9 12 4 18 8 13 3 19 7 14 2 20 6 15 1 21.
Coloraciones. El problema clásico es: si le quitamos dos casillas que están en esquinas opuestas a un tablero de \(8\times 8\), ¿de cuántas maneras se puede cubrir con fichas que ocupan \(1\times 2\) casillas del tablero? Respuesta: de ninguna. ¿Por qué? Pintamos de blanco y negro como en el ajedrez. Las esquinas opuestas tienen el mismo color. Entonces al sacarlas hay más casillas de un color que del otro. Pero si logramos cubrir el tablero con fichas de \(1\times 2\), cada una ocupa una casilla blanca y una negra, y por lo tanto la cantidad total de blancas y de negras debe ser la misma: contradicción. Otro muy lindo problema que sale con coloraciones es este, de la IMO 2018. A mí me costó mucho, pero sale, así que no se lo quemen. La única pista que voy a dar es que basta con resolver el caso \(4\times 4\).
Mirar elementos extremos: el que maximiza o minimiza alguna cantidad. El principio del palomar se puede pensar como una aplicación de esta idea: tomamos el palomar con mayor cantidad de palomas; ese palomar debe tener al menos \(2\) palomas. Para más aplicaciones miren este y este apunte.
Grafos. Un grafo es un conjunto de nodos o vértices \(V\) conectados por aristas o ejes \(E\). Por ejemplo, un grupo de personas forma un grafo donde las personas son los vértices y hay una arista entre dos personas si son amigas entre sí. El grado de un vértice se define como la cantidad de vértices con los que está conectado. La suma de los grados de todos los vértices es igual a \(2|E|\), donde \(|E|\) es la cantidad de aristas (es obvio: cada arista la contamos dos veces cuando sumamos los grados). Un camino entre dos vértices \(u\) y \(v\) es una secuencia de vértices \(u_1, u_2, \ldots, u_k\) donde \(u_1=u\), \(u_k=v\) y hay una arista entre \(u_i\) y \(u_{i+1}\) para todo \(i=1,\ldots,k-1\). Podemos partir el grafo en componentes conexas, que son, para cada vértice, el conjunto de vértices a los cuales hay un camino (incluyéndolo). Con esta idea sale este problema (el 5 del selectivo de IMO de 2009). La teoría de grafos existe, pero en olimpíadas creo que no es útil (en su momento compré un libro de teoría de grafos y no me sirvió para nada), salvo quizás por el teorema de Turán y el teorema de Hall (está en este excelente apunte de Agustín Gutiérrez, que no creo que sea muy útil para olimpíadas pero es realmente muy bueno).
Inducción y principio del mínimo. Leer este y este apunte. Principio del mínimo: todo conjunto de números enteros positivos tiene un mínimo. Esto sirve en teoría de números y álgebra también.
Invariantes. Lean este apunte. Recomiendo pensar este problema genial, que lamentablemente me quemé (¡no se lo quemen! pero sepan que sale buscando invariantes).
Juegos. Lean este apunte.
Álgebra. En OMA creo que es raro que haya problemas 100% de álgebra (salvo problemas muy tontos de resolver ecuaciones en los primeros certámenes). Pero en selectivos y en olimpíadas internacionales sí hay.
Resolver ecuaciones cuadráticas. Completar cuadrados. Esto en los nacionales a partir de segundo nivel se asume que los participantes lo saben si no me equivoco.
Factorización \(x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1})\). Fórmula de Newton \((x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k}y^{k}\).
Polinomios. División de polinomios: si \(a\) y \(b\) son polinomios con coeficientes reales y el grado de \(b\) es al menos 1 entonces existen únicos polinomios \(q\) y \(r\) tales que \(a=qb+r\) y el grado de \(r\) es menor al grado de \(b\). (Esto permite hacer aritmética con polinomios: hay polinomios primos, factorización única en primos, congruencias módulo polinomio, etc. En coeficientes reales esto no es muy interesante por el teorema fundamental del álgebra, del cual se deduce que los polinomios primos son de grado 1 o 2, pero en coeficientes racionales sí hay mucha tela para cortar. De todos modos esto no es muy de olimpíadas.) Sigo. Un polinomio de grado \(n\) tiene a lo sumo \(n\) raíces. Ruffini. Un polinomio de grado impar tiene al menos una raíz real. Si \(P\) es un polinomio con coeficientes enteros y \(a,b\) son enteros entonces \(a-b\mid P(a)-P(b)\).
Ecuaciones funcionales. Lean este apunte.
Desigualdades. La base son las siguientes tres desigualdades. AM-GM (media aritmética-media geométrica): si \(a_1,\ldots,a_n\) son reales positivos entonces \[\frac{a_1+\cdots+a_n}n \geqq \sqrt[n]{a_1\ldots a_n},\] con igualdad si y sólo si son todos iguales. Cauchy-Schwarz: si \(a_1,\ldots,a_n\) y \(b_1,\ldots,b_n\) son reales, \[(a_1^2+\cdots+a_n^2)(b_1^2+\cdots+b_n^2) \geqq (a_1b_1+\cdots+a_nb_n)^2,\] con igualdad si y sólo si existe un número real \(\lambda\) tal que \(a_1=\lambda b_1, \ldots, a_n = \lambda b_n\) o \(a_1=\cdots=a_n=0\). Rearrangement. Hay muchas más cosas, pero creo que no conviene invertir mucho tiempo en esto. Si les interesa escribí un apunte con mucha (demasiada) teoría sobre desigualdades, pero no recomiendo su consumo; en general todas las desigualdades razonables de olimpíadas deberían salir con esas tres. A lo sumo Schur, Hölder.