-----------------------
Conjuntos de sumas de impares
Esta propuesta invita a seguir pensando en sumas de números impares consecutivos a trozos, o mejor todavía, todas las sumas posibles de impares en las que no se repita ningún sumando. Todo número distinto de 2 se puede descomponer en suma de impares distintos, pues, si es impar, la suma la compondría él mismo, y si es par bastaría escribir N=(N-1)+1, suma de dos impares distintos, salvo que N=2.
Podemos representar estas sumas de varias formas. La entrada anterior nos sugiere una forma, y es considerar gnomones situados cada uno en su número de orden dejando huecos. Por ejemplo, la descomposición 15=1+5+9 se puede representar así:
Más compacta y conocida es la de no dejar hueco alguno y adosar las representaciones de los impares para conseguir un diagrama de Ferrers-Young simétrico.
Estos diagramas ayudan a entender las particiones de un número
(ver http://mathworld.wolfram.com/FerrersDiagram.html)
El que nos ha resultado parece una escalera, pero no ha de ser siempre así. En la siguiente imagen puedes ver el correspondiente a 32=1+3+13+15
¿De cuántas formas se puede descomponer un número en suma de impares distintos?
Si acotamos el problema, por ejemplo a sumas de números inferiores o iguales a 2K-1 tendremos la posibilidad de considerar hasta 2K – 1 sumas diferentes, que son las formadas por los distintos subconjuntos de {1, 3, 5, … 2K-1} que son en total 2K y a los que hay que quitar el conjunto vacío, por lo que quedan 2K – 1 sumas diferentes. Sin embargo, los posibles resultados de esas sumas son como mucho K2, porque la suma más pequeña es 1 y la mayor 1+3+5+ … +2K-1= K2.
El análisis anterior nos indica que a partir de K=5 existen más sumas posibles que resultados, luego a algunos de estos se les puede asignar dos o más sumas distintas. Esto era de esperar. Por ejemplo, 8=1+7=3+5
Hemos organizado con hoja de cálculo la búsqueda de todas las S(N) formas posibles de descomponer un número N en sumas de impares distintos. Esencialmente ha consistido en
(1) Calcular K, el orden del mayor impar que puede pertenecer a esas sumas. que para cada número N, que es ENTERO((N+1)/2)
(2) Formar un conjunto de K dígitos binarios, con valores 0,1. Sobre ellos se construyeron todas las variaciones con repetición posibles, que representaban los subconjuntos de {1, 3, 5, 7, … 2K+1}
(3) De las sumas construidas sobre esos subconjuntos se eligieron aquellas cuyo resultado fuera N para acumularlas a un contador y obtener S(N).
De esta forma hemos conseguido la sucesión de la imagen, que coincide con http://oeis.org/A000700
En ella vemos, por ejemplo, que el 16 admite cinco descomposiciones en suma de impares distintos:
16=7+9=5+11=3+13=1+15=1+3+5+7
y 17 otras cinco:
17=17=3+5+9=1+7+9=1+5+11=1+3+13
¿Ves una posible relación empírica?
Parece ser, según la tabla, que un número par y su siguiente suelen presentar el mismo número de descomposiciones, pero algunas otras veces no. Por eso hablamos de algo empírico y aproximado. Puede ser instructivo encontrar las sumas de cada uno para descubrir algunas coincidencias.
Hemos exigido que los números impares sean distintos, pero podríamos permitir repeticiones del tipo 17=1+3+3+3+7. Esto complicaría la cuestión y nos llevaría a las particiones de un número. Puedes consultar
http://hojaynumeros.blogspot.com.es/2011/02/particiones-de-un-numero.html
y
http://hojaynumeros.blogspot.com.es/2011/02/funciones-de-particion-de-un-numero.html
En este caso usaríamos la función “partición en números impares”, que, según demostró Euler, coincide con la partición en partes distintas. (Ver http://oeis.org/A000009) En una entrada posterior comprobaremos esta propiedad.
Estas descomposiciones son casos particulares de la llamada representación de un número según una lista, que ya tratamos en otra entrada (http://hojaynumeros.blogspot.com.es/2010/02/frobenius-y-los-mcnuggets.html)
El concepto es el siguiente: dado un conjunto de números enteros positivos a1, a2, a3,…an, diremos que otro entero positivo N es representable según ese conjunto si existen coeficientes enteros no negativos x1, x2, x3,…xn tales que N= a1*x1+a2*x2+…an*xn
Si exigimos que los coeficientes sólo puedan valer 0 o 1, obtendremos la descomposición en elementos distintos, como hemos hecho en esta entrada. Si los dejamos libres pasaremos al caso general del problema, también llamado “de las monedas”.
Este problema bien merece otra entrada en la que presentemos una herramienta en hoja de cálculo para resolverlo.
No hay comentarios:
Publicar un comentario