Autor Tema: Problema de divisibilidad con residuo negativo

0 Usuarios y 1 Visitante están viendo este tema.

23 Febrero, 2021, 06:34 am
Leído 190 veces

FerOliMenNewton

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 255
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos,
Recientemente, empecé a estudiar teoría de números y tengo una duda respecto al siguiente problema, el cual me parece un poco raro.
Hay una cierta suma de dinero en yenes. Nos dicen que al dividir entre 77 hay un residuo de -50(desde aquí me parece raro, ya que el residuo siempre se define como una cantidad positiva que es estrictamente menor que el dividendo). También nos dicen que al dividir entre 78 el residuo es cero. Se nos pregunta cuánto vale la suma de dinero.
Denotaré dicha suma por \( S \). De acuerdo a la información, existen \( a,b \) enteros tales que
\( S=77b-50=78a \)
De aquí,
\( 77b-78a=50 \)
Esta es una ecuación diofantina lineal. El máximo común divisor de \( 77 \) y \( 78 \) es \( 1 \), por tanto, de la identidad de Bezout sabemos que existen \( u,v \) enteros tales que
\( 77u-78v=1 \)
Lo menciono porque al conocer una solución particular de la ecuación anterior, inmediatamente conocemos una de la ecuación original.
A ojo, vemos que podemos tomar \( u=v=-1 \) de donde se sigue que podemos tomar \( a=b=-50 \) y cualquier otra solución será de la forma
\( a=-50-77k,b=-50-78k \)
con \( k \) un entero.
Mi pregunta es, ¿Por qué la respuesta correcta es 2106 yenes? Esto corresponde a una elección de \( b=28 \) y \( a=27 \) , pero no entiendo por qué tomar justo esos,¿qué tienen de malo los demás enteros positivos que satisfacen la ecuación?  :P
De antemano gracias.
Saludos.

23 Febrero, 2021, 06:57 am
Respuesta #1

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,234
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

¿Has estudiado aritmética modular? Porque si la respuesta es que sí, la diofántica inicial que propones (que es la correcta) puede reescribirse como

\( 78x\equiv50\pmod{77} \)

mientras que la segunda sería

\( 78x\equiv1\pmod{77} \)

Ambas tienen soluciones distintas, y lo característico son las soluciones principales dentro del conjunto \( \Bbb{Z}_{77} \). En el primer caso la única solución principal es \( x=28 \), que coincide con la respuesta del problema.

También es cierto que en la definición de división entera se impone que el resto sea un positivo estrictamente menor que el dividendo, pero me atrevería decir que en aritmética modular no importa. Porque de la ecuación original podemos reemplazar \( b \) por \( b-1 \) para que quede positivo:

\( 77b-50\to77(b-1)-50\to77b+27, \)

Esto tiene que ver con las clases de equivalencia, aunque ya te digo, todo esto se estudia en aritmética modular, que no sé si lo has estudiado.

Saludos

23 Febrero, 2021, 10:10 am
Respuesta #2

geómetracat

  • Moderador Global
  • Mensajes: 2,199
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Pues tal como yo lo veo la respuesta es que hay infinitas soluciones (todas las que conducen a una suma positiva) y la que te dan como buena es la solución más pequeña. No hay nada en el problema que sirva para descartar \[ S=8112 \] por ejemplo.

Sobre lo del residuo \[ -50 \] ya te ha contestado manooooh, es como lo has interpretado tú. Aunque es cierto que suena raro lo de decir "al dividir entre \( 77 \) queda un resto \( -50 \)".
La ecuación más bonita de las matemáticas: \( d^2=0 \)

23 Febrero, 2021, 10:43 am
Respuesta #3

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,421
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola a todos,
Recientemente, empecé a estudiar teoría de números y tengo una duda respecto al siguiente problema, el cual me parece un poco raro.
Hay una cierta suma de dinero en yenes. Nos dicen que al dividir entre 77 hay un residuo de -50(desde aquí me parece raro, ya que el residuo siempre se define como una cantidad positiva que es estrictamente menor que el dividendo).

Sólo en cuanto a esta cuestión.

Si, por ejemplo, consideras los múltiplos de 7 y pones los números naturales ordenados

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...

y si tomas el número 8, por caso, a éste le sobra 1 para llegar a 7, el resto o la “sobra” es 1, y le faltan 6 para llegar a un múltiplo de 7, la “falta” es -6. Pero son equivalentes; para verlo lo que se hace es sumar el módulo en cuestión: -6+7=1. Así puedes trabajar siempre con restos.

Saludos.

Ayer a las 12:25 am
Respuesta #4

FerOliMenNewton

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 255
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
Ya veo, gracias a todos por sus respuestas  :) .
Pues tal como yo lo veo la respuesta es que hay infinitas soluciones (todas las que conducen a una suma positiva) y la que te dan como buena es la solución más pequeña. No hay nada en el problema que sirva para descartar \[ S=8112 \] por ejemplo.

Sobre lo del residuo \[ -50 \] ya te ha contestado manooooh, es como lo has interpretado tú. Aunque es cierto que suena raro lo de decir "al dividir entre \( 77 \) queda un resto \( -50 \)".

Y sí, nada indica que podamos descartar ese o cualquier otra solución posible distinta de \( 2106 \), pensé que había algo que no estaba viendo.
De nuevo gracias!
Saludos.

Ayer a las 12:50 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,532
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Mi pregunta es, ¿Por qué la respuesta correcta es 2106 yenes? Esto corresponde a una elección de \( b=28 \) y \( a=27 \) , pero no entiendo por qué tomar justo esos,¿qué tienen de malo los demás enteros positivos que satisfacen la ecuación?  :P

Por lo que he visto en varias ocasiones, parece haber una antigua tradición no escrita de formular este tipo de problemas con infinitas soluciones como si la solución fuera única, entendiendo que se busca la menor posible. Hay muchos problemas que aparecen en tratados antiguos de matemáticos griegos, chinos, indios, en los que pasa eso: plantean un problema de congruencias con infinitas soluciones y piden "la solución" y, cuando la calculan, calculan la menor posible. Un ejemplo clásico es el Problema del Ganado de Arquímedes, que pide determinar el número de reses de diversas clases y lo plantea como si sólo hubiera una solución, pero hay infinitas. He visto bastantes más ejemplos similares.

Ayer a las 12:55 am
Respuesta #6

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,234
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola Carlos

Por lo que he visto en varias ocasiones, parece haber una antigua tradición no escrita de formular este tipo de problemas con infinitas soluciones como si la solución fuera única, entendiendo que se busca la menor posible. Hay muchos problemas que aparecen en tratados antiguos de matemáticos griegos, chinos, indios, en los que pasa eso: plantean un problema de congruencias con infinitas soluciones y piden "la solución" y, cuando la calculan, calculan la menor posible. Un ejemplo clásico es el Problema del Ganado de Arquímedes, que pide determinar el número de reses de diversas clases y lo plantea como si sólo hubiera una solución, pero hay infinitas. He visto bastantes más ejemplos similares.

Interesante. Algo similar ocurre cuando se pide decir si una tal función verifica la condición de Lipschitz. Entonces hay infinitos valores (cotas superiores), pero algunos profesores piden la menor.

¿Se te ocurre por qué es esto así? Por otro lado, cuando se plantean estos problemas no se suele decir explícitamente "buscar la menor" sino que ya se sobreentiende, ¿ves bien que se sobreentienda, sí, no, por qué?

Gracias y saludos

Ayer a las 01:09 am
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 9,532
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Se te ocurre por qué es esto así?

Pues porque los matemáticos antiguos veían las cosas de otra manera, y supongo que, acostumbrados a ver problemas "clásicos" formulados así, ha habido matemáticos modernos que han imitado el estilo por tradición, sobre todo en problemas que pretenden ser más o menos "realistas" en los que no queda bien hablar de infinitas soluciones (como éste en el que se supone que se trata de determinar una suma de dinero).

Por poner un ejemplo moderno, éste es un problema que planteó Henry Dudeney en 1917 (aunque es una reformulación de un problema mucho más antiguo):

En 1066 el rey Harold II de Inglaterra se enfrentó al ejército normando de Guillermo el Conquistador en la batalla de Hastings. Según Dudeney, el rey Harold contaba con 61 divisiones de soldados que formaban dispuestas en cuadrados idénticos, pero que formaban un solo cuadrado cuando se unía a ellos el propio Harold. Dudeney pregunta cuántos soldados componían el ejército de Harold II, pero en realidad hay infinitas soluciones posibles.

Por otro lado, cuando se plantean estos problemas no se suele decir explícitamente "buscar la menor" sino que ya se sobreentiende, ¿ves bien que se sobreentienda, sí, no, por qué?

Si te refieres al caso de las constantes de Lipschitz me parece un poco forzado, salvo que en un contexto en particular ya se haya convenido en entenderlo así, por abreviar, y no haya lugar a dudas.

En el caso de este tipo de problemas numéricos, pues es una tradición relativamente inofensiva, porque cuando hay infinitas soluciones suele estar claro que hay infinitas y es natural entender que se pide la menor. No es que esté bien o mal, es que es una tradición que puede considerarse simpática, sin más finalidad que volver más "naturales" ciertos problemas. Queda más frío preguntar por las infinitas posibilidades que podrían darse para que el ejército del rey Harold tuviera la propiedad descrita por Dudeney.


Ayer a las 11:40 am
Respuesta #8

Richard R Richard

  • Ingeniero Industrial
  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 490
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Hola , se tiene que entender que la solución a encontrar el la menor positiva, si bien se puede hablar de cantidades negativas de dinero, no es muy buena respuesta cantidades negativas de peras, manzanas o personas.
-128y-127 es solución menor de la ecuación y hay infinitas menores  pero ninguna es la buscada.
Saludos  \(\mathbb {R}^3\)

Ayer a las 01:06 pm
Respuesta #9

feriva

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,421
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino

Hola, manooooh. Recojo la pregunta que haces a Carlos para dar mi opinión también.



¿Se te ocurre por qué es esto así? Por otro lado, cuando se plantean estos problemas no se suele decir explícitamente "buscar la menor" sino que ya se sobreentiende, ¿ves bien que se sobreentienda, sí, no, por qué?


Fíjate en que es un problema del teorema chino, que tiene más años que yo.

Todo se reduce a que \( \dfrac{x-27}{77}
  \) y \( \dfrac{x}{78}
  \) den valores enteros siendo x el mismo valor en las dos fracciones. Pero imagina que nos dieran sólo esta condición, \( \dfrac{x}{78}
  \). Si x tiene que ser positivo y distinto de cero... la solución más natural es el propio módulo, 78, el primer múltiplo. Un chino de aquella época (con el papel de arroz, mojando la caña de bambú en tinta que tenía que fabricar él mismo, con el sombrero ése en forma de casita que no le dejaba ver, sudando al sol... las moscas...) en este caso no se iba a poner a hacer operaciones extras como multiplicar 78 por 2 y mucho menos por números más grandes.

Pero también es cierto que la solución “más sencilla” puede depender de cómo pensemos y operemos; a mí me sale otra solución “más sencilla”.

Si sumo las dos facciones también tiene que ser un entero; es una forma muy simple de razonar, ¿no?

\( \dfrac{x-27}{77}+\dfrac{x}{78}=y
  \)

\( \dfrac{155x-(27*78)}{(77*78)}=y
  \)

Como x es múltiplo de 78, puedo hacer x=78k y dividir todo por 78 (algo muy corriente que hacemos todos los días para simplificar). Me queda la diofántica

\( 155k+77y=27
  \)

esto es, visto “en moderno”, la congruencia

\( 155k\equiv27(mod\,77)
  \)

Y como 155 da resto 1 módulo 77, pues directamente tengo

\( k\equiv27(mod\,77)
  \)

Lo primero que se me ocurre, es decir k=77+27, pues es obvio que al restarle 27 va a ser divisible entre 77; es con mucho,, creo, el razonamiento más simple.

Ahora lo multiplico por 78 y la solución más evidente, según he operado, es x=8112.

Y quién me dice que no... (salvo que me haya equivocado).

Saludos.