POLÍGONOS ESTRELLADOS
Bloque: Taller de matemáticas
 
1.-Definición de polígono estrellado
El polígono estrellado (M, N) es la figura geométrica que se obtiene mediante el siguiente algoritmo:
    PASO 1: Se construye un polígono padre de N lados.
    PASO 2: Se toma un vértice cualquiera y se le etiqueta (es decir, se le marca) como 'visitado'.
    PASO 3: Se traza un segmento desde el último vértice visitado hasta otro que se obtiene saltando M vértices en el sentido contrario a las agujas del reloj. Se etiqueta el vértice al que llegamos como 'visitado'
    PASO 4: Se repite el PASO 3 hasta que el segmento que tracemos termine en un vértice ya visitado.
Un algoritmo es un conjunto de instrucciones precisas cuya realización acaba en algún momento, es decir, no continúa indefinidamente. Por precisas entendemos que en todo momento debemos (nosotros o la máquina que interpreta las instrucciones) saber qué hay que hacer. Para que acabe, todo algoritmo cuenta con una condición de parada, en nuestro caso: hasta que el segmento que tracemos termine en un vértice ya visitado.

Otra cuestión importante en un algoritmo es su corrección entendiendo por tal, que cuando acaba de ejecutarse, el resultado obtenido es lo que deseábamos.

Para empezar, en la siguiente  ventana puedes obtener distintos polígonos estrellados. 
1.-Prueba distintas combinaciones de los parámetros M y N, algunas combinaciones pueden ser M=5 y N=7, M=3 y N=17, M=9 y N=17, etc. 

2.-Da un valor a N fijo (no muy grande), deja pulsada la flecha de M y  verás una especie de película a cámara rápida que si te fijas se repite todo el rato la misma aunque M vaya cambiando. 

Los dos números M y N sirven para distinguir unos polígonos de otros, y realmente son los únicos datos necesarios para la construcción. El valor de N corresponde al número de lados del polígono padre (gris) dentro del cual construimos el polígono estrellado. El valor de M corresponde al salto que damos para pasar de un vértice a otro del polígono padre. 
3.-Describe un algoritmo para freír un huevo (inténtalo), o para ordenar alfabéticamente los alumnos de una clase (describir este algoritmo te puede costar algo más). En ambos casos observa como las cuestiones relativas a la precisión, la condición de parada y la corrección aparecen.
No sería  posible describir con un algoritmo cómo crear  una poesía (¿o sí?).
2. CONSTRUCCIÓN DEL POLÍGONO ESTRELLADO
La siguiente ventana reproduce el algoritmo constructivo que hemos descrito.
Al realizar distintas animaciones y observar cómo se generan los polígonos quizá parezca que nuestro algoritmo funciona 'bien'. Es bastante claro que las instrucciones de nuestro algoritmo son muy precisas,  pero podemos preguntarnos por los otros dos aspectos de un algoritmo:
1.-sobre la condición de parada: ¿Acabará en algún momento?.

La respuesta  seguramente la puedas dar tú y es que al ser los vértices del polígono padre un número finito,  llegará un momento en que el segmento que tracemos acabará en un vértice ya visitado anteriormente. 

Esta forma de razonar es frecuente en matemáticas y se la denomina a veces el 'Principio del Palomar' y dice que 'si en un palomar hay más palomas que agujeros por donde entrar al palomar, por alguno de lo agujeros entrarán al menos dos palomas'. Intenta razonar usando este principio por qué en una reunión de  366 personas al menos dos cumplen los años el mismo día .

2. -Sobre la corrección: ¿El resultado obtenido, cuando acabe, será siempre un polígono estrellado?

Esta pregunta  es más difícil de responder pero en primer lugar sería bueno que te convencieras de la necesidad de plantearla  porque ¿y si existieran dos números (N, M) de forma que al hacer la construcción no obtuviéramos un polígono estrellado?. Veamos algunos problemas que podrían plantearse:

  1. Si tomas en la ventana los pares  (2,8) y  (3,15) verás que  no se obtiene lo que entendemos en general por 'estrellado' y es que los lados se deben de cortar y lo que se obtiene es un polígono 'normal'.
  2. Si tomas en la ventana los pares  (6,15) y (2,5) obtenemos  el mismo polígono estrellado pero en el primer caso no se visitan todos los vértices del polígono padre. Este defecto, que es un mal menor, trataremos de evitarlo en nuestro algoritmo, es decir, no habrá ya dos nombres para la misma estrella y que elegiremos aquella en la que se visitan todos los vértices del polígono padre.
  3. Lo que si parece menos probable es que haya alguna combinación (M,N) donde no se obtenga ningún tipo de polígono, esto último supondría que no se acaba el algoritmo en el vértice en que se empezó, esta cuestión tan sencilla de plantear no tiene una respuesta inmediata.

La respuesta a los dos primeros problemas está muy relacionada. La anomalía que se presenta en el primer caso está bastante clara: en los pares (2,8) y  (3,15) el valor del salto M divide a N el número de lados del polígono, es este caso cuando damos la primera vuelta volvemos al vértice de partida habiendo dado N/M saltos que son los lados del polígono regular (no estrellado) que obtenemos. No se puede formar una estrella porque al dar sólo una vuelta los lados no tienen ocasión de cortarse. Tendremos pues que pedir al menos en nuestro algoritmo que M no divida a N.
En el segundo caso M ya no divide N pero al introducir  los valores  (6,15) y (2,5)  o  (6,14)  y (3,7) en la primera ventana, se obtiene exactamente la misma estrella . Es fácil darse cuenta de que  (6,15) = (3·2,3·5) y de que (6,14) = (2·3,2·7), es decir  en los dos casos M y N tienen un divisor común. Tenemos que pedir pues que (M, N) no tengan divisores comunes, es decir el máximo común divisor sea 1, que podemos escribir de forma simplificada MCD (M,N)=1. Cuando esto ocurre se dice  que M y N son primos entre sí. Si queremos a partir de un par de valores (M,N) obtener el par de números primos entre sí que genera la misma estrella, necesitaremos dividir por el máximo común divisor. Puedes recordar cómo calcularlo en este enlace MCD.  Justificar matemáticamente que cuando  MCD (M,N)=1 se visitan todos los vértices, como hemos intuido experimentándolo, es complicado y se escapa del objetivo de esta unidad.


Nos falta responder al último problema que habíamos planteado. Al aplicar el algoritmo sabemos que en algún momento llegamos por primera vez a un vértice V que ya habíamos visitado (por el principio del palomar) y el algoritmo se para. Para llegar a este vértice habremos necesitado más de una vuelta alrededor del polígono padre, luego a este vértice se puede llegar la primera vez que se visita dando un número de saltos, desde que empezamos a saltar, que podemos llamar k y también, la segunda vez, dando un número se saltos k' (k' será mayor que N para que demos más de una vuelta). Es claro que k<k'. Esto quiere decir que si estoy en V y doy k-k' saltos vuelvo a V, pero esto tiene que ocurrir no sólo para V sino para todo vértice que haya sido visitado alguna vez porque los vértices están colocados simétricamente alrededor de la circunferencia según el polígono padre. Así  que aplicando lo anterior al vértice del que parte el algoritmo en el paso 2:

PASO 2 Se toma un vértice cualquiera y se le etiqueta como 'visitado'.

también le ocurre, por lo tanto el primer vértice visitado dos veces es él ya que los demás se encuentran situados después de él.
       
           
  Agustín Muñoz Núñez
 
© Ministerio de Educación y Ciencia. Año 2001