Olimpiada Matemática — Adrián García Bouzas

Definición

Un entero $n$ es par si $2 \mid n$ , es decir, si existe $k \in \mathbb Z$ con $n = 2k$ . Es impar si $2 \nmid n$ , es decir, si existe $k \in \mathbb Z$ con $n = 2k + 1$ .

La paridad de $n$ es su clase módulo $2$ : $n \bmod 2 \in \{0, 1\}$ .

Teorema

(Reglas de paridad) Sean $a, b$ enteros. Entonces:

Operación	Par $+$ Par	Impar $+$ Impar	Par $+$ Impar
$a + b$	Par	Par	Impar
$a - b$	Par	Par	Impar
$ab$	Par	Impar	Par

En general: $a + b$ es par $\iff$ $a$ y $b$ tienen la misma paridad.

La suma de $n$ números impares es par si $n$ es par, e impar si $n$ es impar.

Demostración

Si $a = 2j$ y $b = 2k$ , entonces $a + b = 2(j + k)$ (par) y $ab = 4jk$ (par). Si $a = 2j + 1$ y $b = 2k + 1$ , entonces $a + b = 2(j + k + 1)$ (par) y $ab = 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1$ (impar). Las demás combinaciones son análogas. $\blacksquare$

Corolario

(Cuadrados y paridades)

(i) Si $n$ es par, $n^2 \equiv 0 \pmod 4$ . Si $n$ es impar, $n^2 \equiv 1 \pmod 4$ .

En particular, $n^2 \not\equiv 2, 3 \pmod 4$ para ningún entero $n$ , y $n^2 \equiv 0$ o $1 \pmod 4$ .

(ii) Si $n$ es impar, $n^2 \equiv 1 \pmod 8$ .

Demostración de (i). Si $n = 2k$ : $n^2 = 4k^2 \equiv 0 \pmod 4$ . Si $n = 2k+1$ : $n^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1 \equiv 1 \pmod 4$ .

Demostración de (ii). Si $n = 2k+1$ : $n^2 = 4k(k+1) + 1$ . Como $k(k+1)$ es el producto de dos enteros consecutivos, es par, así $k(k+1) = 2m$ y $n^2 = 8m + 1 \equiv 1 \pmod 8$ . $\blacksquare$

Este corolario es inmediatamente útil: la ecuación $x^2 + y^2 = n$ no tiene solución si $n \equiv 3 \pmod 4$ , porque el lado izquierdo solo puede ser $\equiv 0, 1, 2 \pmod 4$ .

Ejemplo

Los siguientes ejemplos ilustran la técnica de paridad en orden creciente de sofisticación.

Nivel 1: imposibilidad directa

Ejemplo 1. Demostrar que la suma de tres números impares cualesquiera es impar.

La suma de tres números impares tiene la misma paridad que $1 + 1 + 1 = 3$ , que es impar. $\square$

Ejemplo 2. ¿Es posible que $x^2 + y^2 = 2026$ tenga solución en enteros?

$2026 \equiv 2 \pmod 4$ . Pero $x^2 + y^2 \equiv 0, 1, 2 \pmod 4$ , y el valor $2 \pmod 4$ requiere $x^2 \equiv y^2 \equiv 1 \pmod 4$ , es decir, ambos impares. Pero entonces $x = 2s+1$ y $y = 2t+1$ :

$x^2 + y^2 = (2s+1)^2 + (2t+1)^2 = 4s^2 + 4s + 4t^2 + 4t + 2 = 4(s^2+s+t^2+t) + 2.$

Necesitamos $2026 = 4m + 2$ para algún $m$ , es decir $m = 506$ . ¿Es posible? Sí, la paridad módulo $4$ no descarta. Necesitamos una condición más fina. La representación como suma de dos cuadrados requiere que todo primo $p \equiv 3 \pmod 4$ que divide a $2026 = 2 \cdot 1013 = 2 \cdot 1013$ aparezca con exponente par. $1013$ es primo y $1013 = 4 \cdot 253 + 1 \equiv 1 \pmod 4$ . Por tanto sí hay representación: $2026 = 25^2 + 39^2 + \ldots$ En este caso la paridad fue necesaria pero no suficiente.

Ejemplo 3. Demostrar que $n^2 + n + 1$ es siempre impar para entero $n$ .

$n^2 + n = n(n+1)$ es el producto de enteros consecutivos, siempre par. Así $n^2 + n + 1 = \text{par} + 1 = \text{impar}$ .

Nivel 2: invariante en un proceso

Ejemplo 4. Sobre una pizarra están escritos los números $1, 2, 3, \ldots, 100$ . En cada paso se borran dos números $a, b$ y se escribe $|a - b|$ . Tras $99$ pasos queda un número. ¿Puede ese número ser $1$ ?

La clave: ¿cuál es el invariante?

La suma $S$ de todos los números en la pizarra no es invariante bajo esta operación (ya que $a + b$ es reemplazado por $|a - b|$ , la suma cambia). Pero la paridad de $S$ sí lo es: al borrar $a, b$ y escribir $|a-b|$ , la suma cambia en

$|a - b| - a - b = \pm(a - b) - a - b.$

Si $a \geq b$ : cambia en $(a-b) - a - b = -2b$ , un número par.

Si $b > a$ : cambia en $(b-a) - a - b = -2a$ , un número par.

En ambos casos la suma cambia en un número par, así que la paridad de $S$ es invariante.

La suma inicial es $S_0 = 1 + 2 + \cdots + 100 = 5050$ , que es par. Luego el número final también es par. Como $1$ es impar, no puede ser $1$ . $\square$

Ejemplo 5. Inicialmente hay $n$ fichas, todas cara arriba. En cada paso se voltea exactamente $k$ fichas. ¿Se puede llegar a tener todas las fichas cara abajo?

Sea $f$ el número de fichas cara arriba. Inicialmente $f = n$ . Cada operación cambia $f$ en $\pm k, \pm(k-2), \ldots$ ; en cualquier caso, $f$ cambia en un número de la misma paridad que $k$ .

Si $k$ es impar: cada operación cambia la paridad de $f$ . Para pasar de $f = n$ a $f = 0$ , necesitamos un número de operaciones que cambie la paridad de $n$ a la de $0 =$ par. Esto requiere que $n$ sea impar (empezar impar, cambiar paridad, llegar a par).

Si $k$ es par: $f$ mantiene su paridad. Para llegar a $f = 0$ (par), se necesita que $n$ también sea par.

Conclusión: Se puede llegar a todas cara abajo si y solo si $n \equiv 0 \pmod{\gcd(2, k)}$ ... (La condición completa es más sutil e involucra el número de pasos disponibles, pero la paridad da la obstrucción básica.)

Nivel 3: coloración como paridad extendida

Ejemplo 6. (Tablero mutilado de Gomory) Se elimina la casilla $(1,1)$ y la casilla $(8,8)$ de un tablero de ajedrez de $8 \times 8$ . ¿Se puede cubrir el tablero restante de $62$ casillas con $31$ piezas de dominó de $1 \times 2$ ?

Coloreamos el tablero como tablero de ajedrez: negras las casillas con $i+j$ par, blancas las de $i+j$ impar. Cada pieza de dominó cubre exactamente una casilla negra y una blanca. Los $31$ dominós cubrirían $31$ negras y $31$ blancas.

Las casillas eliminadas son $(1,1)$ y $(8,8)$ , ambas con $i+j$ par, ambas negras. Quedan $30$ negras y $32$ blancas. La diferencia es $2 \neq 0$ .

Pero los $31$ dominós requieren diferencia $0$ . Imposible. $\square$

Ejemplo 7. En un tablero de $n \times n$ se tienen fichas. La operación permitida es: elegir cualquier fila o columna y voltear todas las fichas de esa fila/columna. ¿Puede conseguirse que el número de fichas cara arriba sea exactamente $1$ ?

Sea $f$ el número inicial de fichas cara arriba. Cada operación en una fila/columna cambia el número de fichas cara arriba en $n - 2r$ donde $r$ es el número de fichas cara arriba en esa fila/columna (las cara arriba se voltean para abajo y las cara abajo para arriba). Así $n - 2r \equiv n \pmod 2$ .

Si $n$ es par: cada operación cambia $f$ por un número par. La paridad de $f$ es invariante. Si $f$ inicial es par, el resultado siempre es par; si inicial es impar, siempre es impar. Para llegar a $1$ (impar), $f$ inicial debe ser impar.

Si $n$ es impar: cada operación cambia $f$ por un número impar, alternando la paridad. Si partimos de $f$ par, tras un número impar de movimientos $f$ es impar.

Así la paridad da condiciones sobre qué configuraciones finales son alcanzables.

Nivel 4: cuadrados módulo 4 como herramienta fuerte

Ejemplo 8. Demostrar que $x^2 + y^2 + z^2 = 7$ no tiene solución en enteros.

Los cuadrados son $\equiv 0$ o $1 \pmod 4$ . Por tanto $x^2 + y^2 + z^2$ puede ser $0, 1, 2, 3 \pmod 4$ , pero no $7 \equiv 3 \pmod 4$ .

Espera — sí puede ser $3 \pmod 4$ (tomando $x, y, z$ todos impares: $1 + 1 + 1 = 3$ ). El problema entonces es módulo $8$ : $x^2 \equiv 0, 1, 4 \pmod 8$ para $x$ par, impar, o $\equiv 2 \pmod 4$ respectivamente. Con un análisis más fino, la suma de tres cuadrados $\equiv 0, 1, 2, 3, 4, 5, 6 \pmod 8$ pero no $\equiv 7 \pmod 8$ . Como $7 \equiv 7 \pmod 8$ , no hay solución. $\square$

Teorema (Legendre, 1798). Un entero $n \geq 0$ es suma de tres cuadrados si y solo si $n$ no es de la forma $4^a(8b + 7)$ . La condición módulo $8$ es necesaria y (con la condición módulo $4^a$ ) suficiente.

Ejemplo 9. (OMG 2017, regional) Hay $100$ monedas en una fila, alternando cara-cruz-cara-cruz-... (primera con cara). En cada paso se puede elegir cualquier moneda cara arriba y voltear las dos monedas adyacentes. ¿Se puede llegar a tener todas las monedas con cara?

El invariante: sea $S$ la suma de posiciones (de $1$ a $100$ ) de las monedas con cara arriba. Inicialmente $S = 1 + 3 + 5 + \cdots + 99 = 2500$ (impar... espera, $1 + 3 + \cdots + 99 = 50^2 = 2500$ , par).

Cuando se elige la moneda en posición $p$ (cara arriba) y se voltean las adyacentes en $p-1$ y $p+1$ : si la moneda $p-1$ era cara, $S$ baja en $p-1$ ; si era cruz, $S$ sube en $p-1$ . Análogo para $p+1$ . El cambio de $S$ es $\pm(p-1) \pm (p+1)$ , que es siempre par o impar dependiendo de la paridad de $p-1$ y $p+1$ .

Como $p-1$ y $p+1$ tienen la misma paridad, $\pm(p-1) \pm(p+1) \equiv 0 \pmod 2$ o $\equiv 0 \pmod 2$ — la suma es siempre par. Así $S$ cambia su paridad en múltiplos de... el análisis completo requiere más trabajo, pero la paridad de $S$ módulo $4$ suele dar la respuesta.

(Este problema ilustra que a veces la paridad simple no basta y se necesita el módulo $4$ , como en el análisis de los cuadrados.)

Aplicaciones

Criterios de irresolubilidad. Cuando un problema pide demostrar que algo es imposible, la paridad es lo primero que hay que intentar. Si falla, se pasa a módulo $4$ , luego módulo $8$ , y así sucesivamente hasta encontrar la obstrucción.

Paridad de permutaciones. Cada permutación es un producto de transposiciones. El número de transposiciones en cualquier descomposición tiene la misma paridad (par o impar). Esto define la signatura de una permutación, que es un invariante fundamental en álgebra y en la teoría del determinante.

Problema del $15$ . El rompecabezas del $15$ (las fichas numeradas en un tablero de $4 \times 4$ ) tiene la propiedad de que exactamente la mitad de las $16!$ configuraciones son alcanzables desde la inicial. La condición exacta es que la paridad de la permutación más la paridad de la posición del hueco sea fija. La demostración usa la paridad de permutaciones.

Observación

Paridad como caso especial de módulo $n$ . La paridad es el invariante módulo $2$ . Las mismas ideas generalizan:

Módulo $3$ : suma de cifras módulo $3$ .
Módulo $4$ : cuadrados son $0$ o $1$ (muy útil para sumas de cuadrados).
Módulo $8$ : cuadrados de impares son siempre $1$ (para sumas de tres cuadrados).
Módulo $p$ : criterio de Euler para residuos cuadráticos.

La habilidad en teoría de números es saber qué módulo elegir. La paridad (módulo $2$ ) es la primera opción. Si no basta, se escalan los módulos.

Coloraciones generalizadas. La coloración del tablero de ajedrez (bipartición) es una paridad de la posición: la casilla $(i, j)$ tiene paridad $i + j \pmod 2$ . Generalizando, se puede colorear con $k$ colores donde el color de $(i, j)$ depende de $i + j \pmod k$ . Cada operación de dominó (o de caballo, etc.) mueve entre colores de una forma predecible, y los invariantes de color limitan las configuraciones alcanzables.

Problemas relacionados

(Clásico) Los números $1, 2, \ldots, 2n$ están escritos en un círculo. En cada paso se elige un número y se reemplaza por la diferencia (en valor absoluto) con cada uno de sus dos vecinos, sumando los resultados. ¿Puede terminar con todos ceros?
(OME 2010) En un tablero de $8 \times 8$ , $32$ fichas blancas y $32$ negras se colocan aleatoriamente, una por casilla. ¿Existe siempre una fila o columna que contenga al menos $3$ fichas del mismo color?
(Clásico) Demostrar que la ecuación $x^4 + y^4 = z^2$ no tiene solución entera positiva usando paridad módulo $4$ como primer paso. (Luego se necesita descenso infinito.)
(OMG 2018) Hay $n$ luces numeradas $1, \ldots, n$ , inicialmente todas apagadas. En cada paso se puede cambiar el estado de las luces $k$ y $k+1$ simultáneamente. Determinar para qué valores de $n$ se puede llegar a tener exactamente la luz $1$ encendida y el resto apagadas.
(IMO 1986/1) Sean $A$ , $B$ , $C$ , $D$ cuatro puntos del espacio con la propiedad de que en cada conjunto de tres de ellos hay dos a distancia entera y uno a distancia no entera. Determinar si esto es posible para cuatro puntos colineales. (La paridad de la suma de distancias da la clave.)
(Clásico de combinatoria) Se tienen $n \geq 3$ personas en una rueda. En cada instante, cada persona saluda a su vecino de la derecha y luego se mueven todos un paso a la izquierda. ¿Para qué $n$ es posible que cada par de personas se salude exactamente una vez?