Cómo resolver ecuaciones con variables que son números naturales

Answer 1

Como otros han mencionado, puede haber o no una forma general de resolver ecuaciones “como esta” dependiendo de qué clase consideres que es un ejemplo. Las ecuaciones generales de Diophantine no admiten ninguna solución mecánica. La aritmética de precarga tiene un algoritmo de decisión, pero su tiempo de ejecución puede ser prohibitivo.

Una tercera forma de ver su ejemplo es que es una ecuación lineal de diofantina (es decir, consiste solo en términos que contienen solo una variable, no elevada a ninguna potencia). Un sistema de ecuaciones lineales de diofantina puede resolverse mediante un procedimiento mecánico con tiempo de ejecución polinómico.

El método general es expresar el sistema de ecuaciones como una ecuación matricial AX = C, donde X es el vector columna de variables. Luego convierta A a Smith Normal Forma B = UAV, donde U y V son matrices invertibles y B tiene números solo en su diagonal (y todos los ceros más allá de un punto dado). Deje D = UC, entonces si existen soluciones enteras, son del formar:

[matemáticas] V * (d_ {1} / b_ {1,1}, d_ {2} / b_ {2,2}, \ ldots, d_ {k} / b_ {k, k}, h_ {k + 1 }, \ ldots, h_ {n}) [/ math]

donde las b son la diagonal de la forma normal de Smith B, d son las entradas D, k es el número de entradas distintas de cero en la forma normal de Smith, y las h son valores enteros arbitrarios. Si alguna de las divisiones no resulta ser números enteros, no existen soluciones.

¡Uf! La entrada de Wikipedia sobre ecuaciones de diofantina tiene más detalles.

En su caso, solo tenemos una ecuación, por lo que la solución es algo degenerada.

[matemáticas] A = \ begin {bmatrix} 1 y 2 y 3 \ end {bmatrix} [/ math]

[matemáticas] V = \ begin {bmatrix}
1
Y
-2
Y
-3
\\\\
0 0
Y
1
Y
0 0
\\\\
0 0
Y
0 0
Y
0 0
\ end {bmatrix}
[/matemáticas]

[matemáticas] U = \ begin {bmatrix} 1 \ end {bmatrix} [/ math]

[matemática] B = UAV = \ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix} [/ math]

[matemáticas] D = UC = \ begin {bmatrix} 5 \ end {bmatrix} [/ math]

Entonces las soluciones enteras son de la forma

[matemáticas] \ begin {bmatrix}
1
Y
-2
Y
-3
\\\\
0 0
Y
1
Y
0 0
\\\\
0 0
Y
0 0
Y
0 0
\ end {bmatrix} * \ begin {bmatrix} 5 \\\\ h_ {2} \\\\ h_ {3} \ end {bmatrix} = \ begin {bmatrix} 5 – 2h_ {2} – 3h_ {3} \\\\ h_ {2} \\\\ h_ {3} \ end {bmatrix} [/ math]

¡fue mucho trabajo obtener una respuesta bastante simple! Básicamente dice que elija cualquier número que desee para byc, luego calcule [math] a = 5-2b – 3c [/ math], que es más o menos lo que haría con prueba y error de todos modos. Como solo está interesado en valores mayores o iguales a cero, entonces filtraría este conjunto solo para aquellos en los que los tres valores no son negativos. Pero si tuviera más de una ecuación, obtendría una respuesta menos trivial. 🙂

Answer 2

Ah, ecuaciones diofantinas … tengo que amarlas.

Hay aproximadamente 3 categorías de diofantinas que sé cómo resolver (y probablemente una o dos más que se pueden resolver):
1) ecuaciones lineales (como la que estás preguntando)
2) cuadráticos (por ejemplo, [matemática] x ^ 2 – Dy ^ 2 = 1 [/ matemática] – cuando D es positivo y sin cuadrados, esta forma tiene un número contable (infinito) de soluciones, que se vuelven bastante interesantes)
3) cosas que pueden resolverse mediante álgebra simple (no es realmente una categoría propia, pero me gusta pensar que es una sola), por ejemplo, [matemáticas] x ^ 2 + 2x = y ^ 2 + 8 [/ matemáticas] que pueden ser reescrito como [matemática] (x + 1) ^ 2 – y ^ 2 = 9 [/ matemática] es decir [matemática] (x + y + 1) (x-y + 1) = 9 [/ matemática] en cuyo punto puede equiparar los factores con posibles factores de 9.

De todos modos entraré en detalles sobre (1). Estas ecuaciones son mucho más simples que la mayoría: toda la clase tiene un algoritmo bastante simple (aunque algo tedioso) que puede resolverlas. La idea básica es que puedes expresar el máximo común denominador de dos números como una combinación lineal de los números; El mcd se puede encontrar a través del algoritmo euclidiano.

Por ejemplo, para [matemáticas] 10x + 13y = N [/ matemáticas], calcularíamos:
mcd (13,10) = mcd (13% 10, 10) = mcd (3, 10% 3) = mcd (3, 1) = 1

escrito un poco diferente,
[matemáticas] 1 = 3-2 * 1 [/ matemáticas]
[matemáticas] = 3 – 2 (10-3 * 3) = 7 * 3 – 2 * 10 [/ matemáticas]
[matemáticas] = 7 (13-10) – 2 * 10 = 7 * 13-9 * 10 [/ matemáticas]

En este punto, sabemos que [matemáticas] (x, y) = (-9N, 7N) [/ matemáticas] es una solución a nuestra ecuación. Además, podemos calcular todas las soluciones ahora: tienen la forma [matemáticas] (x, y) = (-9, 7) N + (L / 10, -L / 13) n [/ matemáticas] donde [matemáticas ] L = mcm (10,13) = 130 [/ math] y [math] n [/ math] es cualquier número entero, lo que nos da todas las soluciones:

[matemáticas] (x, y) = (-9, 7) N + (13, -10) n [/ matemáticas]

Si solo estamos interesados ​​en soluciones positivas, entonces podemos restringirnos a ellas con bastante facilidad después del hecho.

Si bien demostré este método para solo dos variables, no debería ser terriblemente difícil de generalizar: simplemente ignore el resto de las variables y encuentre una parte de la solución a la vez. Por ejemplo, si nuestra ecuación original tuviera 3 variables, por ejemplo, [matemática] 10x + 13y + 15z = N [/ matemática], solo consideramos [matemática] 10x + 13y = N-15z [/ matemática], es decir, nuestras soluciones serían [matemáticas] (x, y) = (-9, 7) (N-15z) + (13, -10) n [/ matemáticas].

Gracias por el A2A.

Answer 3

Podemos usar técnicas de generación de funciones para contar el número de soluciones para ecuaciones lineales con soluciones enteras. Por ejemplo, para contar el número de tuplas con enteros no negativos [matemática] a, b, c [/ matemática] de modo que [matemática] a + 2b + 3c = 5 [/ matemática], encontraríamos la [matemática] x ^ 5 [/ matemática] coeficiente de [matemática] \ frac {1} {1-x} \ frac {1} {1-x ^ 2} \ frac {1} {1-x ^ 3} [/ matemática] . Consulte Generación de funciones para obtener más información sobre dichos métodos.

Answer 4

Estás de suerte: contar soluciones enteras para ecuaciones puede ser tan difícil como el último teorema de Fermat, pero este problema en particular es factible:

Resolver para a da a = 5-2b-3c, que es necesariamente entero cuando byc son enteros. Como tal

{(a, b, c): byc son enteros, a = 5-2b-3c}

Es el conjunto de soluciones. En este caso, tuvimos suerte porque el coeficiente de a era 1, lo que significa que no había nada que dividir al resolver a. En general, necesitaría una condición adicional en byc para asegurarse de que la fórmula para un entero resultante.

Answer 5

Esta ecuación cae dentro de la llamada aritmética de Presburger, que de hecho es una aritmética decidible (por lo tanto, puede resolverse mecánicamente). El artículo vinculado tiene la definición principal. El algoritmo para resolver las ecuaciones es bastante complicado y se basa en el concepto de eliminación del cuantificador. Intenta buscar esto si quieres obtener algunas ideas.

Aquí puede encontrar un solucionador para ello http://rise4fun.com/z3/tutorialc …

Answer 6

Generalmente, graficar es tu mejor mejor. Si no hay gráficos disponibles, encuentre los valores más pequeños y más grandes posibles para cada uno (a: 1,5) (b: 1,2) (c: 1,1). Dijiste números naturales. Como c solo puede ser igual al número natural 1, eso deja a + 2b = 2. Esto no se puede resolver, ya que enchufar 1 para b hace que a = 0 y esa es la única opción para b.

Sin solución.

Answer 7

de sympy.solvers.diophantine import diophantine
de símbolos de importación sympy

a, b, c = símbolos (‘a, b, c’, Entero = Verdadero)
diofantina (a + 2 * b + 3 * c – 5)

El código enumerado anteriormente utiliza el módulo diofantina de la biblioteca sympy para el lenguaje Python. Define los símbolos utilizados en su ecuación e insiste en que asuman solo valores enteros. Luego pide una solución. La solución que genera es:

conjunto ([(- 3 * c + 2 * t + 5, -t, c)])

Ahora puede trabajar cuando estas coordenadas son todas mayores o iguales que cero.

Answer 8

Los matemáticos usan N o [matemáticas] N [/ matemáticas] para referirse al conjunto de todos los números naturales. Sin embargo, no hay acuerdo sobre si el cero está incluido o no.

En la ecuación de ejemplo anterior, no hay una tupla que satisfaga la ecuación si define N como que no incluye cero [matemática] N ^ 0 [/ matemática].

Si permite un cero, entonces hay cinco tuplas para a, b, c para [matemáticas] N ^ * [/ matemáticas]:
0, 1, 1
5, 0, 0
1, 2, 0
2, 0, 1
3, 1, 0

Usted resuelve este tipo de ecuaciones por prueba y error / sustitución, ya que no tiene suficientes ecuaciones para resolver directamente y hay más de una respuesta.

Answer 9

Las ecuaciones polinómicas (que incluyen ecuaciones lineales) donde solo le interesan las soluciones de enteros se llaman ecuaciones diofantinas. No sé mucho sobre ellos, pero ese es el término de búsqueda que querría usar para obtener más información.