Este problema es equivalente al problema de la suma de subconjuntos, que pregunta, si se le da un conjunto de enteros, si hay un subconjunto cuyos elementos suman cero (o, equivalentemente, cualquier otro entero fijo). Para obtener una solución de este problema a partir del problema de suma de subconjuntos, simplemente haga un conjunto cuyos elementos sean [math] a_i [/ math], junto con [math] 2 a_i, 3 a_i, [/ math] etc., siempre como [math] n a_i [/ math] es menor que [math] b [/ math]. Luego, verifique si ese conjunto tiene un subconjunto cuya suma es [math] b [/ math].
Lo dejo como un ejercicio para que el lector demuestre que una solución al problema dado también dará una solución al problema de la suma de subconjuntos.
Existen algoritmos de tiempo pseudo-polinomiales para el problema del subconjunto, pero desafortunadamente, se sabe que es NP-completo. Sin embargo, hay algunos resultados parciales interesantes que se pueden establecer para el problema dado.
Vamos a sacar lo obvio del camino: la ecuación [math] a_1 x_1 + \ ldots + a_n x_n [/ math] no tiene posibilidades de ser solucionable a menos que [math] gcd (a_1, \ ldots, a_n) [/ math] se divida [matemáticas] b [/ matemáticas]. De hecho, asumiremos algo un poco más fuerte, a saber, [math] gcd (a_1, \ ldots, a_n) = 1 [/ math]. Ir al caso general de esto es fácil, por lo que no es una gran restricción.
- ¿Existe la transformada de Laplace de 1 / t?
- Cómo contar el número de posibilidades de separar una cadena de n caracteres i veces
- ¿Cuál es el resto de [matemáticas] f (x ^ 7) [/ matemáticas] cuando se divide entre [matemáticas] f (x)? [/matemáticas]
- Cómo demostrar que la raíz de cada número primo es irracional
- ¿Qué es una explicación intuitiva de la identidad de Eulers?
Como nota al margen: si estuviéramos tratando con todos los enteros, esto sería suficiente: el lema de Bézout nos dice que si [math] gcd (a_1, \ ldots, a_n) = 1 [/ math], entonces [math] a_1 x_1 + \ ldots + a_n x_n = b [/ math] siempre se puede resolver sobre los enteros. Desafortunadamente, esto no es suficiente, debido a nuestra restricción a los enteros no negativos .
Defina [math] r_n (b) [/ math] para que sea el número de soluciones [math] (x_1, \ ldots, x_n) [/ math] de manera que [math] a_1 x_n + \ ldots + a_n x_n b [/ math ] Como resultado, uno puede obtener una fórmula asintótica para [matemáticas] r_n (b) [/ matemáticas] en función de [matemáticas] b [/ matemáticas].
Esto se hace haciendo uso del método circular. El quid de la configuración del método es reconocer que:
[matemáticas] r_n (b) = \ int_0 ^ 1 \ sum_ {0 \ leq x_1, \ ldots, x_n \ leq b} e ^ {2 \ pi i (a_1 x_1 + \ ldots + a_n x_n – b)} dx_1 \ dx_2 \ ldots dx_n [/ math]
La gran idea de Hardy, Littlewood y Ramanujan cuando se les ocurrió este método (que es mucho más general de lo que he escrito aquí) fue dividir esta integral en “arcos mayores” y “arcos menores”. aquellas piezas que están cerca de números racionales con pequeños denominadores. En teoría, los arcos principales deberían dominar, dando la mayor contribución: la integral sobre los arcos menores debería cancelarse en su mayoría.
Por supuesto, eso es solo en teoría, en la práctica, tienes que mostrar directamente que los arcos principales dominan. Estrictamente hablando, este análisis no requiere herramientas analíticas extremadamente sofisticadas, pero es difícil , porque hay muchos parámetros para elegir, y encontrar un método que funcione puede ser muy desafiante.
Afortunadamente, el caso particular que tenemos aquí ha sido resuelto. La esencia del resultado que obtienes al final del día es que siempre que [math] b [/ math] sea lo suficientemente grande (es decir, es más grande que alguna constante determinada por [math] a_i [/ math ]), entonces la ecuación de diofantina dada es solucionable. Esto se debe a que, en términos generales, [math] r_n (b) [/ math] debería crecer como [math] \ frac {b ^ {n – 1}} {(n – 1)}} [/ math].