| Click here to view this page in English. |
Dados de Sicherman
Enviado por Chrix de Bloomington, Minnesota, 2 de julio de 2000.
Respuesta original y este artículo por Allen Stenger.
He aquí un par de problemas que me fueron dadas por un amigo...
Cuando se tira un par estándar de dados de seis caras,
hay 11 resultados posibles,
con una cierta probabilidad de ocurrencia para cada posible resultado
(la probabilidad de obtener un total de 8 es 5/36, por ejemplo).
Esto se llama la distribución de probabilidad.
Ahora bien, resulta que usted puede tomar dos 6-dados y poner en las caras
otros números enteros positivos,
de tal manera que la distribución de probabilidad de el sumo es la misma.
Es decir, puede escribir una serie completamente diferente de números
en los dados, pero todavía tienen la misma probabilidad de tirar cualquier
total, como si los dados eran regulares. Resulta que la única manera de hacer esto
es poner 1, 2, 2, 3, 3, 4 en un dado y 1, 3, 4, 5, 6, 8 en el otro
(me permite repeticiones de números, y si lo piensas bien, eso debe ocurrir).
Los dos problemas que tengo se refieren a parejas de dados con más de 6 caras.
El primer problema que se puede hacer por ensayo y error, pero el segundo
ciertamente no se puede hacer así, y sería necesario un método avanzado de
resolverlo.
- Hallar los dos métodos adicionales de poner números en una pareja de dados de 8 caras.
- Hallar el único método adicional de poner números en una pareja de dados de 35 caras.
Sugerencia 1
Usar una función generadora. (Ejercitarse con el caso de 6 caras, porque ya sabe la respuesta.)
Sugerencia 2
Esta sugerencia da la respuesta para dados de 6 caras (que se llaman Dados de Sicherman)
por el uso de una función generadora. Después de entender esta respuesta, podría
resolver los casos de 8 y de 35 caras.
Para escribir el problema usando una función generadora, usamos una variable
x
y observamos que: el coeficiente de
x^n en
(x^1 + x^2 + x^3 + x^4 + x^5 + x^6)(x^1 + x^2 + x^3 + x^4 + x^5 + x^6)
es el número de formas de tirar
n
con 2 dados regulares. Esto vale
porque interpretamos el primer factor como el resultado de tirar el dado primero (el
exponente es el número de puntos en arriba) y el segundo factor como el resultado de
el dado segundo. Por ejemplo, usted puede lanzar un 8 en 5 formas, porque los factores
que conducen a la
x^8
son
x^2 \cdot x^6, \quad x^3 \cdot x^5, \quad x^4 \cdot x^4, \quad
x^5 \cdot x^3, \quad x^6 \cdot x^2.
Los dados de Sicherman tienen polinomios también, que son
(x^1 + x^2 + x^2 + x^3 + x^3 + x^4)(x^1 + x^3 + x^4 + x^5 + x^6 + x^8),
y el hecho de que tienen la misma frecuencia que la distribución de
dados regulares implica que este producto de polinomios debe ser exactamente el mismo que
el producto para los dados regulares, y si de hecho si se multiplica a cabo
verá que en realidad son idénticos.
Sabemos mucho acerca de polinomios, en
particular sobre su factorización, de modo de convertir nuestro problema en un
problema polinomio podemos utilizar este conocimiento y resolverlo. Imagine que
no se sabe ya la otra solución para dados de 6 caras.
Nos gustaría encontrar polinomios de modo que
\begin{eqnarray}
&&(x^1 + x^2 + x^3 + x^4 + x^5 + x^6)(x^1 + x^2 + x^3 + x^4 + x^5 + x^6)\\
&=& (x^{a_1} + x^{a_2} + x^{a_3} + x^{a_4} + x^{a_5} + x^{a_6})
(x^{b_1} + x^{b_2} + x^{b_3} + x^{b_4} + x^{b_5} + x^{b_6}) \quad \quad \mathrm{(*)}
\end{eqnarray}
en que los a y los b
son los números de punto en cada cara,
y queremos encontrarlos. Una solución válida debe tener todos los
a y los b
mayor que o igual a 1.
Ahora usamos las propiedades de polinomios.
Factorizamos totalmente la izquierda por
\begin{eqnarray}
&& x^1 + x^2 + x^3 + x^4 + x^5 + x^6 \\
&=& x(1+x^1 + x^2 + x^3 + x^4 + x^5) \\
&=& x \frac{x^6 - 1}{x - 1} = x (x^3 + 1) \frac{x^3 - 1}{x - 1} \\
&=& x (x + 1) (x^2 - x + 1) (x^2 + x + 1),
\end{eqnarray}
y el lado izquierdo de (*) es
x^2 (x + 1)^2 (x^2 - x + 1)^2 (x^2 + x + 1)^2.
No sabemos cuáles son los términos en el lado derecho, pero sabemos
que si factorizamos los términos completamente, debemos conseguir
la factorización misma, aunque los términos pueden ser agrupados de manera diferente.
Esto significa que
puede trabajar hacia atrás para descubrir los términos de la derecha:
tenemos en cuenta diferentes
formas de agrupación de los factores para que dos polinomios
(x^{a_1} + x^{a_2} + x^{a_3} + x^{a_4} + x^{a_5} + x^{a_6}) \mathrm{\ y \ }
(x^{b_1} + x^{b_2} + x^{b_3} + x^{b_4} + x^{b_5} + x^{b_6}) \quad \quad \mathrm{(**)}
y ver cuáles
representan dados válidos con 6 caras. Todas las combinaciones no serán válidas, por ejemplo,
no puede poner todos los factores del polinomio en primer lugar, y ninguno en el segundo
(dejando el segundo un constante 1) porque cada polinomio debe tener
6 potencias de
x
para representar a las 6 caras. De hecho, podemos eliminar la
la mayor parte de las posibilidades de la siguiente manera:
-
El requisito de que cada polinomio represente un dado de 6 caras puede
ser escrito numéricamente por diciendo que el valor en
x=1
de cada polinomio en (**) debe ser 6.
Mirando la factorización completa, nos damos cuenta de que
los valores de los factores
x,
x + 1,
x^2 - x + 1, y
x^2 + x + 1
en
x=1
son 1, 2, 1, y 3.
Si un polinomio en (**) tuviera ambos factores
(x + 1)
o ambos factores
(x^2 + x + 1),
entonces en
x=1
el polinomio sería divisible por 4 o 9, y por tanto no podía
ser igual a 6. Por lo tanto, cada polinomio en (**) tiene un solo
copia de estos factores.
-
Cada cara debe tener al menos un punto, por lo que cada polinomio en (**) debe
tienen un factor
x
(de lo contrario el polinomio tendría un término constante, es decir
x^0,
representará 0 puntos).
Por lo tanto cada polinomio en (**) tiene que tener un factor de
x.
La incertidumbre que queda es de los dos factores
(x^2 - x + 1).
No hay ninguna razón obvia por qué tenemos que dar una copia a
cada polinomio, o si podemos dar dos copias al mismo
polinomio. De hecho, ambas opciones valen, dando un factor a cada uno
producirá los dados regulares, y (como se puede comprobar multiplicando
los polinomios), dando los dos ejemplares a un polinomio producirá
dos dados válidos, que son los dados de Sicherman:
x (x + 1) (x^2 + x + 1) \mathrm{\ y \ } x (x + 1) (x^2 - x + 1)^2 (x^2 + x + 1),
que produce
x + 2x^2 + 2x^3 + x^4 \mathrm{\ y \ } x + x^3 + x^4 + x^5 + x^6 + x^8,
y los puntos son
1,2,2,3,3,4 \mathrm{\ y \ } 1,3,4,5,6,8.
Esa es la solución completa para los dados de 6 caras. Ahora utilizar las mismas ideas
para resolver los casos de 8 y de 35 caras.
(La sugerencia siguiente da las factorizaciones necesarios.)
Sugerencia 3
Para los casos de 8 y de 35 caras tenemos la factorización completa
x + \cdots + x^8 = x (x+1) (x^2+1) (x^4+1)
y
\begin{eqnarray}
x + \cdots + x^{35} &=& x (x^4+x^3+x^2+x+1)(x^6+x^5+x^4+x^3+x^2+x+1) \\
&& (x^{24}-x^{23}+x^{19}-x^{18}+x^{17}-x^{16}+x^{14}-x^{13}+x^{12}-x^{11}\\
&& \quad +x^{10}-x^8+x^7-x^6+x^5-x+1).
\end{eqnarray}
Haga clic aquí para ver el resto de la respuesta.
El Resto de la Respuesta
El caso de 8 caras tiene tres mas factorizaciones, y por tanto tres diseños de dado
(no dos, como dice el problema):
\begin{eqnarray}
x (x + 1)^2 (x^4 + 1) &\cdot& x (x^2 + 1)^2 (x^4 + 1) \\
x (x + 1) (x^4 + 1)^2 &\cdot& x (x + 1)(x^2 + 1)^2 \\
x (x + 1)^2 (x^2 + 1) &\cdot& x (x^2 + 1) (x^4 + 1)^2
\end{eqnarray}
y esos producen
\begin{eqnarray}
(x^7+2x^6+x^5+x^3+2x^2+x) &\cdot& (x^9+2x^7+2x^5+2x^3+x) \\
(x^{10}+x^9+2 x^6+2x^5+x^2+x) &\cdot& (x^6+x^5+2x^4+2x^3+x^2+x) \\
(x^5+2x^4+2x^3+2x^2+x) &\cdot& (x^{11}+x^9+2x^7+2x^5+x^3+x)
\end{eqnarray}
(Gracias a Art DuPré para enviando la factorización tercera,
que no estaba en la solución original.)
El caso de 35 caras tiene una factorización más, y produce:
\begin{eqnarray}
(x^{11}&+&2x^{10}+3x^9+4x^8+5x^7+5x^6+5x^5+4x^4+3x^3+2x^2+x) \\
\cdot \, (x^{59}&+& x^{54}+x^{52}+x^{49}+x^{47}+x^{45}+x^{44}+x^{42}+x^{40}+x^{39} \\
&+& x^{38}+x^{37}+x^{35}+x^{34}+x^{33}+x^{32}+x^{31}+x^{30}+x^{29} \\
&+& x^{28}+x^{27}+x^{26}+x^{25}+x^{23}+x^{22}+x^{21}+x^{20}+x^{18} \\
&+& x^{16}+x^{15}+x^{13}+x^{11}+x^8+x^6+x).
\end{eqnarray}
Funciones Generadoras
A generating function is a clothesline on which we hang up a
sequence of numbers for display. (Herbert S. Wilf)
(Una función generadora es un tendedero en que colgamos una
secuencia de números para mostrarla.)
Una función generadora es un polinomio o una serie infinito en que
el coeficiente de la potencia
nésimo
es el valor a
n
de alguna función en que estamos interesados.
En este problema el coeficiente es el número de caras que tienen
n
puntos.
Funciones generadoras se utilizan en casi todos los tipos de problemas de recuento.
Nos permiten transformar un problema en un recuento algebraica o analítica
problema. Con nuestros dados usamos propiedades algebraicas de polinomios
(factorización) para resolver el problema.
Frecuentemente, las funciones generadoras son las series infinitas y no polinomios;
En estos casos se suele tratar de obtener una expresión de forma cerrada para
la función representada por la serie infinita, y usamos hechos sobre el
comportamiento de esta función para deducir datos sobre los coeficientes.
Las referencias mas abajo dan muchos ejemplos de problemas que pueden
ser resueltos con funciones generadoras.
Polinomios Ciclotómicos
Para resolver los problemas de dados, teníamos que factorizar polinomios de la forma
x^{n-1} + ... + x + 1,
es decir, factorizar
x^n - 1 = (x-1) (x^{n-1} + ... + x + 1).
Los raíces de este polinomio se llaman
n-ésimas raíces de la unidad
(unidad significa el número 1).
Una n-ésima raíz de la unidad primitiva
es una que no es m-ésimas raíz de la unidad para un
m menor que n.
Ejemplo: Las raíces cuartas de la unidad son las raíces de
x^4 - 1 = 0.
Estas raíces son 1, -1, i, y -i.
De estas,
1 es primera raíz de la unidad,
-1 es segunda raíz de la unidad,
y las demás,
i y -i,
son primitivas cuartas raíces de la unidad.
El polinomio cuyas raíces son todos los raíces primitivas de la unidad de orden
n
se llama polinomio ciclotómico de orden
n.
Las raíces son convencionalmente designadas por la letra griega
\zeta,
y el polinomio es convencionalmente designado por un
letra griega capital \Phi :
\Phi_n(x) = \prod_\zeta (x - \zeta).
Ejemplo (continuación): Los polinomios ciclotómicos para 1, 2, y 4 son
\begin{eqnarray}
\Phi_1(x) &=& x - 1 \\
\Phi_2(x) &=& x + 1 \\
\Phi_4(x) &=& x^2 + 1
\end{eqnarray}
"Ciclotómico" viene de una frase griega que significa "cortando un círculo".
Si dibujamos la circunferencia unidad en el plano complejo con
las n-ésimas raíces de la unidad, ellas se encuentran en la circunferencia de círculo
y cortan el círculo en n arcos iguales.
Estos puntos son también los vértices de un polígono regular con
n
vértices, inscrito en el círculo. Las raíces de la unidad y los
polinomios ciclotómicos ocurren en muchas áreas de las matemáticas, y
sabemos mucho acerca de ellos.
Es un hecho sorprendente que los polinomios ciclotómicos tienen
coeficientes enteros, y un hecho aún más sorprendente que todos ellos son
irreductible (es decir, que no se factoriza en
polinomios de grado inferior con coeficientes racionales).
Un hecho no sorprendente, pero útil, es que
los polinomios ciclotómicos dan la factorización completa
x^n - 1 = \prod_{m|n} \Phi_m(x).
Ejemplo: Dados de 8 caras. Tenemos las factorización
\begin{eqnarray}
x^8 - 1 &=& \Phi_1(x) \Phi_2(x) \Phi_4(x) \Phi_8(x) \\
&=& (x-1) (x+1) (x^2+1) \Phi_8(x) \\
&=& (x^4 - 1) \Phi_8(x), \\
\Phi_8(x) &=& \frac{x^8 - 1}{x^4 - 1} = x^4 + 1.
\end{eqnarray}
Referencias
- Martin Gardner, "Dados de Sicherman, recuento de Kruskal y otras curiosidades",
capítulo 17 en
Mosaicos de Penrose y Escotillas Cifradas,
Labor, 1990.
-
Wikipedia tiene un artículo sobre
polinomios ciclotómicos.
-
Wikipedia tiene un artículo sobre
funciones generadoras.
-
(en inglés) Haga clic
aquí para ver la pregunta original enviado por Chrix.
|
