Los descendientes del 1

Hoy os voy a dejar un problema que nos ha enviado omalaled de Historias de la Ciencia. Está sacado de la Facultad de Matemáticas y Estadística de la UPC, donde al parecer cada mes proponen uno y regalan un libro a quien lo resuelve. El problema en cuestión es el que propusieron en marzo del año pasado. Aquí os lo dejo tal y como nos lo ha formulado nuestro amigo:

Cada número x tiene 2 hijos, el hijo x+1 y el hijo x/(x+1). ¿Cuáles son los descendientes del número 1? (ojo, no los hijos, sino todos los descendientes).

Se exige alguna demostración, por supuesto 🙂

Yo intuyo por dónde van los tiros, pero todavía no tengo demostración. A ver si entre todos la sacamos.

Author: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

28 Comments

  1. Me da que va a ser que sus descendientes son los naturales y todos los racionales positivos. Pero tampoco tengo demostración. Estamos trabajando en ellou.

    Post a Reply
  2. Tengo una idea: podemos conseguir (aplicando sólo una de las dos reglas) los números naturales y sus inversos. Luego, de ahí, podemos obtener 1/x+1 y (x-1)/x. De ahí se deduce que una parte de las fracciones se obtiene.

    Además, podemos obtener, partiendo de los inversos, 1/x → (x-1)/x. Desarrollando, se obtienen progresivamente el resto de las fracciones.

    No sé cómo formular todo esto en una deostración más o menos formal.

    P.D.:¿Aquí también hay libro?

    Post a Reply
  3. Jose tiene pinta sí.

    David me da que haría falta algo más «formal».

    Por cierto, no, no hay libro, no hay presupuesto por ahora. Pero quien sabe, igual más adelante 🙂

    Post a Reply
  4. un esbozo .. los descendientes izquierdos son 1/n y los derechos n

    como se genera P/Q cualquiera
    si llegamos a algún 1/x o x se demostraría que ese numero se genera a partir de 1

    caso 1)si p >Q
    es ((p-q)/q)+1 su padre seria un p’/q donde p’

    Post a Reply
  5. un esbozo .. los descendientes izquierdos son 1/n y los derechos n

    como se genera P/Q cualquiera
    si llegamos a algún 1/x o x se demostraría que ese numero se genera a partir de 1

    caso 1)si p mayor que Q
    es ((p-q)/q)+1 su padre seria un p’/q donde p’ menor que q , p’= p-q
    caso 2)si p menor que q
    p/q= (p/a)/(q/a) = (p/a)/((p+a)/a) = (p/a)/((p/a)+1)
    a = q-p el padre es un p/a

    como buscar el ancestro de un numero
    .. en el caso 1 vamos reduciendo el denominador hasta tener una fracción menor que uno un entero un 1/numero o un caso 2 , en el caso 2 reducimos el denominador hasta tener un entero o un caso 1 ..
    una demostración mas formal no se hacerla

    Post a Reply
  6. He empezado a leer el post directamente por el enunciado del problema y mientras iba avanzando estaba pensando, «coño, ese problema me suena, me parece que pusieron uno muy parecido en El Full…» xD

    Si no recuerdo mal (es posible que recuerde mal) eran todos los racionales positivos.

    PD: tenéis todos los Fulls colgados en la web de la FME: www-fme.upc.edu

    Post a Reply
  7. Es cierto, Papá Oso. fme es la Facultad de Matemáticas y Estadística.

    Salud!

    Post a Reply
  8. ^DiAmOnD^, es para lo que dan mis estudios de ESO (Bachillerato en progreso, 16% completado)

    principeeto: sí.

    Post a Reply
  9. Hola, mi respuesta es los racionales positivos.

    Es fácil ver q el algoritmo del problema solo produce racionales positivos, lo q se busca entonces es ver si produce a todos los racionales positivos.

    Tomamos un p y q cualquiera. Si p > q, el número p/q proviene del numero (p-q)/q. En caso p

    Post a Reply
  10. Hola, mi respuesta es los racionales positivos.

    Es fácil ver q el algoritmo del problema solo produce racionales positivos, lo q se busca entonces es ver si produce a todos los racionales positivos.

    Tomamos un p y q cualquiera. Si p > q, el número p/q proviene del numero (p-q)/q. En caso q > p, p/q proviene p/(q-p).

    Partiendo de cualquier p/q, buscamos en forma sucesiva encontrar la raíz del árbol operando como se menciona anteriormente. Como en el numerador como en el denominador se observan sucesiones decreciente de números positivos, se va a poder trabajar hasta que p = q y en ese caso probamos q todos los racionales descienden de uno para este algoritmo.

    Post a Reply
  11. Tu razonamiento me parece impecable, Alejandro.

    Post a Reply
  12. Principeeto: no solo me lo creo sino que además pienso ganarme la vida con ello.

    WHAHAHAHAHAHAHA!

    Post a Reply
  13. El crack de Alejandro ha dado con la respuesta correcta. Como Asier dice: impecable.

    Salud!

    Post a Reply
  14. Alejandro, no me ha quedado muy claro de dónde sacas eso pe y qu. Quiero decir, cómo obtienes esas letras, sean cuales sean.

    No sé si ha quedado claro lo que pregunto.

    Post a Reply
  15. El problema me parece que tiene más miga de lo que uno puede poner aquí, si lo que se quiere es poner una demostración rigurosa, claro.
    Como ha dicho ya alguna gente, y yo estoy de acuerdo, se generan los racionales positivos, después habría que demostrar que todo racional se genera de esa forma.

    Lo mejor que se me ocurre es demostrarlo por inducción y ahí es donde se complica la cosa pues se entra en terreno más técnico:
    Primero hay que ordenar todos los números que se obtienen. Lo mejor es hacerlo sobre el gráfico que sale al ir poniendo los números que van saliendo (sale una especie de árbol sobre el que hay que numerar las ramas que salen: 1, 2, 3, … así hasta el infinito).

    Luego se formula la hipótesis de inducción: que todo número racional positivo puede generarse tal y como se describe.

    Se comprueba que la hipótesis es cierta para los primeros casos (que no es más que mirar las primeras ramas del árbol).

    Y luego hay que comprobar que un número cualquiera n/m puede generarse tal y como se ha supuesto, teniendo en cuenta que se está suponiendo que los números anteriores (de acuerdo a la ordenación que se haya tomado) se generan de esa forma.

    El tercer paso es el más complicado y es donde entra en juego la ordenación que se haya tomado.

    Bueno, esto es lo que se me ocurre para demostrarlo, aunque no es propiamente la demostración, sino una indicación de cómo hacerla. Si se escribe entera queda aún más larga.
    Es un problema de 1º de carrera de Matemáticas, así que puede ser algo duro para algunas personas.

    Disculpad la extensión. Saludos y que tengais unos días felices.

    Post a Reply
  16. Hola. Gracias Asier y omalaled por entender mi razonamiento !!

    Davidmh: p y q son enteros positivos cualesquiera. De esta manera se puede formar cualquier racional positivo como p/q. Si uno prueba algo para cualquier racional positivo sin poner ninguna otra condicion, automaticamente lo estara probando para todos los racionales positivos.

    Espero q haya sido esta tu duda.

    Post a Reply
  17. No me he explicado ¿cómo obtienes esos pe y qu cualesquiera?

    Post a Reply
  18. Davidmh «p» y «q» como dicen son enteros positivos cualesquiera, esto significa que podemos tomar cualquier entero y llamarlo «p», y tomar otro entero cualquiera y llamarlo «q», para que a partir de ahí podamos seguir con la demostración.

    Esto quiere decir que nos da igual el valor de «p» y «q», es decir, nos da igual el número que llamemos «p» o «q», podemos usar cualquiera.

    Para abreviarlo todo en una frase, «p» y «q» se obtienen poniendo el número que a tí te plazca, siempre que sea entero positivo.

    Post a Reply
  19. oscarchan: se hace al revés de como dices; demuestras que cualquier racional (p/q) tiene un solo padre y ese padre está más cerca del 1 que el hijo. Ahí es donde se aplica la inducción.

    Davidhm: p y q son, como dice neok, cualesquiera. Imagina que haces un razonamiento para dos números enteros, por ejemplo, 55 y 102 y tienes unas consecuencias. Ahora tomas el 17 y el 19 y haces el mismo razonamiento y tienes las mismas consecuencias … entonces dices: sean dos número p y q (que pueden ser 55 y 102 o 17 y 19 y así extensible a dos números cualesquiera).

    Quizás este razonamiento parezca trivial para muchos, pero he dado muchas clases de matemáticas y siempre enpiezo preguntando a mis alumnos «si te hablo con letras en vez de números, ¿me entiendes?».

    Salud

    Post a Reply
  20. omalaled has conseguido el comentario 2.000 de Gaussianos.

    ¡Gracias a todos!

    Post a Reply
  21. OOOOOeeeeeee … ¡Vamos a por el 3.000! 🙂

    Por cierto, qie no es «enpiezo, sino «empiezo»; pero el fallo es porque la m y la n están al lado en el teclado.

    Pasad buenas fiestas

    Post a Reply
  22. omalaled cuánta razón tienes en lo del tema de las letras y los números. Yo también lo he visto en mis clases.

    Por cierto, la i y la u también están al lado en el teclado 😛

    Post a Reply
  23. Los descendientes son los racionales positivos, para demostralo basta probar que todos los racionales entre cero y uno son descendientes de uno, luego estaran todos, ya que sumando uno repetidas veces obtenemos todos los racionales positivos.
    El otro hijo (x/(x+1)) nos permite probar esto, empezando de un entero p obtenemos todas las fracciones de tipo p/(np+1), si empezamos con p/2 obtenemos p/(np+2), etc; luego si probamos que las fracciones de tipo p/q con q

    Post a Reply
  24. Alejandro, dices que puedes obtener p = q cuando definiste que p > q o p < q !?!?
    ¿O quisiste decir que llegamos a numerador = denominador?

    No me quedó claro eso. Por otro lado, si este último fuese el caso, ¿cuál es la forma de operar para llegar a esto? Digo, no me queda claro si usar una ecuación de recurrencia u otra cosa.

    Post a Reply
  25. Partiendo de 1 te da por un lado los naturales (que creo que eso es evidente) y por otro lado los número de la forma \frac{1}{n},\ n\in\mathbb{N} . El primer desdenciendiente de 1 (su hijo) sería \frac{1}{1+1}=\frac{1}{2}. Ahora, por inducción, suponemos que \frac{1}{n} es un descendiente y vemos cuál es su descendiente:
    \dfrac{\frac{1}{n}}{1+\frac{1}{n}}=\dfrac{\frac{1}{n}}{\frac{n+1}{n}}=\frac{1}{n+1}
    Por lo que así se generan todos los descendientes.

    Post a Reply
  26. Sea H el conjunto de los descendientes de 1.

    ○H no es vacio, pues 2=1+1 esta en H.
    ○H solo contiene racionales positivos. En efecto, los hijos de 1 son 2 y 1/2, y si x es un racional positivo, x+1 sera racional positivo y x/(x+1) sera racional positivo. (induccion veloz(?)).
    ○1 no esta en H. Si 1 estuviese en H, tendria un padre, x, que satisfaria que x+1=1, por lo que x=0, y x no estaria en H (padre ausente); o x/(x+1)=1, por lo que 1=0 (padre demente).

    Supondremos entonces que H esta formado solamente por racionales positivos a/b, tal que a y b son distintos.
    Ahora bien, los hijos de a/b son:
    ○a/b+1=(a+b)/b o
    ○(a/b)/(a/b+1)=a/(b+a).

    De igual manera, se puede determinar que el padre de a/b o es (a-b)/b o a/(b-a), dependiendo de si a>b o b>a respectivamente. De esta manera, tambien se demuestra que todo elemento de H solo puede tener un padre, para no violar la tricotomia.

    Supongamos entonces que tenemos a/b. Vemos que existe un numero finito de generaciones que comienzan en 1 y acaban en a/b. Para demostrar esto, comenzaremos con a/b y localizaremos a su padre. Para este ultimo, haremos lo mismo y asi, en lo posible, hasta llegar a 1.

    Definiremos a continuacion el proceso:
    ○Si a>b entonces el padre es (a-b)/b, pues (a-b)/b es mayor que cero, es racional positivo y (a-b)/b+1=a/b.
    ○Si a<b entonces el padre es a/(b-a), pues a/(b-a) es mayor que cero, es racional positivo y [a/(b-a)]/[a/(b-a)+1]=a/b.
    ○Si a=b entonces el proceso termina.

    Ahora bien, en cada iteracion, si el proceso no termina (como deseamos), ocurriran dos cosas:
    ○El numerador disminuira en al menos una unidad, pues b es mayor o igual que 1. Esto puede ocurrir a lo sumo un numero a-1 de veces (pues el numerador debe ser mayor o igual que 1) antes de que el proceso termine.
    ○El denominador disminuira en al menos una unidad, pues a es mayor o igual que 1. Nuevamente, esto puede ocurrir a lo sumo un numero b-1 de veces antes de que el proceso termine.

    Asi, comenzando en un racional positivo distinto de 1, tenemos que como mucho el numero de generaciones, o de pasos para llegar a 1, estara acotado superiormente por a-1+b-1=a+b-2, o sea, un numero finito de generaciones.

    Luego, H, el conjunto de los descendientes, esta formado por todos los racionales positivos distintos de 1.

    Por ejemplo, si comienzo con 30/13 tengo la siguiente cadena generacional:
    30/13 → 17/13 → 4/13 → 4/9 → 4/5 → 4/1 → 3/1 → 2/1 → 1/1.
    Me parece que esta relacionado con el algoritmo de Euclides.

    Espero que sea satisfactoria.
    Saludos.

    Post a Reply

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.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Responder a David Cancelar respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.