Secuencias Supercrecientes

Una secuencia supercreciente es una lista de números enteros positivos $a_1, a_2, a_3, ... , a_n$ en la que cada término es mayor que la suma de todos los anteriores. $$a_2 > a_1 \\ a_3 > a_1 + a_2 \\ a_4 > a_1 + a_2 + a_3 \\ \vdots \\ a_n > a_1 + a_2 + ... + a_{n-1}$$

Dicho de otro modo, cada número “crece más rápido” que la suma acumulada de los que lo preceden. Veámoslo con un ejemplo clásico:

La secuencia $2, 3, 6, 13, 27, \ldots$ cumple perfectamente esta condición, porque:

$$3 > 2$$

$$2, \color{red}3, 6, 13, 27, \ldots$$

El tercer término (6) supera la suma de los dos primeros (5):

$$6 > 2 + 3$$

$$\underbrace{2,3}_{5}, \color{red}6, 13, 27, \ldots$$

El cuarto término (13) también cumple: $$13 > 2 + 3 + 6$$

$$\underbrace{2,3,6}_{11}, \color{red}{13}, 27, \ldots$$

Y lo mismo ocurre con el siguiente: $$27 > 2 + 3 + 6 + 13$$

$$\underbrace{2,3,6,13}_{24}, \color{red}{27}, \ldots$$

¿Por qué importan las secuencias supercrecientes?

Más allá de ser una curiosidad matemática, estas secuencias tienen aplicaciones muy concretas. Se utilizan en campos como la teoría de la complejidad computacional y la criptografía.

En el primer caso, ayudan a resolver versiones simplificadas del famoso problema de la mochila (o knapsack problem), uno de los grandes retos de la computación. En el segundo, sirven como base para sistemas de cifrado, como el criptosistema de Merkle-Hellman, que aprovecha precisamente sus propiedades especiales.

Ejemplo práctico: resolviendo un problema de mochila con una secuencia supercreciente

Supongamos que tenemos el conjunto $N = \{27, 2, 6, 13, 3\}$ y una mochila con capacidad máxima de 30 unidades. Queremos llenarla exactamente, usando algunos de los objetos, sin pasarnos del límite.

Primero ordenamos los elementos de menor a mayor:

$$a = \{2, 3, 6, 13, 27\}$$

Como esta secuencia es supercreciente, podemos resolver el problema paso a paso con un algoritmo muy simple, en lugar de probar todas las combinaciones posibles.

Buscamos una combinación de los términos que sume exactamente 30:

$$x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + x_4 \cdot 13 + x_5 \cdot 27 = 30$$

Donde cada $x_i$ puede ser 0 (no se elige el elemento) o 1 (sí se elige).

Pasos del algoritmo

Comenzamos por el mayor elemento, $a_5 = 27$. Como $27 \le 30$, lo incluimos: $x_5 = 1$. $$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + x_4 \cdot 13 + \color{red}{1} \cdot 27 = 30 $$
Actualizamos el espacio restante: $m = 30 - 27 = 3$.
El siguiente elemento, $a_4 = 13$, es demasiado grande ($13 > 3$), así que $x_4 = 0$.
Lo mismo con $a_3 = 6$: no cabe, por tanto $x_3 = 0$.
El término $a_2 = 3$ encaja perfectamente en el espacio restante, por lo que $x_2 = 1$.
Ya no queda espacio ($m = 0$), de modo que $x_1 = 0$ y el algoritmo termina.

El resultado final es:

$$ 0 \cdot 2 + \color{red}{1} \cdot 3 + 0 \cdot 6 + 0 \cdot 13 + \color{red}{1} \cdot 27 = 30 $$

$$3 + 27 = 30$$

¡Listo! Hemos llenado la mochila usando solo dos elementos. Gracias a la propiedad supercreciente, el algoritmo funciona de manera directa y rápida, sin necesidad de cálculos complejos ni combinaciones infinitas.

Si la secuencia no fuera supercreciente, este método dejaría de ser válido, y habría que recurrir a algoritmos mucho más costosos.

En resumen, las secuencias supercrecientes son un ejemplo fascinante de cómo una idea matemática sencilla puede tener un impacto real en la informática y la seguridad digital.