Vistas de página en total

jueves, 7 de agosto de 2014

Las parrillas

Problema de El País
http://sociedad.elpais.com/sociedad/2014/07/29/videos/1406656175_265355.html

La solución
http://sociedad.elpais.com/sociedad/2014/08/05/videos/1407248470_547635.html

Lo que se plantea a continuación es en el caso de reglas ACB  y después NBA cuántas parrillas iniciales pueden resolver el problema y en cuántos conjuntos disjuntos se componen todas las parrillas posibles y de cuántas parrillas se compone cada conjunto.

Explicación de las distintas parrillas con reglas ACB


Las distintas operaciones las denominamos. F1,F2,F3,F4,C1,C2,C3,C4,D1,D2. F es fila, C columna, D diagonal.
Se aprecia que las operaciones son conmutativas y además involutivas. Es decir: F1*F2 = F2*F1  y F1 * F1 := no produce cambio alguno.
Esto quiere decir que el orden da igual y que solo hay 10 posibles operaciones a realizar, pues más volvemos a algún estado anterior.
Sin embargo Si hacemos F1*F2*F3*F4*C1*C2*C3*C4 nos vuelve al estado inicial, luego sobra una de esas operaciones, digamos C4.
Esto quiere decir que F1*F2*F3*F4*C1*C2*C3 = C4.
Realmente podemos poner el signo "=" sustituyendo a uno cualquiera de producto"*" de una cadena que nos vuelva a a la situación inicial, por ejemplo F1*F2*F3*F4 = C1*C2*C3*C4

Pero también F1*F2*F3*F4*C1*C2*C3*D1*D2*C1*F2*F3  nos vuelve al estado inicial, de lo que deducimos que D2 = F1*F4*C2*C3*D1. Luego solo podemos usar D1 o D2 para producir estados diferentes. Es decir como mucho ocho operaciones. Sabemos que hay 2^16 = 65536 parrillas distintas y que con las operaciones descritas no podemos recorrer todas ellas desde una inicial, debe haber varios conjuntos excluyentes del mismo número de parrillas.
Tenemos 8 operaciones a realizar: F1,F2,F3,F4,C1,C2,C3,D1, Codificamos con 1 si usamos una determinada operación y un cero si no. 00000000 significa el estado inicial y sin operaciones y 11111111 el estado que se alcanza realizando las ocho posibles operaciones.  Eso nos da 2^8 = 256 estados diferentes alcanzables desde cada posición inicial -incluiido este-  y 2^16 / 2^8 = 2^8 = 256  conjuntos diferentes. Si la posición inicial está dentro del conjunto  que contiene la parrilla todos 1 tiene solución. O sea probabilidad 1/256.

Explicación de las distintas parrillas con reglas NBA


En el caso de que se apliquen las reglas NBA la cosa es mucho más sencilla pues las casillas de las esquinas y las cuatro del centro las podremos cambiar a nuestro antojo, las primeras con un solo movimiento cada una y las centrales con muy pocos. Así el problema será resoluble si en las 8 casillas restantes hay un número par de -1 y no tendrá solución si es impar. Solo queda calcular el número de casos del total que son pares o impares. Las pares serán la suma de las combinaciones pares:
 C (8,0) + C(8,2) + C(8,4) + C(8,6) + C(8,8) = 1+ 28 + 70 + 28 +1 = 128
Las impares;     C (8,1) + C(8,3) + C(8,5) + C(8,7)  =  8 + 56 + 56 +8 = 128
O sea tiene la misma probabilidad (1/2) de ser resoluble que irresoluble. El número total de parrillas es esas 256 posibilidades multiplicadas por las 16 casos posibles de las esquinas y por los 16 casos posibles de las centrales= (128 + 128) * 16 * 16 = 2^16 = 65536