Mientras hacía tiempo en un bar, me volvió a atacar una de mis
típicas compulsiones numerológicas y me puse a garabatear números en
una servilleta de papel.
Se me ocurrió lo siguiente:
Elegir un grupo de n números (de 1 en adelante) de forma tal que las diferencias entre cualquier par de números sean todas diferentes. La idea es que el mayor número del conjunto sea el menor posible.
Por ejemplo, para n=3 podrímos elegir (1, 2, 4) y las diferencias serían 1,2 y 3, todas distintas.
Para n=4 tenemos (1,2,4,8) y las diferencias son 1,2,4,3,6,7, también todas distintas.
Podríamos pensar que la serie de las potencias de 2 es la solución al problema.
Efectivamente, para n=5 el conjunto (1,2,4,8,16) tiene todas sus diferencias diferentes, pero es mejor el conjunto (1,2,4,8,13) Pueden comprobar que las 10 diferencias son todas distintas.
Lo dicho.
Encuentren los mejores conjuntos para n=6, 7, 8, 9, 10 (y aquí me cansé, pero ustedes pueden seguir)
Encuentren, si es posible, un método que permita construir estos conjuntos.
Update
El lector Arnoldo Briceño (gracias) nos hace descubrir que este tema en realidad ya es conocido bajo el nombre de Regla de Golomb.
El tema resultó ser mas profundo de lo que pensaba y el método que
habíamos propuesto no llega a producir los mejores conjuntos.
Para n=4 habíamos dicho (1,2,4,8) pero es mejor (1,2,5,7)
Para n=5 teníamos (1,2,4,8,13) pero es superada por (1,2,5,10,12) o por (1,3,8,9,12)
En la página de la wikipedia se muestran las reglas óptimas hasta n=25
Estas son complicadas de encontrar y fueron halladas con métodos de
procesamiento distribuido al estilo del programa seti@home.
Suscribirse a:
Enviar comentarios (Atom)
2 comentarios:
11 comentarios originalmente en “Diferencias”
oloman Dijo:
junio 3, 2006 a 5:06 am e
1, 2, 4, 8, 13, 21, 31, 45 y 66 para una serie de 9. Más adelante el método…cuando vuelva de viaje.
Elessar Dijo:
junio 3, 2006 a 2:12 pm e
(Snif, snif, no me quiere recordar… tengo que poner mi nombre cada vez… aunque tenga las cookies habilitadas…)
Hacer sí es trabajo… quizás lo haría, pero acabo de presentarme para participar en las olimpíadas iberoamericanas de física para liceo (tratando de clasificar para uruguay) y estoy sumamente cansado.
City Dijo:
junio 5, 2006 a 4:54 am e
Un posible metodo es el siguiente:
Supongamos que R3 es el conjunto de restas entre un conjunto de 3 numeros. Podemos suponer tambien que R3 mapea la mayor cantidad de numeros seguidos pe: (1,2,4) R3=(1,2,3). A partir de aquí si añadimos al conjunto (1,2,4) qualquier numero, pe el 8 ,el R4 no podra mapear los numeros del 1 hasta el 6, R4={1,2,3,4,6,7}. Fijaros que ahora nos falta el 5 en el conjunto de restas. Pues el siguiente numero que añadamos a la solución deberia ser aquel cuyas restas al menos contengar el 5. Una posibilidad es sumar el 5 a la ultima solucion (la resta mas pequeña posible con el siguiente numero). Si seguimos este metodo solo tenemos que ir observando los numeros sin mapear y estos iran dando soluciones (en el caso de muchos numeros sin mapear escoger el mas pequeño de ellos).
El único punto que dudo, es si al utilizar el resultado de un grupo mas pequeño conseguimos un mejor mapeado que tratar cada solución independiente, aunque con grupos pequeños parezca que si funciona.
santiago Dijo:
junio 5, 2006 a 7:40 pm e
No sé si mapear tenga algún significado demasiado específico (para eso de “mejor mapeado”), pero si no, por lo que entendí sí funciona. La suma de la “menor resta que no está” con el mayor del conjunto es el primer número que cumple la premisa para formar el conjunto de siguiente orden, a partir del anterior: todas sus restas con el resto no están porque son las que ya se tenían recorridas (por lo tanto nuevas).
Además, si se suma “la primera que no está” con un número que no sea el mayor del conjunto, la resta entre el resultado y este ultimo será menor que “la primera” con lo que ya estará incluida.
Y si se toma una resta que no esté mayor a la primera, igual funciona pero se hace todo más grande.
Ya, qué enredos, a la próxima uso numeritos
Markelo Dijo:
junio 6, 2006 a 12:04 am e
Bien. Ese es el método que usé yo. Sin embargo…
Siempre me molestan los métodos “recursivos” en donde para averiguar el conjunto de n elementos, primero hace falta conocer el de n-1.
¿Habrá algún método no recursivo que permita obtener, por ejemplo, un conjunto de 88 números sin necesidad de calcular los 87 anteriores?
Ni idea.
Markelo Dijo:
junio 6, 2006 a 12:06 am e
Elessar: Ni idea. Será que el blog tiene memoria selectiva :-)
No, en serio. No se por qué puede ser. ¿Seguro que tenés habilitadas las “galletas” y tildas el “remember personal info”?
¿A alguno más le pasa?
El Bengador Hanonimo Dijo:
junio 6, 2006 a 10:49 am e
a mi me pasa, cambio los datos y no hay caso, vuelven estos
Arnoldo Briceño Dijo:
junio 6, 2006 a 3:22 pm e
No tiene nada que ver esto con las reglas de golomb????
santiago Dijo:
junio 6, 2006 a 10:08 pm e
A mi me pasó. Basta quitar las cookies de este sitio y luego dejar que se vuelvan a poner con los datos nuevos
Markelo Dijo:
junio 7, 2006 a 12:39 am e
Gracias Arnoldo:
Tienes toda la razón. Ya me imaginaba yo que el tema debió haber sido tratado anteriormente.
Ya tengo sueño. Se los dejo para que lo busquen, pero les aviso que estamos equivocados y que hay soluciones mejores que las propuestas.
para n=4 dijimos (1,2,4,8) y es mejor (1,2,5,7)
De aquí figúrense que todo lo que dijimos sigue mal.
Markelo Dijo:
junio 7, 2006 a 12:40 am e
Ah: Prueben lo que dice Santiago de las cookies.
Publicar un comentario