Palíndromos y capicúas

¿Qué es un palíndromo?

Un número palíndromo (o capicúa, en terminología española) es un número cuya representación decimal se lee igual de izquierda a derecha que de derecha a izquierda. Ejemplos: $121$, $1331$, $12321$, $9$, $44$.

Formalmente, $n$ es palíndromo si sus cifras satisfacen $d_i = d_{k-i}$ para todo $i$, donde $d_0, d_1, \ldots, d_k$ son las cifras de $n$ (con $d_0$ la cifra de las unidades y $d_k$ la cifra más significativa).

Los palíndromos aparecen en olympiadas con frecuencia porque combinan condiciones aritméticas (divisibilidad, residuos) con condiciones sobre los dígitos, lo que da sistemas de ecuaciones interesantes.

Palíndromos de 2, 3 y 4 cifras

Palíndromos de 2 cifras: tienen la forma $\overline{aa} = 11a$ con $a \in \{1, \ldots, 9\}$. Son exactamente los múltiplos de 11 entre 11 y 99: $\{11, 22, 33, \ldots, 99\}$. Hay 9 de ellos.

Palíndromos de 3 cifras: tienen la forma $\overline{aba} = 100a + 10b + a = 101a + 10b$ con $a \in \{1,\ldots,9\}$, $b \in \{0,\ldots,9\}$. Hay $9 \times 10 = 90$ de ellos.

Palíndromos de 4 cifras: tienen la forma $\overline{abba} = 1001a + 110b$ con $a \in \{1,\ldots,9\}$, $b \in \{0,\ldots,9\}$. Factorizando: $\overline{abba} = 11(91a + 10b)$. Todo palíndromo de 4 cifras es divisible por 11.

Esta última observación generaliza: todo palíndromo de número par de cifras es divisible por 11, porque la suma alternada de sus dígitos es $0$.

Divisibilidad de palíndromos

Para palíndromos de $2m$ cifras (número par): los dígitos satisfacen $d_i = d_{2m-1-i}$, así que la suma alternada $d_0 - d_1 + d_2 - \cdots - d_{2m-1} = \sum_{i=0}^{2m-1} (-1)^i d_i$. Agrupando en pares $(d_i, d_{2m-1-i})$: como $d_i = d_{2m-1-i}$ y los signos de $i$ y $2m-1-i$ son opuestos (pues $(2m-1-i) + i = 2m-1$ es impar), cada par contribuye $d_i((-1)^i + (-1)^{2m-1-i}) = d_i((-1)^i - (-1)^i) = 0$. La suma alternada total es $0$, lo que prueba $11 \mid n$.

Para palíndromos de $2m+1$ cifras (número impar): el criterio del 11 da suma alternada $= \pm d_m$ (la cifra central). Luego $11 \mid n$ si y solo si $11 \mid d_m$, es decir si y solo si $d_m = 0$. Pero $d_m = 0$ en un palíndromo impar significa que la cifra central es $0$, lo cual es posible (e.g., $10001$).

Resumen: (a) todo palíndromo de número par de cifras es múltiplo de 11; (b) un palíndromo de número impar de cifras es múltiplo de 11 si y solo si su cifra central es $0$.

Palíndromos en base $b$

La definición se extiende: $n$ es palíndromo en base $b$ si sus dígitos en base $b$ se leen igual en ambos sentidos. Por ejemplo, $\overline{121}_{(b)} = b^2 + 2b + 1 = (b+1)^2$ es palíndromo en cualquier base $b \ge 3$ (sus dígitos son $1, 2, 1$, y $(b+1)^2$ siempre es cuadrado perfecto).

Un resultado sorprendente: todo entero positivo es palíndromo en alguna base. Esto se sigue del hecho de que en base $n-1$ (con $n > 2$), el número $n$ se escribe $\overline{11}_{(n-1)}$, que es palíndromo.

Problema clásico: "Demuestra que no existen números palíndromos de 4 cifras en base 10 que sean primos." Prueba: ya mostramos que $\overline{abba} = 11(91a+10b)$. Como $a \ge 1$, se tiene $91a + 10b \ge 91 > 1$. Luego $\overline{abba}$ es compuesto (múltiplo de $11$ mayor que $11$).

Conteo de palíndromos menores que $N$

Contar los palíndromos de exactamente $k$ cifras es sencillo:

Si $k$ es impar, $k = 2m+1$: el palíndromo queda determinado por sus primeras $m+1$ cifras (la cifra más significativa de 1 a 9, las siguientes $m-1$ de 0 a 9, y la cifra central de 0 a 9). Total: $9 \cdot 10^m$.

Si $k$ es par, $k = 2m$: el palíndromo queda determinado por sus primeras $m$ cifras (la más significativa de 1 a 9, las siguientes $m-1$ de 0 a 9). Total: $9 \cdot 10^{m-1}$.

Los palíndromos de 1 a 4 cifras son: $9$ (una cifra) $+ 9$ (dos cifras) $+ 90$ (tres cifras) $+ 90$ (cuatro cifras) $= 198$. Este tipo de conteo aparece en problemas de combinatoria con teoría de números.