Ecuación diofántica

1) Una bodega debe entregar un pedido de 81000 litros de vino sin embotellar. Para ello posee camiones cisterna que transportan 3500 litros cada uno y remolques cisterna que transportan 1500. Cada camión puede llevar como mucho un remolque y, lógicamente, los remolques no pueden circular solos. Ademas, las cisternas deben ir llenas. Si la bodega quiere minimizar el numero de camiones utilizados, ¿cuántos camiones y remolques debe utilizar? ¿Y si cada camión pudiera llevar hasta dos remolques?.
2) Una maquina autoservicio se ha quedado sin cambio y solo puede devolver monedas de 1 euro, monedas de 2 euros y billetes de 5 euros. Si tiene que devolver 29 euros,
a) ¿Puede hacerlo? ¿Por qué?
b) En caso de ser posible, dar todas las posibles maneras de hacerlo.
3)En una bolsa hay monedas de 5, 10 y 20 céntimos. Se sabe que hay en total 24 monedas y que su valor es 2 euros. ¿Qué combinaciones de monedas son posibles?
4) Resolver el siguiente acertijo, propuesto en el siglo IX por el astrónomo indio Mahavira: un grupo de 23 viajeros llega a un campamento y encuentra 63 montones de sacos, todos con el mismo numero de sacos, y un montón adicional con 7 sacos. Si sabemos que los viajeros no podrán cargar con más de 50 sacos y pudieron repartirselos por igual y sin abrirlos, ¿cuántos
sacos había en cada uno de los montones?.
1

1 respuesta

1
Respuesta de
¡Hola Carito1557!
La ecuación diofántica se decuce fácilmente:
Llamando "x" el número de camiones e "y" el número de remolques resulta:
3500x + 1500y = 81000 
en http://gaussianos.com/como-resolver-ecuaciones-diofanticas/
Verás los fundamentos teóricos y prácticos.
Y también te hará falta
http://es.wikipedia.org/wiki/Algoritmo_de_Euclides
La verdad es que no resulta muy fácil entederlo, por eso lo resolveré yo pero tienes que tener delante esas páginas para comprender lo que hago ya que no daré todas las explicaciones que para eso están allí.
La condición necesaria y suficiente para que esa ecuación tenga solución es que el mcd(3500,1500) divida a 81000. Ese máximo común divisor es 500 que divide a 81000 luego hay solución.
Para calcular una solución particular conviene usar el algoritmo de Euclides extendido en el cual se va calculando mcd(a, b) con a>=b como mcd( b, resto de a \ b) y se apuntan los cocientes.
3500/1500 = 2 y resto 500
1500/ 500 = 3 y resto 0
Ahora se forman estas matrices cuyo elemento 2,2 son los cocientes con signo menos en orden inverso a como se extrajeros y multiplicamos esas matrices. Por suerte solo hubo dos cocientes y nuestra operación es esta
|0   1 |     |0    1|       |1  -2|
|1  -3 | X  |1  -2|   =  |-3  7|
Pues los coeficientes son exactamente los de la primera fila.
En efecto mcd (3500,1500) = 1 x 3500 -2 x 1500 = 500
como 81000 / 500 es 162 multiplicaremos ambos miembros por 162 y tendremos
162 x 3500 -324 x 1500 = 81000
(162,-324) es una solución, pero no nos interesa y además carece de sentido porque buscamos una que sea natural en sus dos términos. Pero es el comienzo para hallar otras soluciones.
La teoría dice:
Si x0, y0 enteros son una solución particular de la ecuación ax + by =n
entonces todas las soluciones enteras de la misma son de la forma:
x = x0 + (b/d)t
y = y0  - (a/d)t
siendo de el mcd(a,b) y "t" cualquier número entero.
Pues con esto tenemos que nuestra ecuación tendra estas respuestas:
x = 162 + (1500/500)t = 162 + 3t
y = -324 - (3500/500)t = -324 - 7t
Deberemos elegir un "t" tal que "x" sea positivo lo menor posible para minimizar el número de camiones pero que a la vez "y" sea también positivo y menor que "x" porque no puede haber más remolques que camiones. Una primera aproximación puede obtenerse resolviendo la siguiente inecuación:
162 + 3t >= -324 -7t <==> 10t >= -486 <==> t   >= -48,6 ==> t  >= -48
Tomamos t= -48
x = 162 + 3·(-48) = 162 - 144 = 18
y = -324 -7·(-48) = -324 + 336 = 12
Por si no nos fiamos de la inecuación tomamos  t=-49 y tenemos
x =162 -3·49 = 15
y =-324 +7(49) = 19 
que en efecto no sirve por tener más remolques que camiones
Otros valores válidos podrían surgir con t=-47, -46, etc, pero son peores porque como podrás comprobar salen más camiones que con t =-48
En resumen, la mejor solución es 18 camiones y 12 remolques.
Y lo dejo aquí de momento porque tengo que hacer otras cosas y la cabeza me echa humo. Tampoco iba a dejar sin contestar y que otro se me adelantara con su respuesta después de todo lo que he sudado. Entonces ya contestaré el resto del ejercicio cuando pueda. Espero que te este sirviendo lo visto hasta ahora.
Un saludo.
Ahora tengo unos segundo solamente, resolveré otro poquito.
Dices: ¿Qué pasaría si cada camión pudiera llevar 2 remolques?
En principio no varía la ecuación ya que seguirá siendo una suma de algo multiplicado por 3500 y algo por 1500. Pero en la respuesta se permitirá que "y" pueda tener un valor mayor, en concreto se permitirá 2x <=y.  Es decir:
2(162 + 3t) >= -324 -7t  <==> 324 +6t >= -324 -7t <==> 13t >=-648 <==> t >= - 49,84
Luego t  >= -49 si t es entero
x =  162 + 3(-49) = 15
y = -324 -7(-49) = 19
De nuevo comprobamos que con t =- 50 tendríamos x=12 e y=26 falso porque algun camión tendría que llevar más de dos remolques y con t =-48 harían falta 18 camiones que es más costoso que llevar 15.
En resumen 15 camiones y 19 remolques si pueden llevarse 2remolques por camión.
Quizá fue un poco fuerte el usar matrices para el cálculo de los coeficientes de la solución particular cuando nuestro caso era tan sencillo:
De 3500 = 2 x 1500 + 500 se deducía inmediatamente 500 = 1 x 3500 -2 x 1500
Pero es un método que puede venir bien para situaciones más complejas aunque no es estrictamente necesario.
----------------------------------------------------------------------------------------------------------------
El de las monedas.
Es bien posible basta ver que se consigue con cinco billetes y dos monedas de 2 euros.
En
http://www.educajob.com/xmoned/temarios_elaborados/matematicas/tema15.pdf
Se aborda la ecuación diofántica lineal con más de 2 incógnitas y lógicamente con complejidad creciente. Tanto que en vez de usar el método que sugiere es mejor hacer combinatoria. Tomemos las posibles ternas de, la primera para billetes, la segunda para monedas de 2 y la tercera para euros
0,0,29
0,1,27
0,2,25
0,3,23
0,4,21
0, 5,19
0,6,17
0,7,15
0,8,13
0,9,11
0,10,9
0,11,7
0,12,5
0,13,3
0,14,1
1,0,24
1,1,22
1,2,20
1,3,18
1,4,16
1,5,14
1,6,12
1,7,10
1,8,8
1,9,6
1,10,4
1,11,2
1,12,0
2,0,19
2,1,17
2,2,15
2,3,13
2,4,11
2,5,9
2,6,7
2,7,5
2,8,3
2,9,1
3,0,14
3,1,12
3,2,10
3,3,8
3,4,6
3,5,4
3,6,2
3,7,0
4,0,9
4,1,7
4,2,5
4,3,3
4,4,1
5,0,4
5,1,2
5,2,2
Y esas son todas, no me pidas que las cuente.
Volveré a terminar el problema en otro momento. Otra vez podrás dividirlos en varias preguntas que cada parte tiene mucha miga.
Un saludo.
Perdón, la última era 5,2,0.
Volveré.
Muchas gracias el primer ejercicio lo estoy estudiando, pero no me que da clrao el de las monedas me enrede y como puedes ver son cuatro problemas propuestos, verdad, entonces el de las monedas cual es, el 2 o el 3 por favor, es que no lo entiendo...
Y muchas gracias por su dedicación...
El listado anterior corresponde al segundo problema, el de la máquina de autoservicio. Cada una de las ternas que aparecen contiene el número de billetes de 5, el de monedas de 2 euros y el de monedas de 1 euro. Por ejemplo, la terna:
2,9,1 significa 2 billetes de 5 euros + 9 monedas de 2 euros + 1 moneda de 1 euro.
Comprendo que el primer problema sea complicado, creo que es para estudiantes de carrera de matemáticas y curso elevado. ¿No sé qué estudios tienes tú?
Hoy en día, podría hacerse todo esto de forma mucho más sencilla con programas informáticos. Por ejemplo, en Real Basic, pongamos un botón (PushButton1) y cuatro casillas de texto estático (StaticText1, StaticText2, StaticText3, StaticText4). Para el evento de hacer clic en el botón escribimos la siguiente subrutina:
Sub Action()
  dim x1, y1, lim as integer
  lim=floor(81000/3500)
  x1=1
  while x1<=lim
      y1=0
    while y1<=x1
      if x1*3500 +y1*1500 = 81000 then
        statictext1.text =str(x1)
        statictext2.text =str(y1)
        y1=x1+1
        x1=lim+1
      else
         y1=y1+1
      end if
    wend
    x1=x1+1
  wend
  x1=1
  while x1<=lim
    y1=0
    while y1<=2*x1
      if x1*3500 +y1*1500 = 81000 then
        statictext3.text =str(x1)
        statictext4.text =str(y1)
        y1=x1+1
        x1=lim+1
      else
        y1=y1+1
      end if
    wend
    x1=x1+1
  wend
End Sub
Es un programa muy poco depurado pero muy sencillo y nos dará las respuestas, en:
StaticText1 los camiones cuando solo se permite 1 remolque por camión.
StaticText2 los remolques cuando solo se permite 1 remolque por camión.
StaticText3 los camiones cuando solo se permiten 2 remolque por camión.
StaticText4 los remolques cuando solo se permiten 2 remolque por camión.
Ahora viene el ejercicio tercero.
Llamando por a ls monedas de 5 cents, "y" a las de 10 y "z" a las de 20, tendremos un sistema con dos ecuaciones.
x +y + z = 24
5x + 10y + 20z = 200
despejamos z en la primera ecuación y lo sustituimos en la segunda
z = 24 - x  -y
5x +10y + 20(24 - x -y ) = 200
5x +10y + 480 - 20x - 20y = 200
-15x -10y = -280
 3x + 2y = 56                     [1]
   x+y+z = 24                     [2]
Las soluciones posibles serán siempre números positivos:
x entre 0 y 18 y número par para que se cumpla [1]
Y entre 0 y 20 para no pasar de los 2euros
z entre 0 y 10 para no pasar de los 2 euros
como y<=20 ==> x>5 para que se cumpla [1]
x = 6 ==> y = 19 ==> z = -1 FALSO
x = 8 ==> y = 16 ==> z = 0  VERDADERO
x =10 ==> y = 13 ==>z = 1  VERDADERO
x =12 ==> y = 10 ==>z = 2  VERDADERO
x =14 ==> y =  7 ==> z= 3   VERDADERO
x =16 ==> y = 4 ==> z = 4   VERDADERO
x =18 ==> y = 1 ==> z = 5  VERDADERO
x = 19==>  y = -2                 FALSO
Luego se pueden dar los seis casos señalados como verdadero.
---------------------------------------------------------------------------------------------------------------
El acertijo de los sacos.
Sea "x" el número de sacos de cada montón e "y" los sacos que se llevó cada viajero.
El número de sacos será 63x + 7 y se repartieron entre 23 viajeros. Luego nos dicen que no llevaba cada uno más de 50, eso será seguramente porque la ecuación admite muchas respuestas y con eso se puede hacer que solo haya una. La ecuación es:
63x + 7 = 23y
63x - 23y = -7
Hacemos el algoritmo extendido de Euclides para calcular el mcd y la respuesta particular
63 / 23 = 2 resto 17   [1]
23 /17  = 1 resto 6     [2]
17/ 6    = 2 resto 5     [3]
6/5       = 1 resto 1     [4]
5/1       = 5 resto 0
Ahora viene lo más laborioso, o hacemos el producto de matrices
|0   1 |       |0   1|       |0   1|       |0   1|       |0   1|         |-4  11|
|1  -5 |  x   |1  -1|   x  |1  -2|   x  |1  -1|   x  |1  -2|    =   |21  27|
y en la primera fila del producto está la combinación lineal del mcd(63,23)
-4 · 63 + 11 · 23  = 1
O deshacemos el proceso de las operaciones hechas antes poniendo los restos como dividendo menos cociente por divisor:
de [4] tenemos 1 = 6 - 1·5
por [3]   1 = 6 - 1 (17- 2·6) = -17 + 3·6
por [2]   1 = -17 + 3(23 - 1·17) = 3·23 - 4·17
por [1]  1 = 3·23 -4(63 -2·23) = -4·63 + 11·23
Ambos modos son equivalentes y pesados pero uno de los dos hay que usar. ¡Ojalá fuera más fácil, pero no lo es!
Resumiendo tenemos
-4 · 63 + 11 · 23 =1
multiplicando por -7
(-7)(-4)63 -(7) ·11 · 23 = -7
28 · 63 - 77 · 23 = -7
y (28, 77) es una solución particular de (x,y)
Ahora la teoría dice que siendo (x0, y0) solución particular, toda solución será de la forma
x = x0 + (b/d)t
y = y0 - (a/d)t
siendo de el mcd(a, b) y "t" cualquier número entero.
O sea
x = 28 - 23t
y = 77 - 63t
Si t = 0 ==> y =77 y nos pasamos de los 50 sacos permitidos
Tomamos t =1 que es la única respuesta ya que valdrá porque con 2 se llevan sacos negativos
x = 28 - 23 = 5
y = 77 - 63 = 14
Habia 5 sacos en cada montón, se llevaron 14 cada uno.
Nunca esta mal verificarlo:
los sacos eran 63 · 5 + 7 = 322
se llevaron 14 ·23 = 322
¡biiiiiieen"
Bueno, con esto queda hecho todo, creo que ya me merezco un buen descanso. Ay, por lo que más quieras no te olvides de puntuar (con todo) la pregunta y cerrarla.
Un saludo.
Muchísimas gracias ... y si son complicados imaginate son de teoría de números... en la carrera de matemáticas...
Se lo agradezco un montón... me sirvió bastante tu aclaración
Añade un comentario a esta respuesta
Añade tu respuesta
Haz clic para o
Escribe tu mensaje

Más respuestas relacionadas

¿No es la pregunta que estabas buscando?
Puedes explorar otras preguntas del tema Matemáticas o hacer tu propia pregunta: