Cómo resolver ecuaciones diofánticas

Este artículo ha sido promovido en Menéame. Si te ha gustado y quieres votarlo entra aquí y menéalo.

Motivación

Supongamos que nos encontramos el siguiente problema:

Un hombre va a una tienda de ropa y compra 12 trajes, unos negros y otros grises, por 1200 €. Si los trajes negros valen 30 € más que los grises y ha comprado el mínimo posible de estos últimos, ¿cuántos trajes ha comprado de cada color?

Vamos a plantearlo:

\{trajes \; negros \}=x
\{trajes \;grises \}=12-x

\{precio \; de \; un \; traje \; gris \}=y
\{precio \; de \; un \; traje \; negro \}=y+30

La ecuación queda:

x(y+30)+(12-x)y=1200

Haciendo cuentas nos queda lo siguiente:

30x+12y=1200

Si estabais pensando que nos iba a quedar un sistema de ecuaciones sencillo de resolver estáis equivocados. Nos ha quedado una única ecuación con dos incógnitas. ¿Nos faltan datos? No. Podemos resolverla. Bienvenidos al maravilloso mundo de las ecuaciones diofánticas.

Ecuaciones diofánticas

Una ecuación diofántica es una ecuación algebraica en la que aparecen varias variables cuyas soluciones son números enteros. Es decir, resolver una ecuación diofántica consiste en determinar qué números enteros la cumplen. Su nombre lo toman del matemático Diofanto de Alejandría, quien, además de ser uno de los primeros en utilizar simbolismo en álgebra, se dedicó entre otras cosas al estudio de estas ecuaciones

Las ecuaciones diofánticas del tipo anterior se denominan ecuaciones diofánticas lineales. Este caso particular de este tipo de ecuaciones es el que vamos a aprender a resolver en este artículo. Más concretamente, vamos a mostrar (y demostrar) un método para calcular las soluciones enteras de la ecuación

ax+by=n

con a,b,n \in \mathbb{Z}.

Existencia de soluciones

El primer resultado que vamos a ver y demostrar tiene que ver con la existencia de soluciones de estas ecuaciones. Vamos con él:

Teorema:

Una ecuación lineal diofántica de la forma ax+by=n tiene solución entera x_0,y_0 si y sólo si el máximo común divisor de a y b es un divisor de n.

Además, si llamamos d al mcd(a,b) se tiene que una solución particular de dicha ecuación puede obtenerse de la siguiente forma:

\begin{matrix} x_0=\frac{n}{d} \cdot \alpha \\ y_0=\frac{n}{d} \cdot \beta \end{matrix}

siendo d=\alpha a + \beta b.

Demostración:

1.- Comenzamos con la implicación de izquierda a derecha:

Si la ecuación

ax+by=n (1)

tiene solución entera, entonces existen x_0,y_0 \in \mathbb{Z} tales que ax_0+by_0=n

Como d es un divisor común de a y b, entonces a=a_1 d y b=b_1 d, con a_1,b_1 \in \mathbb{Z}.

Tenemos entonces lo siguiente:

ax_0+by_0=a_1dx_0+b_1dx_0=(a_1x_0+b_1y_0)d=n

Es decir, nos queda una expresión del tipo kd=n, con todos ellos números enteros. En consecuencia tanto k como d deben dividir a n, concluyendo así esta parte de la demostración.

2.- Vamos ahora con la implicación de derecha a izquierda, obteneidno como bonus el además:

Supongamos ahora que d es un divisor de n. Entonces existe k\in\mathbb{Z} tal que n=kd. Por otra parte, por el teorema de Bezout existen \alpha, \beta \in\mathbb{Z} tales que d=\alpha a + \beta b. Multiplicamos los dos miembros de esta igualdad por k:

kd=k \alpha a + k \beta b=n

De donde obtenemos

(k \alpha)a+(k \beta)b=n

Con lo que hemos llegado a que k \alpha y k \beta son soluciones de la ecuación (1).

Entonces:

\begin{matrix} x_0=k \alpha =\frac{n}{d} \cdot \alpha \\ y_0=k \beta=\frac{n}{d} \cdot \beta \end{matrix}

es una solución de la ecuación (1), que es lo que queríamos demostrar. \Box

Lo que hemos conseguido hasta ahora es saber reconocer qué ecuaciones diofánticas lineales tienen soluciones y calcular una solución particular de las mismas. Pero queremos una solución general, es decir, todas las soluciones de las ecuaciones diofánticas lineales que se puedan resolver. A ello vamos en el siguiente punto.

Solución general de una ecuación diofántica lineal

Vamos a demostrar el siguiente teorema:

Teorema:

Si x_0,y_0 \in\mathbb{Z} es una solución particular de la ecuación

ax+by=n (1)

entonces todas las soluciones enteras xy de la misma son de la forma:

\begin{matrix} x=x_0+\frac{b}{d} \cdot t \\ y=y_0-\frac{a}{d} \cdot t \end{matrix} (2)

con t \in\mathbb{Z}, siendo d=mcd(a,b).

Demostración:

Si x_0,y_0 es solución de la ecuación (1), entonces se cumple que ax_0+by_0=n. Pero entonces las expresiones de (2) también son solución de dicha ecuación:

a \left ( x_0+\frac{b}{d}t \right )+b \left ( y_0-\frac{a}{d}t \right )=ax_0+by_0+a \frac{b}{d} t-b \frac{a}{d} t=n

Faltaría ver entonces que todas las soluciones de (1) son de la forma que hemos descrito en (2). A por ello vamos:

Partiendo de la solución particular anterior x_0,y_0, supongamos que tenemos una solución x,y de la ecuación diofántica lineal (1). Tenemos entonces las dos ecuaciones siguientes:

\begin{matrix} ax+by=n \\ax_0+by_0=n \end{matrix}

Restamos las dos ecuaciones, obteniendo

a(x-x_0)+b(y-y_0)=0

Pasando el segundo sumando al otro miembro de la igualdad llegamos a

a(x-x_0)=b(y_0-y) (3)

Dividimos ahora por d:

\frac{a}{d} (x-x_0)=\frac{b}{d} (y_0-y)

Como \textstyle{\frac{a}{d}} y \textstyle{\frac{b}{d}} son números enteros primos relativos (ya que al dividirlos entre su máximo común divisor les hemos quitado los factores que tuvieran en común en un principio), y \textstyle{\frac{a}{d}} divide a \textstyle{\frac{b}{d}} (y_0-y), debe cumplirse que \textstyle{\frac{a}{d}} divida a (y_0-y).

Esto nos lleva a que debe existir t\in\mathbb{Z} tal que:

y_0-y=\frac{a}{d} t

De donde obtenemos que y debe ser de la forma:

y=y_0-\frac{a}{d} t, con t\in\mathbb{Z}

Sustituyendo este valor de y en la ecuación (3) llegamos, después de unos sencillos cálculos, a la expresión buscada para x:

x=x_0+\frac{b}{d} t \quad \Box

Ejemplo práctico

Volvamos a nuestro amigo el de los trajes. Nos quedamos en la ecuación diofántica lineal siguiente:

30x+12y=1200

Vamos a ver si somos capaces de encontrar cuántos trajes de cada color compró este señor.

Como mcd(30,12)=6 es un divisor de 1200 nuestra ecuación tiene soluciones. Para obtener \alpha y \beta debemos utilizar el algoritmo de Euclides para el cálculo del máximo común divisor junto con la identidad de Bezout, citada anteriormente. En este caso se obtiene

6=30-12 \cdot 2

por lo que \alpha=1 y \beta=-2.

Entonces la solución particular queda de la siguiente forma:

\begin{matrix} x_0=\frac{1200}{6} \cdot 1=200 \\ y_0=\frac{1200}{6} \cdot (-2)=-400 \end{matrix}

A partir de esto ya es sencillo encontrar todas las soluciones:

\begin{matrix} x=200 +\frac{12}{6} \cdot t=200+2t \\ x=-400-\frac{30}{6} \cdot t=-400-5t \end{matrix}

En principio estas expresiones nos dan todas las soluciones del problema, pero todavía no hemos terminado. Hay que tener en cuenta más cosas. Analizando los datos obtenidos sabemos que el número de trajes negros que ha comprado es T_N=200+2t, por lo que el número de trajes grises comprados es T_G=12-T_N=12-200-2t=-188-2t.

Teniendo en cuenta que el número de trajes de cada tipo comprados por nuestro amigo debe ser positivo y menor que 12 se tiene lo siguiente:

\begin{matrix} 0 < T_G < 12 \\ 0 < -188-2t < 12 \\ 188 < -2t < 200 \\ -100 < t < -94 \end{matrix}

Por tanto, los únicos valores posibles para t son t=\{-99,-98,-97,-96,-95 \}.

Pero el enunciado también decía que ha comprado el mínimo número de trajes grises posibles. Probando con los valores anteriores esta condición se cumple para t=-95. En consecuencia el protagonista de nuestro problema compró -188-2 (-95)=2 trajes grises y 12-2=10 trajes negros.


Fuente de la demostración:

  • Álgebra y Matemáticas Discretas I, de Carmen Moreno Valencia.

Share

Sin comentarios

  1. Trackback | 28 sep, 2009

    Bitacoras.com

  2. Trackback | 28 sep, 2009

    Cómo resolver ecuaciones diofánticas

  3. Alejandro | 28 de septiembre de 2009 | 15:26

    Vótalo Thumb up 0

    Intersante post. Aunque yo siempre había resuelto estos problemas derivando para hallar el mínimo.

  4. mada | 28 de septiembre de 2009 | 17:57

    Vótalo Thumb up 0

    muy buen post, y muy interesante también!

  5. Emmanuel | 28 de septiembre de 2009 | 21:52

    Vótalo Thumb up 0

    @ Alejandro
    Pero esa función es lineal

    Y pues hasta lo que se una recta no tiene máximos o mínimos XD

    ¿O me equivoco?

    Saludos

  6. M | 28 de septiembre de 2009 | 22:42

    Vótalo Thumb up 0

    Esta es una muestra más de lo cómodo que resulta la linealidad en matemáticas, por la generalidad de resultados que permite. Podrían darse también resultados para las soluciones de la ecuación lineal general a_1 x_1+\ldots+a_n x_n=b.

    Espero que este excelente post nos conduzca, más pronto que tarde, a la joya de la corona: la reciprocidad cuadrática en la resolución de la ecuación cuadrática.

  7. Abeco | 29 de septiembre de 2009 | 05:14

    Vótalo Thumb up 0

    Muy buen trabajo quisiera que me envies el trabajo en formato .tex si es posible.

  8. smart | 29 de septiembre de 2009 | 06:27

    Vótalo Thumb up 0

    Muy interesante.
    Emmanuel, tienes que tener en cuenta que en la recta, y es el precio del traje gris y la x es el número de trajes negros. Esta es una recta que en el primer cuadrante está limitada por y = 100, x= 0 (el coste del traje gris sería de 100 y no habría comprado trajes negros y 12 grises) y y=0,x=40 (habría comprado 40 trajes negros). Además hay una recta que limita las x; x<=12 ya que el número total de trajes es 12, por lo que nunca podrá ser x mayor que este valor. Entonces se trata de ver por qué pares de números naturales pasa ese segmento.

    Quedaría otro caso: que el precio de cada traje no tenga que ser necesariamente un natural sino un real (luego habría que ver si por el redondeo puede tratarse como un número natural haciendo que el precio sea dado en céntimos)

  9. Emmanuel | 29 de septiembre de 2009 | 22:54

    Vótalo Thumb up 0

    Comprendo la metodología que se siguió para llegar a ese resultado de 2 trajes grises y 10 trajes negros,

    Cual es la diferencia entre el resultado obtenido mediante este método de solución de ecuaciones diofánticas en el cual se ha comprado el mínimo de trajes grises y algo simple como siguiendo la lógica (entendiendo como “mínimo” que no pudo haber comprado cero trajes grises)
    y decir el mínimo de trajes grises que compro son 1 y el numero de trajes negros 11???

    que tiene malo esta respuesta? con una simple ecuación sacas cuanto costo cada uno de los trajes si hubiese comprado un traje gris y los otros 11 negros XDD

    x + 11(x+30)=1200
    12x+330=1200
    x=870/12

  10. Sote | 30 de septiembre de 2009 | 03:11

    Vótalo Thumb up 0

    Allí dice:
    \begin{matrix} x=x_0+\frac{b}{d} \cdot t \\ y=y_0-\frac{a}{b} \cdot t \end{matrix}
    Pero, debe ser:
    \begin{matrix} x=x_0+\frac{b}{d} \cdot t \\ y=y_0-\frac{a}{d} \cdot t \end{matrix}

    Genial artículo!

  11. gaussianos | 30 de septiembre de 2009 | 15:15

    Vótalo Thumb up 0

    Emmanuel, en el problema estaba implícito que el precio de cada traje también debe ser un número entero (ya que si no es así la ecuación que se acaba resolviendo no se podría tomar como diofántica, ya que sus soluciones podrían ser números no enteros). Igual lo tenía que haber especificado.

    Sote, cierto. Lo cambio ahora. Gracias :).

  12. Emmanuel | 1 de octubre de 2009 | 00:41

    Vótalo Thumb up 0

    Bueno ya aclarado ese punto ya veo la utilidad de este procedimiento

    Saludos!

  13. Trackback | 1 oct, 2009

    La ecuación de Pell | Gaussianos

  14. Nicolás | 3 de octubre de 2009 | 02:29

    Vótalo Thumb up 0

    Hay un problema que me parece que puede estar relacionado con este tema, al menos en lo que se refiere a cantidades enteras. De todas formas es un ejemplo divertido…
    “El dentista le prohibió a Juan comer más de 10 caramelos por día, pero además, si algún día come más de 7 caramelos, entonces los dos días siguientes no puede comer más de 5 caramelos por día.
    Calcular cuál es el mayor número de caramelos que puede comer Juan durante 25 días seguidos obedeciendo las indicaciones del dentista.”

  15. Ramón | 3 de octubre de 2009 | 03:16

    Vótalo Thumb up 0

    Perdón, hay algo que no entiendo: Debajo de la ecuación 3, en la segunda demostración, por que razón a/d debería dividir a (y0-y) dando como resultado un entero?

    Si no me equivoco (y0-y)/(a/d) no tiene porque ser un entero. Corregidme por favor.

  16. Trackback | 5 oct, 2009

    El algoritmo de Euclides | Gaussianos

  17. magui | 20 de octubre de 2009 | 05:19

    Vótalo Thumb up 0

    genial ya le entendi no encontraba ningun ejemplo que me ayudara a entender ya podre hacer mi tarea gracias gracias

Escribe un comentario

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia. Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.