tag:blogger.com,1999:blog-4730773743666324035.post5105518718453119766..comments2023-11-16T13:20:00.273-03:00Comments on Números y algo mas...: 1399 - Buenos vecinosClaudiohttp://www.blogger.com/profile/08887776875701773421noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-4730773743666324035.post-29396274131243276722015-07-02T09:31:31.396-03:002015-07-02T09:31:31.396-03:00Muchas gracias Carlos,
vicente iq.Muchas gracias Carlos,<br /><br />vicente iq.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-65237198852142968692015-07-01T22:38:08.640-03:002015-07-01T22:38:08.640-03:00En atención a la solicitud de Vicente aquí va mi r...En atención a la solicitud de Vicente aquí va mi rollototote.<br /><br />Generación de sarta S mínima de N signos tal que cada uno de ellos tenga como vecino al menos una vez a <br /><br />el resto de los signos (Entrada 1399, Claudio Meller)<br /><br />A. El algoritmo general para generar S es el siguiente<br /><br />1. Ordenar los N signos en un orden cualquiera Este orden se recorrerá ciclicamente hasta terminar.<br />2. Iniciar con el primero de los símbolos ordenados en el paso anterior.<br />3. Procediendo siempre en el mismo orden, elegir el primero de los signos restantes para formar un <br /><br />apareamiento no existente.<br />4. Finalizar cuando se hayan obtenido todos los apareamientos posible. En casi contrario regresar a 3.<br /><br />B. Comentarios al algoritmo<br /><br />a) Una sarta S completa y mínima tiene una longitud total L. La cantidad total de apareamientos a <br /><br />lograr es A=N(N-1)/2.<br /> <br />b) Al ir generando S, se dice que se produce un "cierre" en la sarta, cuando no se han obtenido todos <br /><br />los apareamientos posibles, y sin embargo ninguna elección de nunguno de los signos restantes produce <br /><br />un nuevo apareamiento.<br /><br />c) Cuando N es impar, el único "cierre" de S se produce al final de la sarta y éste siempre ocurre al <br /><br />colocar por (N+1)/2 vez el primer símbolo de la sarta. Todos los demás símbolos ocurren (N-1)/2 veces. <br /><br />En este caso L = N(N-1)/2+1. <br /><br />d) Cuando N es par, el primer cierre de S se produce cuando se han colocado L-N+2 signos quedando por <br /><br />colocar N-2 signos distintos. Entre esos N-2 signos pendientes de colocar se encuentran los (N-2)/2 <br /><br />apareamientos restantes. Estos apareamientos pendientes simplemente se añaden a la sarta previamente <br /><br />obtenida.Todos los símbolos ocurren N/2 veces. En este caso L = (N^2)/2.<br /><br />C. Soluciones<br /><br />Se usará el símbolo "|" para indicar la posición en el que ha ocurrido un "cierre" en la sarta <br /><br />generada.<br /><br />C1, Soluciones impares para N=3, 5, 7 y 9<br /><br />N=3, L=4, A=3, A->C<br />S=ABCA|<br /><br />N=5, L=11, N=10, A->E<br />S=ABCDEACEBDA|<br /><br />N=7, L=22, N=21, A->G<br />S=ABCDEFGACEGBDFADGCFBEA|<br /><br />N=9, L=37, A=36, A->I<br />S=ABCDEFGHIACEGIBDFHADGAEHBEICFBGCHDIFA|<br /><br />C2, Soluciones pares para N=4, 6, 8 y 10<br /><br />N=4, L=8, A=6, A->D<br />S=ABCDAC|BD|<br /><br />N=6, L=18, A=15, A->F<br />S=ABCDEFACEADFBD|EB|CF|<br /><br />N=8, L=32, A=28, A->H<br />S=ABCDEFGHACEGADFHBDGBEHCFAE|BF|CG|HD|<br /><br />N=10, L=50, A=45, A->J<br />S=ABCDEFGHIJACEGIADFHJBDGJCFIBEHAEIGCAFJDHBF|GB|CH|ID|EJ|<br /><br />D. Comentarios finales<br /><br />D1. Sean A y P prefijos y sufijos válidos con respecto a S. A y P son válidos si estan compuestos <br /><br />exclusivamente por símbolos pertenecientes a S. Si S es una solución, entonces AS, SP y ASP son <br /><br />soluciones válidas también.<br /><br />D2. Cualquier subsarta entre dos elementos iguales y consecutivos en una sarta, pueden rotarse 180° y <br /><br />la sarta no se altera en cuanto a los apareamientos contenidos.carlos riverahttp://www.primepuzzles.netnoreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-73985920901055668742015-07-01T06:16:18.225-03:002015-07-01T06:16:18.225-03:00Estoy preparando un artículo. Pero más q una demos...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.Carlos Riverahttps://www.blogger.com/profile/15430102978026793984noreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-90295905275605144292015-06-30T17:02:48.877-03:002015-06-30T17:02:48.877-03:00Interesante el tema.
Se pueden plantear muchas va...Interesante el tema. <br />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.<br />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.<br />etc.<br /><br />Vicente iq.<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-81933888109766098352015-06-30T12:51:36.866-03:002015-06-30T12:51:36.866-03:00Carlos, ¿es posible tener acceso a la demostración...Carlos, ¿es posible tener acceso a la demostración de esos resultados?<br /><br />vicente iq.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-55151779924031580442015-06-30T09:41:55.685-03:002015-06-30T09:41:55.685-03:00(N^2)/2 y N(N-1)/2+1 dan el largo de la sarta mini...(N^2)/2 y N(N-1)/2+1 dan el largo de la sarta minima si N es par o impar, respectivamente.Carlos Riverahttps://www.blogger.com/profile/15430102978026793984noreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-32839756703413766612015-06-29T13:59:16.734-03:002015-06-29T13:59:16.734-03:00Gracias. Otros resultados mas tarde.Gracias. Otros resultados mas tarde.Carlos Riverahttps://www.blogger.com/profile/15430102978026793984noreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-63343434492041756422015-06-29T11:13:20.406-03:002015-06-29T11:13:20.406-03:00Si Carlos, no logro hacerlo con menos caracteresSi Carlos, no logro hacerlo con menos caracteresClaudiohttps://www.blogger.com/profile/08887776875701773421noreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-44841797837718529742015-06-29T00:20:45.155-03:002015-06-29T00:20:45.155-03:00Claudio, mis mínimos para N 6 y 7 son 18 y 22. Qué...Claudio, mis mínimos para N 6 y 7 son 18 y 22. Qué opinas?Carlos Riverahttps://www.blogger.com/profile/15430102978026793984noreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-90478370919085806232015-06-27T19:45:41.138-03:002015-06-27T19:45:41.138-03:00He modificado mi técnica y parece que 11 es un mín...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...carlos riverahttp://www.primepuzzles.netnoreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-60205851912825035302015-06-27T18:59:50.469-03:002015-06-27T18:59:50.469-03:00Tienes razón. Lo cual quiere decir que mi técnica ...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.<br /> carlos riverahttp://www.primepuzzles.netnoreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-37941354520658130122015-06-27T15:19:33.410-03:002015-06-27T15:19:33.410-03:00Carlos se puede hacer con 11 signos.
ABCADCEBDEACarlos se puede hacer con 11 signos.<br />ABCADCEBDEAClaudiohttps://www.blogger.com/profile/08887776875701773421noreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-2072893387692354242015-06-27T15:19:08.457-03:002015-06-27T15:19:08.457-03:00Carlos se puede hacer con 11 signos.
ABCADCEBDEACarlos se puede hacer con 11 signos.<br />ABCADCEBDEAClaudiohttps://www.blogger.com/profile/08887776875701773421noreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-69511356446785498832015-06-27T11:33:23.458-03:002015-06-27T11:33:23.458-03:00Para N=5 creo que la sarta más corta es de 14 sign...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.carlos riverahttp://www.primepuzzles.netnoreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-80734166189532780572015-06-26T21:22:12.978-03:002015-06-26T21:22:12.978-03:00Observaciones:
1) El enunciado NO indica que los ...Observaciones:<br /><br />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.<br /><br />2) En realidad este problema no es relativo a números, sino a sartas lineales de signos con cierta propiedad de posicionamiento entre ellos.<br /><br />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 carlos riverahttp://www.primepuzzles.netnoreply@blogger.comtag:blogger.com,1999:blog-4730773743666324035.post-40587563729316385702015-06-25T10:01:17.545-03:002015-06-25T10:01:17.545-03:00Una propiedad de estos números es la siguiente:
si...Una propiedad de estos números es la siguiente:<br />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:<br />1021<br />2102<br />0210<br /><br />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.<br /><br />Vicente iq.<br /><br />Anonymousnoreply@blogger.com