Ternas aditivas

Enunciado

Este ejercicio requiere comprender cuántas de estas ternas aditivas podemos llegar a tener en un conjunto cualquiera (probablemente no sea necesario enfrentarse directamente a 20 elementos), de forma que creemos una estrategia para conseguir tener el máximo posible. También trataremos de probar que no es posible conseguir tener más ternas aditivas de las que indicamos.

Lo más sencillo es empezar por un conjunto de tres números. Evidentemente, a lo sumo se puede conseguir una única terna aditiva. Piensa en un par de números, y su suma, y tendrás numerosos ejemplos.

¿Y si tenemos cuatro números? Entonces, podemos considerar los tres más pequeños. Pueden o no ser una terna aditiva. A lo sumo tendremos una con ellos tres. ¿Cuántas ternas aditivas puden contener al mayor de los cuatro? Supongamos que hay dos. Como tienen en común el nmúmero mayor, hay dos pares entre los tres más pequeños que suman el mayor, si restamos el número común, tenemos dos números iguales, y, claro, ellos tres no pueden formar entonces una terna. Eso quiere decir que hay un máximo de dos en total. Ejemplos, {1, 2, 3, 4}, con las ternas {1, 2, 3} y {1, 3, 4}. Busca las ternas en {2, 5, 7, 12}.

Añadamos uno más. Ya hemos visto que en los cuatro números menores puede llegar a haber un total de dos ternas aditivas, y para hacer ternas aditivas con el quinto número, el mayor, debemos agruparlos de dos en dos para que sumen el quinto. Sólo se puede hacer de dos formas sin repetir un número, ya que si repetimos uno sabemos que hay que repetir el otro. Es decir, que en cinco elementos sólo podemos encontrar cuatro ternas aditivas, eso si podemos agrupar los cuatro números menores de dos en dos de forma que suben lo mismo. Es fácil hacerlo en {1, 2, 3, 4, 5}, con {1, 2, 3}, {1, 3, 4}, {1, 4, 5} y {2, 3, 5}. Es imposible encontrar un quinto número apropiado en el otro ejemplo que dimos para cuatro números.

Sin embargo, empieza a verse una regla, ¿no? Añadir un sexto número supondrá añadir, al máximo de cuatro ternas aditivas, dos más, ya que si hubiese más de dos, en dos de ellas coincidiría uno de los sumandos, y el resultado, luego el otro sumando también sería igual y tendríamos la terna repetida. Luego para seis números podemos conseguir seis ternas a lo sumo. Y las podemos conseguir, añadiendo el 6 a los cinco primeros números, ya que 1 + 5 = 2 + 4 = 6.

Cuando añadamos el 7, tendremos nueve ternas, contando con 1 + 6 = 2 + 5 = 3 + 4 = 7, y es el máximo número de ternas que podemos añadir con un séptimo número, porque sólo podemos hacer tres parejas de números distintos con seis números.

Pasemos al caso general. Supongamos que tenemos un número n para el que tenemos probado que cualquier conjunto de n números tiene un máximo de 1 + 1 + 2 + 2 + 3 + ... + [(n - 1)/2] ternas aditivas. El elemento entre corchetes representa la parte entera. Llamemos sm(n) a esta expresión para abreviar (veremos una manera mejor de calcular este valor al final). Supongamos que también hemos probado que el conjunto {1, 2, 3, ... , n} tiene exactamente esa cantidad sm(n) de ternas aditivas. Si tenemos un conjunto de n + 1 elementos ¿cuál será la máxima cantidad de ternas aditivas que podemos encontrar en él?

Separemos el elemento mayor. Como el resto forman un conjunto de n elementos, se podrán hacer a lo sumo sm(n) ternas aditivas. Y como a lo sumo se pueden encontrar [n/2] parejas distintas de números en el conjunto de n números, sólo se podrán construir [n/2] ternas aditivas que contengan al elemento mayor (recuerda que si hay dos ternas distintas, con el resultado en común y uno de los sumandos igual, el otro también lo es, por lo que ambas son iguales). Por lo tanto, el máximo de ternas aditivas para un conjunto de n + 1 números es sm(n) + [n/2] = sm(n + 1).

Además, el conjunto {1, 2, 3,...,n} tenía exactamente sm(n) ternas aditivas, por lo que {1, 2, 3, ..., n, n + 1} tendrá sm(n) más las ternas formadas por n + 1 y los sumandos 1 + n = 2 + n - 1 = 3 + n - 2 = ..., que hacen un total de [n/2] (si n es par, n/2 y n/2 + 1 serán los términos centrales, y en caso contrario sobrará un número que no podrá ser miembro de ninguna terna aditiva con n + 1). Por lo tanto, tendrá exactamente sm(n + 1) ternas aditivas.

El proceso para demostrar este tipo de fórmulas se llama inducción. Se debe cumplir para los primeros valores, y si se supone demostrado para un valor, se debe demostrar que el siguiente también lo verifica. De esta forma, el resultado es cierto para cualquier valor natural.

Bueno, pues ya sabemos que para 20 números el máximo número de ternas aditivas es 1 + 1 + 2 + 2 + ... + 9 + 9 = (9 + 1)*9 = 90. Y sabemos que {1, 2,..., 20} es un conjunto con 90 ternas aditivas.

Para sumarlo, se suman por separado las progresiones 1 + 2 + ... + 9 (observa que 9 es la parte entera de (20-1)/2) y se multiplica por 2. Supongo que conoces la estrategia de sumar el primero y el último, y contar los sumandos iguales que aparecen. Si el objetivo, en lugar de 20, fuese un número impar, como 35, se calcularía la fórmula para 34 (el par anterior) y se añadiría 17 ((35-1)/2 al total.