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 

2 comentarios:

  1. Faltan dos detalles:
    (1) En las reglas ACB: ¿Cómo sabes que no hay más relaciones que no has considerado?
    (2) En las reglas NBA: Te falta verificar que dado un par cualquiera de casillas del borde, hay una combinación de movimientos que cambia el sino de esas dos casillas. Con lo que has escrito, sería posible que la condición de tener un número par de unos en las ocho casillas del borde es una condición necesaria pero no suficiente para tener solución.

    ResponderEliminar
    Respuestas
    1. 1 ¿Qué otras relaciones no he considerado? F1F2F3F4C1C2C3C4D1dD2 es el máximo número de operaciones a realizar, pero he demostrado que F1F2F3F4C1C2C3D1 es lo máximo que podemos hacer sin repetir posiciones, luego nos da un máximo de 255 posiciones más la inicial.
      Por otro lado si F1F2F3F4C1C2C3D1 (ni sus permutaciones) no da lugar a posiciones repetidas tampoco ningún subconjunto lo va a hacer por tanto hay 255 +1 alcanzables.

      2 Es evidente que en las ocho posiciones que no son centrales al cuadro ni esquinas de este los -1 se anulan (convierten e 1) dos a dos. Si hay dos -1 adyacentes pueden estar en una diagonal de dos (inmediato entenderlo) o en el centro de una fila o columna. Conmutando la fila o columna convertimos ambos -1 en 1 y da igual lo que pase con las esquinas pues una a una la podemos conmutar.
      Si no son adyacentes con las mismas operaciones de conmutar la diagonal de dos, o conmutando la fila o columna (si se encuentra en el centro) podemos mover cualquier -1 hasta hacerlo adyacente a otro -1. Pero esto es evidente para quien haya entendido la solución al problema original.

      Eliminar