Sean $n$ y $q$ enteros positivos. Un $(n,q)$ collar es un conjunto de $n$ puntos equiespaciados en una circunferencia, donde cada punto se ha coloreado con un color elegido entre $q$ posibles. Un $(n,q)$ collar es primo si no es posible dividirlo en arcos iguales entre sí (de longitud y coloración). Demuestra que la cantidad de $(n,q^n)$ collares primos es igual a $n$ veces el número de $(n^2,q)$ collares primos.
NOTA: Dos $(n,q)$ collares se consideran iguales si se puede obtener uno a partir del otro mediante una rotación.
martes, 28 de agosto de 2012
Suscribirse a:
Comentarios de la entrada (Atom)
2 comentarios:
Weeeeee, el 6 de la centro de 2004.
Aquí va un mini-resumen de las ideas de la solución:
-Vamos a imaginarnos que los collares con $n$ perlas son realmente collares de $n$ pelotas y los de $n^{2}$ perlas son de $n^{2}$ canicas. Entonces, a cada una de las $q^{n}$ pelotas posibles le asociamos una y sólo una secuencia de $n$ canicas (son $q^{n}$ pues cada canica puede ser de $q$ colores distintos) y vamos a decir que un collar de pelotas genera a uno de canicas si sustituimos las pelotas por las secuencias de canicas correspondientes y las mantenemos en forma de collar.
-Después, es necesario probar que si tenemos un collar de pelotas primo y lo cambiamos por su collar de canicas correspondiente, el último también es primo, también que si un collar de canicas es primo, si lo cambiamos por un collar de pelotas que lo genere el último también es primo.
-Al final sólo queda ver que por cada collar de canicas primo hay $n$ collares de pelotas primas que lo generan (por las rotaciones) y acabamos.
Una "biyección" mas ó menos
Publicar un comentario