Autor Tema: Cantidad de soluciones salvo isomorfismo

0 Usuarios y 1 Visitante están viendo este tema.

23 Agosto, 2019, 06:45 pm
Leído 1219 veces

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Se tiene una estrella como la de la figura:



Los puntos están etiquetados. A cada uno, se le asigna un valor entre 1 y 12. La suma de los valores de cada segmento tiene que ser 26, y no puede haber valores repetidos (o sea, a cada nodo le corresponde un número distinto).

¿Cuántas soluciones diferentes hay a este problema (considerando dos iguales si es posible reetiquetar los nodos para que sean idénticas)?
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

23 Agosto, 2019, 11:07 pm
Respuesta #1

martiniano

  • Héroe
  • Mensajes: 1,223
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola.

Una pregunta: ¿se trata de un problema cuya solución es asequible con los recursos propios de un humano, o se puede usar la fuerza bruta de los ordenadores para responder?

24 Agosto, 2019, 06:09 am
Respuesta #2

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Una pregunta: ¿se trata de un problema cuya solución es asequible con los recursos propios de un humano, o se puede usar la fuerza bruta de los ordenadores para responder?

Se puede usar un programa. Por ejemplo, éste resuelve el problema de hallar soluciones en Prolog:

Código: [Seleccionar]
:-use_module(library(clpfd)).

estrella([X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12]) :-
    Vars = [X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12],
    Vars ins 1..12,
    all_different(Vars),
    X2+X3+X4+X5 #= 26,
    X2+X6+X9+X12 #= 26,
    X5+X7+X10+X12 #= 26,
    X1+X3+X6+X8 #= 26,
    X1+X4+X7+X11 #= 26,
    X8+X9+X10+X11 #= 26,
    label(Vars).

Se puede probar interactivamente acá. Con la query

Código: [Seleccionar]
?- estrella([X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12]).

arroja las soluciones y con

Código: [Seleccionar]
?- aggregate_all(count, (estrella([X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12])), Count).

las cuenta (son 960 en total). El problema es que, de esas 960 totales que hay, me interesaba saber cuáles eran realmente "únicas" en el sentido de que no se obtiene una, por ejemplo, mediante rotación de otra.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

24 Agosto, 2019, 06:32 am
Respuesta #3

martiniano

  • Héroe
  • Mensajes: 1,223
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola.

Pues entonces piensa que por cada solución salvo isomorfismos tienes 6 simetrías y dos rotaciones. Entonces, al conocer las soluciones totales, puedes hacer \( \displaystyle\frac{960}{6\cdot{2 }}=80 \)

Un saludo.

24 Agosto, 2019, 10:44 am
Respuesta #4

robinlambada

  • Moderador Global
  • Mensajes: 3,374
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola yo encuentro 6 simetrías y 6 rotaciones. A bote pronto me parecen todas distintas, pero 960 no es divisible entre 36.
Desde el móvil no puedo dibujar las simetrías y rotaciones.
Debe pasar que alguna rotación coincida con una simetría, pero no lo veo.
La estrella tiene 6 puntas, si se gira la estrella 6 veces desde el centro \( \pi /3 \) se llegará la misma posición. Por ello hay 6 rotaciones donde no permanece invariante ninguna variable.
En el hexágono interior veo 6 simetrías respecto a las rectas que unen vértices opuestos. Y estos vértices si permanecen invariantes tras la simetría. Por ello no pueden coincidir con alguna rotación.
¿Dónde está el error?
Posiblemente halla más soluciones, o conté mal.

Saludos.
P.d.: Falta un signo de interrogación en mi pregunta, desde mi móvil no lo tengo en el teclado, si alguien lo corrige , le estaré agradecido.
Envejecer es como escalar una gran montaña: mientras se sube las fuerzas disminuyen, pero la mirada es más libre, la vista más amplia y serena.

La verdadera juventud una vez alcanzada, nunca se pierde.

24 Agosto, 2019, 10:57 am
Respuesta #5

robinlambada

  • Moderador Global
  • Mensajes: 3,374
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
De hecho acabo de encontrar otras 6 simetrías más que son las 6 rectas que unen las puntas opuestas de la estrella. Me saldrían por cada solución 6×6×6=216 simetrías.
Saludos.
P.d.: pero de esta s 6 últimas posiblemente puedan ser combinación de rotaciones más simetrías de los ejes que pasan por los vértices interiores. (Hexágono).
Aunque ahora debo irme lo miraré más tarde).
Envejecer es como escalar una gran montaña: mientras se sube las fuerzas disminuyen, pero la mirada es más libre, la vista más amplia y serena.

La verdadera juventud una vez alcanzada, nunca se pierde.

24 Agosto, 2019, 11:57 am
Respuesta #6

martiniano

  • Héroe
  • Mensajes: 1,223
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola robinlambada.

El razonamiento de mi anterior mensaje no es correcto. Sin embargo, y de casualidad, mantengo el resultado al que he llegado. Simetrías solo me salen seis. Las tres cuyos ejes pasan por los vértices del hexágono y las tres cuyos ejes pasan por los vértices de la estrella. Giros, efectivamente, hay seis.

De todas formas, creo que lo que entra aquí en juego es el grupo diedro del hexágono, \( D_6 \), cuyo cardinal es 12, que es el número de isomorfismos que se puede aplicar a una de las soluciones para obtener sus isomorfas.

Venga, que ya lo tenemos. Un saludo  ;)

24 Agosto, 2019, 07:48 pm
Respuesta #7

robinlambada

  • Moderador Global
  • Mensajes: 3,374
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola robinlambada.

El razonamiento de mi anterior mensaje no es correcto. Sin embargo, y de casualidad, mantengo el resultado al que he llegado. Simetrías solo me salen seis. Las tres cuyos ejes pasan por los vértices del hexágono y las tres cuyos ejes pasan por los vértices de la estrella. Giros, efectivamente, hay seis.

De todas formas, creo que lo que entra aquí en juego es el grupo diedro del hexágono, \( D_6 \), cuyo cardinal es 12, que es el número de isomorfismos que se puede aplicar a una de las soluciones para obtener sus isomorfas.

Venga, que ya lo tenemos. Un saludo  ;)
Claro,que burro soy, no he contado que solo hay una recta por cada dos vértices. Entonces son 6 simetrías. No me he parado a pensarlo suficientemente. Pero como dices se deben combinar simetrías y giros y se reduzca el número.
Saludos.
Envejecer es como escalar una gran montaña: mientras se sube las fuerzas disminuyen, pero la mirada es más libre, la vista más amplia y serena.

La verdadera juventud una vez alcanzada, nunca se pierde.

24 Agosto, 2019, 08:30 pm
Respuesta #8

martiniano

  • Héroe
  • Mensajes: 1,223
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Si. Se reduce a 12. Piensa como si tuvieses un hexágono regular (o la estrella del problema, da lo mismo) recortado en papel con los vértices numerados. 12 son las diferentes maneras como lo podrías colocar con los vértices sobre seis puntos fijos de una mesa.

Saludos.

24 Agosto, 2019, 10:57 pm
Respuesta #9

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias a los dos por su aporte. Tengo que reflexionar bien sobre todos los movimientos para convencerme de que son 12  :D

Saludos.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

24 Agosto, 2019, 11:50 pm
Respuesta #10

martiniano

  • Héroe
  • Mensajes: 1,223
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola.

Si no has oído hablar de los grupos diedros lo puedes entender pensando en li del hexágono (o estrella) de papel y los puntos de la mesa.

El hexágono sólo se puede colocar de seis maneras con una de las caras hacia arriba y de otras seis con la otra cara.

¿Cómo lo ves?