lunes, 22 de junio de 2015

1399 - Buenos vecinos

Definamos como números con buenos vecinos a aquellos números que en su composición participan N dígitos distintos, tal que cada dígito participante es al menos vecino una vez de todos los otros dígitos.

Evidentemente todos los números que tienen solo dos dígitos distintos tiene buenos vecinos.

Para tres dígitos distintos tenemos por ejemplo :
1021 (el menor posible y además primo)
Tiene buenos vecinos porque el 0 está al menos una vez al lado del 1 y del 2, y lo mismo ocurre para el 1 y el 2.

Para cuatro dígitos distintos:
10203123  (¿Es el menor?)
24123413 que es primo. (¿Es el menor?)

La idea entonces es encontrar para N dígitos distintos (N=4 a N=10), el menor número con buenos vecinos que además sea primo.


Si lo quieres compartir o guardar
Share/Bookmark

16 comentarios:

  1. Una propiedad de estos números es la siguiente:
    si rotamos cíclicamente cada dígito desde 0 hasta n, el número resultante sigue siendo buen vecino. En el ejemplo de Claudio del 1021, rotando cada dígito desde 0 hasta 2 podemos obtener los siguientes:
    1021
    2102
    0210

    De esta propiedad se deduce que dada una solución cualquiera siempre podremos encontrar otra que comience por 1. Por lo que el 24123413 no es el menor porque podemos rotar cada dígito hacia atrás una posición obteniendo otro resultado válido, el 13412342.

    Vicente iq.

    ResponderEliminar
  2. Observaciones:

    1) El enunciado NO indica que los N dígitos deben ser los primeros N dígitos sino sólo que haya N dígitos distintos.

    2) En realidad este problema no es relativo a números, sino a sartas lineales de signos con cierta propiedad de posicionamiento entre ellos.

    Al mezclar esto con los números y en especial con los números primos yo encuentro que para N=4, el menor primo es 10307137

    ResponderEliminar
  3. Para N=5 creo que la sarta más corta es de 14 signos totales. Si esto es así, el primo menor es éste: 10210427047147.

    ResponderEliminar
    Respuestas
    1. Carlos se puede hacer con 11 signos.
      ABCADCEBDEA

      Eliminar
    2. Carlos se puede hacer con 11 signos.
      ABCADCEBDEA

      Eliminar
  4. Tienes razón. Lo cual quiere decir que mi técnica para producir una sarta de longitud mínima aún requiere refinamiento. Ahora bien usando tu sarta, el primo menor es este: 10213250351.

    ResponderEliminar
  5. He modificado mi técnica y parece que 11 es un mínimo real para N=5. Aunque yo obtengo esta sarta ABCADBECDEA, que es un poco distinta que la tuya dado que se giró la subsarta BEC. Sin embargo NO produce un primo menor que el ya obtenido con tu sarta. Estas rotaciones de subsartas están interesantes...

    ResponderEliminar
  6. Claudio, mis mínimos para N 6 y 7 son 18 y 22. Qué opinas?

    ResponderEliminar
    Respuestas
    1. Si Carlos, no logro hacerlo con menos caracteres

      Eliminar
    2. (N^2)/2 y N(N-1)/2+1 dan el largo de la sarta minima si N es par o impar, respectivamente.

      Eliminar
    3. Carlos, ¿es posible tener acceso a la demostración de esos resultados?

      vicente iq.

      Eliminar
    4. Estoy preparando un artículo. Pero más q una demostración de las fórmulas, lo q tengo es una ejemplificación de los resultados obtenidos mediante el algoritmo empleado (greddy o voraz) y que yo sugiero y supongo siempre genera solucion y que esa solución es mínima. Si todo eso es cierto, las formulas se obtienen por generalización de esos resultados, más bien que pir deducción. En un par de días publico o envio esto.

      Eliminar
  7. Interesante el tema.
    Se pueden plantear muchas variantes como por ejemplo utilizar sartas, como las llama Carlos, en forma de collar; o sea, el primer dígito unido con el último.
    Se puede extender a 2 dimensiones para disponer en un cuadriculado los números de forma que se consideren vecinos los que estén al lado de un dígito dado en horizontal o vertical.
    etc.

    Vicente iq.

    ResponderEliminar
  8. En atención a la solicitud de Vicente aquí va mi rollototote.

    Generación de sarta S mínima de N signos tal que cada uno de ellos tenga como vecino al menos una vez a

    el resto de los signos (Entrada 1399, Claudio Meller)

    A. El algoritmo general para generar S es el siguiente

    1. Ordenar los N signos en un orden cualquiera Este orden se recorrerá ciclicamente hasta terminar.
    2. Iniciar con el primero de los símbolos ordenados en el paso anterior.
    3. Procediendo siempre en el mismo orden, elegir el primero de los signos restantes para formar un

    apareamiento no existente.
    4. Finalizar cuando se hayan obtenido todos los apareamientos posible. En casi contrario regresar a 3.

    B. Comentarios al algoritmo

    a) Una sarta S completa y mínima tiene una longitud total L. La cantidad total de apareamientos a

    lograr es A=N(N-1)/2.

    b) Al ir generando S, se dice que se produce un "cierre" en la sarta, cuando no se han obtenido todos

    los apareamientos posibles, y sin embargo ninguna elección de nunguno de los signos restantes produce

    un nuevo apareamiento.

    c) Cuando N es impar, el único "cierre" de S se produce al final de la sarta y éste siempre ocurre al

    colocar por (N+1)/2 vez el primer símbolo de la sarta. Todos los demás símbolos ocurren (N-1)/2 veces.

    En este caso L = N(N-1)/2+1.

    d) Cuando N es par, el primer cierre de S se produce cuando se han colocado L-N+2 signos quedando por

    colocar N-2 signos distintos. Entre esos N-2 signos pendientes de colocar se encuentran los (N-2)/2

    apareamientos restantes. Estos apareamientos pendientes simplemente se añaden a la sarta previamente

    obtenida.Todos los símbolos ocurren N/2 veces. En este caso L = (N^2)/2.

    C. Soluciones

    Se usará el símbolo "|" para indicar la posición en el que ha ocurrido un "cierre" en la sarta

    generada.

    C1, Soluciones impares para N=3, 5, 7 y 9

    N=3, L=4, A=3, A->C
    S=ABCA|

    N=5, L=11, N=10, A->E
    S=ABCDEACEBDA|

    N=7, L=22, N=21, A->G
    S=ABCDEFGACEGBDFADGCFBEA|

    N=9, L=37, A=36, A->I
    S=ABCDEFGHIACEGIBDFHADGAEHBEICFBGCHDIFA|

    C2, Soluciones pares para N=4, 6, 8 y 10

    N=4, L=8, A=6, A->D
    S=ABCDAC|BD|

    N=6, L=18, A=15, A->F
    S=ABCDEFACEADFBD|EB|CF|

    N=8, L=32, A=28, A->H
    S=ABCDEFGHACEGADFHBDGBEHCFAE|BF|CG|HD|

    N=10, L=50, A=45, A->J
    S=ABCDEFGHIJACEGIADFHJBDGJCFIBEHAEIGCAFJDHBF|GB|CH|ID|EJ|

    D. Comentarios finales

    D1. Sean A y P prefijos y sufijos válidos con respecto a S. A y P son válidos si estan compuestos

    exclusivamente por símbolos pertenecientes a S. Si S es una solución, entonces AS, SP y ASP son

    soluciones válidas también.

    D2. Cualquier subsarta entre dos elementos iguales y consecutivos en una sarta, pueden rotarse 180° y

    la sarta no se altera en cuanto a los apareamientos contenidos.

    ResponderEliminar
    Respuestas
    1. Muchas gracias Carlos,

      vicente iq.

      Eliminar

Si quieres deja un comentario, si la entrada tiene mas de 15 dias deberás esperar a que la autorice y por favor si no tienes gmail deja tu nombre si no quedas como anónimo. Gracias!