DESAFÍO 40+1: SOLUCIÓN


(Escribe Rogelio:)
Antes de nada, muchas gracias a todos, empezando por Santi, por vuestro interes, esfuerzo y por comentar o mandar una solucion (o correccion!). De hecho voy a usar vuestras soluciones para ahorrarme un poco de curro. Han mandado codigos Python y Excel para quien los quiera!. Todas las soluciones estan basicamente bien, la diferencia esta en los detalles.
(Ah, mi teclado no tiene enyes ni acentos)
He recibido unas 9 respuestas, 2 de ellas corrigiendome el enunciado inicial (muchas gracias a Pardillano y Jesus). De las 7 restantes 4 o 5 estan perfectas y a 2 se les pasa aclarar que pasa con algun tipo de segmentos. Hay 2 tipos de soluciones:
1. Usando simetrias
2. Contando segmentos
Lo mas facil, visual y elegante es usando simetrias.  Las soluciones de Maito (su solucion 1) y Miquel son muy buenos ejemplos. JCMM tambien recurre a las simetrias sin esquemas. Las simetrias horizontal y vertical se usan siempre sin problema. Se puede recurrir a las simetrias respecto a las diagonales o no, pero al hacerlo no hay que olvidarse que tanto los segmentos superpuestos a las diagonales como los que las cortan perpendicularmente son la imagen de ellos mismos. Hay que emparejarlos o contarlos y ver que son multiplos de 8 (ver solucion de Miquel). Jabon, tu solucion fue la mas corta pero se te paso contar los segmentos perpendicularres a las diagonales.  De todas estas destaco las de Maito y Miquel por sus ilustraciones (las de Miquel muy navidenyas).
Un poco mas tecnico es recurrir a contar segmentos, ver las soluciones impecables de Javier D y Pedro Correa. JC tambien opto por este camino pero se olvido de las pendientes como x,y=(2,3) o (4,7), etc.
Nadie ha demostrado correctamente que pasa cuando N es impar (Javier D y Miquel lo intuyen sin demostrarlo). Veamos que el unico N impar con segmentos multiplos de 8 es N=3.
Prosigamos con el razonamiento de Javier D (ver pdf: SOLUCIÓN AL 40+1 DESAFÍO).
x,y (lo que el llama f,c) han de ser primos relativos. Esto se cumple si y solo si existen
dos numeros enteros a,b, tal que:
ax+by=1
Para todo par de primos relativos x,y tal que y>2, y>x, existe otro par de primos relativos
dado por: y-x, y
facilmente demostrable pues:
-a(y-x)+(b+a)y = ax+by= 1
Esta propiedad es como otra simetria mas del problema. Por ejemplo para el caso de la diagonal larga
(x,y)=(1,3) su simetrica “primo relativo” es (2,3). Tambien hay un caso que es su propia imagen en
esta simetria, este es (1,2).
Asi pues a partir de y=3 los primos relativos vienen siempre de 8 en 8.
Usando esta propiedad el numero de segmentos para N>4 se puede reescribir como:
(pulsar en la ecuación si no se ve completa)
donde el primer sumando comprende los pares (1,0), (0,1), (1,1) y (-1,1) y es multiplo de 8 siempre.
El segundo sumando comprende (2,1), (-2,1), (1,2) y (-1,2) y solo es multiplo de 8 para N par.
Por ultimo, el sumatorio comprende todos los casos con y>2. La funcion PR(x,y) es 1 si x,y
son primos relativos, en caso contrario PR(x,y) vale 0. Esta ultima contribucion es siempre multiplo de 8.
Aqui ya se puede concluir que solo existe un N impar con segmentos multiplos de 8, N=3
(otro enunciado interesante para el problema). Para simplificar la ecuacion y por cuestiones
didacticas se puede reemplazar el sumatorio sobre x por la funcion indicatriz de Euler (o phi), que nos da el numero de primos relativos  x,y tal que x<y, asi quedaria:
(pulsar en la ecuación si no se ve completa)
La funcion indicatriz de Euler es par para todo y>2.
Todas las formas de calculo me han llevado a que para N=50 hay 476160 segmentos
(como decian alfalfa, Javier D, Miquel y creo que Pedro (no corri el Excel)).
Tal y como decia alfalfa, en esta ecuacion se ve que cuando N es par y no es multiplo de 4 (por lo que
N-2 si es multiplo de 4) todos los terminos son multiplos de 16 (pues 4*(N-2) es multiplo de 16 y 8*(N-2y) con N par tambien es multiplo de 16). Este es otro enunciado interesante para el problema.
Me han gustado mucho todas las soluciones, como son pocas podeis echarles un ojo y elegir vosotros la mejor. Creo que la de Maito es particularmente clara, la de Miquel navidenya y las de Javier D y Pedro rigurosas y tecnicas. Por supuesto esto es solo mi opinion personal, y vosotros que pensais?
Ha sido todo un placer estar a este lado pero sera un descanso volver al lado de los “desafiados”!
Hasta el proximo.
Demostración desafío 40+1 maito
Gráfico-demostración Miquel Garriga:

20 comentarios

Archivado bajo OTROS

20 Respuestas a “DESAFÍO 40+1: SOLUCIÓN

  1. Pedro Correa

    Mola, Rogelio. Ha molado mucho, ¡¡en serio!!

  2. jabon

    Bien corregido por mi parte, como te he dicho antes. En la respuesta daba por sobreentendida la parte “fácil” digámoslo así (verticales, horizontales y diagonales a 45), para tratar sólamente el entramado de las diagonales largas.

  3. Ya lo creo, ¡qué rabia no haber podido dedicarle el tiempo necesario! muy bonito.

  4. Rogelio

    Hola,
    muchas gracias!
    Yo no veo las ecuaciones en la entrada, vosotros las veis?
    Santi, te las mando en pdf?

    • Yo sí las veo, mándalas de todas formas.

    • JC

      yo tampoco las veo, por ejemplo veo…
      y, asi quedaria:
      image.png

    • Anónimo

      Rogelio, ya veo las ecuaciones. Yo pensaba que el número de segmentos paralelos a (x,y) era (N-2x)(N-2y), y multiplicando por 4 los paralelos a (x,y) ó (y,x) ó (y,-x) ó (x,-y), es decir
      4(N-2x)(N-2y) que es múltiplo de 8
      Y el total de segmentos
      = 4 (N-2) (N-1) + ∑ 4(N-2x)(N-2y)
      y el sumatorio para todo x, y, x<y, coprimos, y ≤ (N/2) – 1

    • JC

      Rogelio, ya veo las ecuaciones. Yo pensaba que el número de segmentos paralelos a (x,y) era (N-2x)(N-2y), y multiplicando por 4 los paralelos a (x,y) ó (y,x) ó (y,-x) ó (x,-y), es decir
      4(N-2x)(N-2y) que es múltiplo de 8
      Y el total de segmentos
      = 4 (N-2) (N-1) + ∑ 4(N-2x)(N-2y)
      y el sumatorio para todo x, y, x<y, coprimos, y ≤ (N/2) – 1

      • Rogelio

        En efecto es asi, tu ecuacion da el mismo resultado que las de la entrada.
        Si es por el y <= N/2-1 en vez de y<=N/2, es lo mismo ya
        que el termino (N-2y) es cero para y=N/2.

        Como pones los simbolos? en html?

        • JC

          el símbolo (te refieres al sumatorio supongo) lo tenía en word, y he ha sido copiar-pegar
          Me refería a lo de cambiar (N-2x) por (N-y)

          • Rogelio

            eso ocurre al sumar los segmentos que pronienen de los 2 pares de primos relativos que existen para todo y>=3 (x,y e y-x,y), osea (N-2x)(N-2y) + (N-2y+2x)(N-2y) …

  5. jabon

    Rogelio, es correcta tu apreciación. Te envié la respuesta tal como me vino a la cabeza, y tal vez algo se haya sobreentendido. Intento detallarla un poco más, porque me parece que es sencilla.

    Como ya dije, quise plasmar la idea, pero tal vez no se entienda bien. Vendría a ser esto. (En el dibujo que ha
    hecho Miquel, se aprecia esto que voy a comentar).

    Considerando la retícula con segmentos sólo horizontales, verticales y diagonales a 45 grados, tendríamos los siguientes segmentos = 8 + (n-3) * 2 * 6 + (n-3) ^2 * 4

    Esos siempre serían múltiplo de 8 (incluso en los impares), fácilmente apreciable ( sólo debemos fijarnos en dos sumandos que se reducen a 4 * n * (n-3), en los que siempre se multiplica el 4 por un número par el “n” o el “n-3”, con ello se asegura el múltiplo de 8; y el 8 (sumando inicial), no hay problema.

    En cuanto al otro tipo de líneas (las diagonales largas), subdividimos el tablero en 8 partes a 45 grados (como si colocásemos una brújula en el centro exacto de la retícula).
    Los puntos en ellas incluidos son los mismos y a su vez son simétricos entre sí; por este motivo el número de segmentos que nacerán o terminarán en cada uno de ellos será el mismo, y por lo tanto habría que multiplicar por ocho (luego siempre serán múltiplo de ocho). Adelantar que entre dos puntos simétricos nunca puede haber un segmento (cosa que sí ocurre en la retícula impar, motivo por el que fallaría),
    En la retícula par, existirán unos puntos que coincidirán con una de las líneas que hemos utilizado para la subdivisión (las dibujadas a 45 grados). Diríamos que ni son de una ni son de otra zona, esto no nos debe importar porque el segmentos AB, es el mismo que el BA; dicho de otro modo, un segmento que acabe en esos puntos (recordemos, líneas divisorias a 45 grados), habrá empezado en otro punto. Si ese está en el interior de una de las ocho zonas, cumple con la premisa anterior; y si existiese un segmento que uniese un punto de una “intersección” (líneas subdivisorias a 45 grados) con otro de otra, comprobaríamos que por simetría se forman otro siete más.

  6. Rubén

    Yo le di unas cuantas vueltas al coco pero no las suficientes.. ; )

    Saludos

  7. JC

    Yo de las “diagonales largas” sólo vi las paralelas a (m,1) ó a (1,m) ó a (1,-m) ó a (m,-1), para cualquier m. Así que mi solución NO es correcta porque faltan más “diagonales largas”.
    Aunque no he visto todas las soluciones, entiendo que la “solución oficial” del desafío es la Solución1 de Maito, porque es sencilla, bonita, y no requiere conocimientos superiores a ESO.

  8. Maito

    Me alegro que os haya gustado mi primera propuesta, aunque con la segunda me quedé a medio camino.
    Creo que Rogelio ha puesto el listón muy alto para futuras propuestas.
    Enhorabuena.

  9. Pedro Correa

    Yo también daría el premio de la semana a Maito. Yo intenté resolverlo sin hacer demasiadas cuentas, creí que lo había conseguido… pero lo de las simetrías lo pasé por alto. Muy “visual”.

  10. jabon

    En efecto, las simetrías eran la clave. El de Maito está muy bien, y los dibujos de Miquel también hablan por sí sólos.

  11. alfalfa

    Muchas gracias Rogelio por el problema y por completar la solución.

  12. Divagante

    Este me ha venido grande. Muy bueno Rogelio.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s