¿Cuántas opciones de signos hacen que la ecuación [matemática] 1 \ pm 2 \ pm 3 \ pm \ ldots \ pm n = 0 [/ matemática] sea verdadera, para una [matemática] n [/ matemática] dada?

Answer 1

Si está buscando una fórmula realmente corta y elegante que implique operaciones elementales, me temo que no hay una. Pero se puede expresar (con bastante facilidad) utilizando una función combinatoria bastante estándar: particiones restringidas. La teoría de las particiones es vasta [1], con muchas capas de relaciones de recurrencia, que generan funciones, aproximaciones e identidades, y este problema es esencialmente preguntar sobre un cierto número de particiones que satisfacen dos condiciones estándar.

Una elección de signos [matemática] \ pm [/ matemática] que hace que [matemática] 1 \ pm 2 \ pm 3 \ pm 4 \ pm \ ldots \ pm n = 0 [/ matemática] se determina mediante un subconjunto de [matemática] \ {1,2, \ ldots, n \} [/ math] que contiene [math] 1 [/ math] y cuya suma es [math] n (n + 1) / 4 [/ math]. Dado tal subconjunto, marcamos sus elementos con [math] + [/ math] y los otros elementos con [math] – [/ math], y la suma total es [math] 0 [/ math] desde [math] 1 +2+ \ ldots + n = n (n + 1) / 2 [/ math]. De manera similar, dada una selección de signos, el subconjunto de esos números marcados con [matemáticas] + [/ matemáticas] se sumarán a [matemáticas] n (n + 1) / 4 [/ matemáticas].

Por supuesto, esto solo funciona si [math] n (n + 1) / 4 [/ math] es un número entero. Si no es así, entonces el número de soluciones es simplemente [matemáticas] 0 [/ matemáticas]. A partir de ahora, asumiremos que [matemáticas] n [/ matemáticas] o [matemáticas] n + 1 [/ matemáticas] es divisible por [matemáticas] 4 [/ matemáticas], lo que significa que [matemáticas] n [/ matemáticas] es congruente a [matemáticas] 0 [/ matemáticas] o [matemáticas] 3 [/ matemáticas] módulo [matemáticas] 4 [/ matemáticas].

En lugar de contar los subconjuntos que contienen [matemáticas] 1 [/ matemáticas], es un poco más fácil contar los que contienen [matemáticas] n [/ matemáticas]. El número de subconjuntos de cualquier tipo es el mismo: es la mitad del número de todos los subconjuntos con suma [matemática] n (n + 1) / 4 [/ matemática]. Un subconjunto que contiene [matemática] n [/ matemática] es lo mismo que un subconjunto de [matemática] \ {1,2, \ ldots, n-1 \} [/ matemática] que se suma a [matemática] n ( n + 1) / 4-n = n (n-3) / 4 [/ matemática].

Veamos un ejemplo para aclarar esto. Hay cuatro soluciones a nuestra ecuación cuando [matemáticas] n = 7 [/ matemáticas], y son

[matemáticas] 1-2-3-4-5 + 6 + 7 = 0 [/ matemáticas]

[matemáticas] 1-2 + 3 + 4-5 + 6-7 = 0 [/ matemáticas]

[matemáticas] 1 + 2-3-4 + 5 + 6-7 = 0 [/ matemáticas]

[matemáticas] 1 + 2-3 + 4-5-6 + 7 = 0 [/ matemáticas]

Cada uno de estos define dos subconjuntos que suman [matemáticas] 14 [/ matemáticas]: los números positivos y los negativos. Por ejemplo, la primera solución proviene de los conjuntos [math] \ {1,6,7 \} [/ math] y [math] \ {2,3,4,5 \} [/ math]. En cada caso, hay exactamente un conjunto que contiene [matemáticas] 7 [/ matemáticas], y los otros números en el conjunto suman [matemáticas] 14-7 = 7 [/ matemáticas]. Y, de hecho, hay cuatro particiones de [matemáticas] 7 [/ matemáticas] que consisten en números distintos entre [matemáticas] 1 [/ matemáticas] y [matemáticas] 6 [/ matemáticas]:

[matemáticas] 1 + 6 = 7 [/ matemáticas]

[matemáticas] 2 + 5 = 7 [/ matemáticas]

[matemáticas] 3 + 4 = 7 [/ matemáticas]

[matemáticas] 1 + 2 + 4 = 7 [/ matemáticas].

---

La conocida función de partición [math] p (n) [/ math] cuenta el número de particiones de [math] n [/ math], que es el número de formas de escribir [math] n [/ math] como un suma de enteros positivos, independientemente del orden. Existen varias variaciones para [math] p (n) [/ math]: por ejemplo, [math] p (n, r) [/ math] generalmente denota el número de particiones de [math] n [/ math] donde los sumandos no son mayores que [math] r [/ math], y [math] q (n) [/ math] se usa generalmente para denotar el número de particiones de [math] n [/ math] en partes distintas (que, según un famoso teorema de Euler, es lo mismo que el número de particiones en partes que son todas impares).

Lo que necesitamos aquí es una combinación de las dos restricciones: usaremos [math] q (n, r) [/ math] para denotar el número de particiones de [math] n [/ math] en partes distintas no mayores que [ matemáticas] r [/ matemáticas]. Con eso, la respuesta a la pregunta es simplemente

[matemáticas] \ displaystyle S (n) = q \ left (\ frac {n (n-3)} {4}, n-1 \ right) [/ math]

En palabras, el número de opciones de signos que resuelven [matemáticas] 1 \ pm 2 \ pm 3 \ pm 4 \ pm \ ldots \ pm n = 0 [/ matemáticas] es el número de particiones de [matemáticas] n (n-3) / 4 [/ math] en distintas partes que no exceden [math] n-1 [/ math].

Las funciones [matemáticas] p (n, r) [/ matemáticas] y [matemáticas] q (n) [/ matemáticas] fueron muy estudiadas desde la época de Euler, y hay una enorme cantidad de información sobre ellas. No pude localizar de inmediato una referencia para nuestra versión restringida “combinada” [math] q (n, r) [/ math], pero estoy seguro de que también hay mucha documentación al respecto.

---

Una tabla que muestra los valores de [math] S (n) [/ math] se puede encontrar, como de costumbre, en el OEIS [2]. Puede ver, por ejemplo, que [matemáticas] S (15) = 361 [/ matemáticas], y de hecho [matemáticas] q (45,14) = 361 [/ matemáticas].

0, 0, 1, 1, 0, 0, 4, 7, 0, 0, 35, 62, 0, 0, 361, 657, 0, 0, 4110, 7636, 0, 0, 49910, 93846, 0, 0, 632602, 1199892, 0, 0, 8273610, 15796439, 0, 0, 110826888, 212681976, 0, 0, 1512776590, 2915017360, 0, 0, 20965992017, 40536016030, 0, 0, 294245741167

Los pares de [matemáticas] 0 [/ matemáticas] corresponden a aquellos valores de [matemáticas] n [/ matemáticas] que son congruentes con [matemáticas] 1 [/ matemáticas] o [matemáticas] 2 [/ matemáticas] módulo [matemáticas ] 4 [/ math], para lo cual no hay solución. Los números crecen bastante rápido, y será interesante determinar su tasa de crecimiento asintótico; lo agregaré aquí una vez que lo descubra.

EDITAR: Christian Schmidt encontró un artículo [3] haciendo exactamente eso (Blair Sullivan, Sobre una conjetura de Andrica y Tomescu ) . Curiosamente, el artículo no menciona la interpretación de suma de signos de [matemáticas] S (n) [/ matemáticas], sino que lo considera como el coeficiente medio en la expansión de

[matemáticas] (1 + x) (1 + x ^ 2) \ cdots (1 + x ^ n) [/ matemáticas]

que es claramente lo mismo: este polinomio tiene un grado [matemático] n (n + 1) / 2 [/ matemático], y el coeficiente medio está en potencia [matemática] n (n + 1) / 4 [/ matemático], contando el número de formas de combinar números distintos de [matemática] 1,2, \ ldots, n [/ matemática] para alcanzar esa suma.

Sullivan demuestra que

[matemáticas] \ displaystyle S (n) \ sim \ sqrt {\ frac {6} {\ pi}} 2 ^ nn ^ {- 3/2} [/ matemáticas].

Notas al pie

[1] The Theory of Partitions (Enciclopedia de Matemáticas y sus aplicaciones): George E. Andrews: 9780521637664: Amazon.com: Libros

[2] A058377 – OEIS

[3] https://cs.uwaterloo.ca/journals…

Answer 2

Este es un problema bastante interesante. Si todos los signos fueran suma, entonces tendríamos el enésimo número triangular, [matemáticas] n * (n + 1) / 2 [/ matemáticas]. Dado que la suma debe ser cero, eso significa que los términos negativos están cancelando los términos positivos. Por lo tanto, la suma de los términos negativos debe ser la mitad de la suma de todos los términos, es decir. [matemáticas] n * (n + 1) / 4 [/ matemáticas]. (Tenga en cuenta que esto solo puede ocurrir si [math] n * (n + 1) [/ math] es divisible por 4, o como se mencionó la respuesta de George Savva, [math] n [/ math] debe ser 3 o 0 mod 4 .)

El número que busca es el número de particiones distintas de [math] n (n + 1) / 4 [/ math] con la partición más grande como máximo [math] n [/ math] y la más pequeña al menos 2. (Desde Tengo que ser positivo en su forma de la pregunta.) Encontrar una fórmula para eso está por encima de mi calificación salarial.

Answer 3

La Enciclopedia en línea de secuencias enteras La Enciclopedia en línea de secuencias enteras® (OEIS®) informa que esta secuencia es conocida y que sus asintóticos se han resuelto.

Número de particiones de suma de la mitad del n-ésimo número triangular por números distintos en el rango de 1 a n. Ejemplo: a (7) = 8 ya que triangular (7) = 28 y 14 = 2 + 3 + 4 + 5 = 1 + 3 + 4 + 6 = 1 + 2 + 5 + 6 = 3 + 5 + 6 = 7+ 1 + 2 + 4 = 7 + 3 + 4 = 7 + 2 + 5 = 7 + 1 + 6. – Hieronymus Fischer, 20 oct 2010

La siguiente fórmula asintótica fue declarada como una conjetura por Andrica & Tomescu en 2002 y probada por BD Sullivan en 2013. Ver su artículo y H.-K. Revisión de Hwang MR 2003j: 05005 del artículo de JIS. – Jonathan Sondow, 11 nov 2013

Fórmula asintótica: a (n) ~ sqrt (6 / Pi) * n ^ (- 3/2) * 2 ^ n para n = 0 o 3 (mod 4) cuando n se acerca al infinito.

a (n) = 0 a menos que n == 0 o 3 (mod 4).

Answer 4

Si te refieres a posibles soluciones, entonces es [matemática] 2 ^ {n-1} [/ matemática]. Tiene (n-1) operadores entre n valores. Cada operador es “+” o “-“, por lo tanto, es una potencia de dos.

Si te refieres a soluciones únicas, entonces es una función recursiva

[matemáticas] F (n) = F (n-1) + n [/ matemáticas]

con [matemáticas] n \ en [1, infnity) [/ matemáticas] y [matemáticas] F (1) = 1 [/ matemáticas]

Aquí está el recuento de soluciones para los primeros diez valores de n

1, 2, 4, 8, 13, 19, 26, 34, 43

Lo comprobé con una función Python simple (no recursiva)

de producto de importación itertools

def F (N):
signos = producto ((- 1,1), repetir = N-1)
respuestas = set ()
para g en signos:
tot = 1 + suma ([s * v para s, v en zip (rango (2, N + 1), g)])
respuestas.add (tot)
volver len (respuestas)

Answer 5

No hay soluciones si n mod 4 = 1 o 2 porque habrá un número impar de números impares en la secuencia.

Hay al menos una solución si n mod 4 = 0.

Más allá de eso estoy atascado!