The Chemist's Cabinet Puzzle: a polynomial approach

THE CHEMIST’S CABINET PUZZLE: A POLYNOMIAL APPROACH JES´ US GAGO-VARGAS, MARIBEL HARTILLO HERMOSO, AND JOS´ E MAR´ IA UCHA ENR´ IQUEZ Abstract. Realizamos un an´alisis del juego conocido por el herbolario. Se modeliza su soluci´on mediante un sistema polin´omico, y deducimos el n´umero de soluciones a partir de herramientas de ´ Algebra Conmutativa. 1. Introducci´ on El herbolario es un rompecabezas bidimensional de 16 piezas. En 2005, la editorial RBA ([RBA]) lo public´o en una bonita versi´on de madera (figura 1), tal como lo dise˜n´o su creador Jean-Claude Constantin ([Constantin]). El nombre procede del parecido con los botes donde se almacenaban las hierbas y otras sustancias en las farmacias. El objetivo es disponer las 16 piezas m´oviles en una caja, dispuestas en 4 filas y 4 columnas. Las piezas se diferencian entre s´ı por los salientes laterales y las bandas marrones horizontales. Sin embargo, es posible considerar el rompecabezas formado por las 16 piezas que se obtienen al tomar un cuadrado, Date: July 2007. 1991 Mathematics Subject Classification. Primary XXAYY5; Secondary XXA55, XXD55. Key words and phrases. Non-linear systems, Gr¨obner bases. This work was completed with the support of FQM-333, BFM2001-3164. Figure 1. Modelo en madera 1 2 J. GAGO-VARGAS, M. HARTILLO, AND J.M. UCHA Figure 2. Relaciones entre piezas y escoger en cada lado un entrante o un saliente (figura 2). El marco presenta tambi´en salientes y muescas, y una barra horizontal en la parte superior. La disposici´on de ambos elementos resulta clave para determinar el n´umero posible de soluciones. Desde el punto de vista de la representaci´on, exigimos que las piezas de la fila superior tengan entrantes arriba, y las piezas de la fila inferior salientes abajo. Un ejemplo de soluci´on aparece en la figura (3). Este juego ha sido analizado en [CFF-61, CFF-62], en donde aparecen los resultados de Jacques Haubrich sobre el n´umero de soluciones del rompecabezas. Nuestro prop´osito es calcular dicho n´umero a partir de un modelo del problema como sistema de ecuaciones polin´omico. El ideal que definen dichas ecuaciones es cero dimensional y radical, por lo que el n´umero de soluciones del problema viene dado por la dimensi´on como C-espacio vectorial dimCC[x1,...,xn]/I, THE CHEMIST’S CABINET PUZZLE: A POLYNOMIAL APPROACH 3 Figure 3. Soluci´on inicial donde nes el n´umero de variables que usaremos en el modelo. Este n´umero es posible calcularlo mediante bases de Gr¨obner. 2. Modelo Consideremos una pieza del rompecabezas. Viene definida por los entrantes/salientes en los lados del cuadrado. Identificamos entonces cada pieza por un conjunto de 4 variables xi, xi+1, xi+2, xi+3, donde cada una de ellas puede tomar los valores 0,1. xi xi+1 xi+2 xi+3 Por ejemplo, el 0 indica que es un entrante, y el 1 que es un saliente. Como son 16 piezas, obtenemos 64 variables. El modelo visual del problema queda como sigue. x1x5x9x13 x2x3−x6x7−x10 x11 −x14 x15 x4x8x12 x16 | | | | x17 x21 x25 x29 x18 x19 −x22 x23 −x26 x27 −x30 x31 x20 x24 x28 x32 | | | | x33 x37 x41 x45 x34 x35 −x38 x39 −x42 x43 −x46 x47 x36 x40 x44 x48 | | | | x49 x53 x57 x61 x50 x51 −x54 x55 −x58 x59 −x62 x63 x52 x56 x60 x64 4 J. GAGO-VARGAS, M. HARTILLO, AND J.M. UCHA Las condiciones de frontera se imponen sobre las variables x1, x5, x9, x13, x2, x15, x18, x31, x34, x47, x50, x63, x52, x56, x60, x64. El marco superior de la caja nos dice que x1= 0, x5= 0, x9= 0, x13 = 0, y el marco inferior x52 = 1, x56 = 1, x60 = 1, x64 = 1. En los laterales izquierdo y derecho, definidos por las variables x2, x18, x34, x50 yx15, x31, x47, x63 respectivamente, tendremos que colocar cuatro ceros y cuatro unos. Sea L1el subconjunto de cuatro valores de {2,18,34,50,15,31,47,63}donde tendremos un entrante, y L2el conjunto complementario, donde colocaremos un saliente. Entonces xi1= 1, i1∈L1, xi2= 0, i2∈L2. La primera condici´on que se aplica a todas las variables es que valen cero o uno. Esto se expresa con las relaciones F(xi) = xi(xi−1) = 0, i = 1,...,64. Cu´ales son las relaciones entre las piezas? En primer lugar, si dos piezas est´an conectadas, en una de ellas tiene que haber un entrante y en la otra un saliente. Por ejemplo, consideremos la relaci´on entre x3yx6. La condici´on, desde el punto de vista de la l´ogica proposicional es x3= 0 ⇔x6= 1. Entonces, con el dato de que cada una de ellas es cero o uno, lo podemos expresar con la condici´on polin´omica x3+x6−1 = 0. Por claridad en la notaci´on, sea H(i, j) = xi+xj−1. Las relaciones de encaje entre las piezas se definen por el car´acter nulo de los polinomios H(3,6), H(7,10), H(11,14), H(4,17), H(8,21), H(12,25), H(16,29), H(19,22), H(23,26), H(27,30), H(20,33), H(24,37), H(28,41), H(32,45), H(35,38), H(39,42), H(43,46), H(36,49), H(40,53), H(44,57), H(48,61), H(51,54), H(55,58), H(59,62). Llamemos Sal conjunto de pares (i, j) dado por los encajes anteriores. Por otro lado, debemos indicar que todas las piezas son diferentes. Por ejemplo, consideremos las piezas definidas por las variables x1, x2, x3, x4yx5, x6, x7, x8. La condici´on, en principio, queda como (1) x16=x5or x26=x6or x36=x7or x46=x8. Como antes, la condici´on x16=x5se puede reducir a que H(1,5) = x1+x5−1 = 0. Entonces la condici´on 1 da lugar a H(1,5)H(2,6)H(3,7)H(4,8) = 0. Si llamamos G(i, j) = H(i, j)H(i+ 1, j + 1)H(i+ 2, j + 2)H(i+ 3, j + 3), las condiciones de piezas distintas son definidas por el car´acter nulo de los 15(15+1) 2= 120 polinomios G(1,5), G(1,9), G(1,13), G(1,17),...,G(1,61), G(5,9),...,G(53,61), G(57,61). THE CHEMIST’S CABINET PUZZLE: A POLYNOMIAL APPROACH 5 Sea Del conjunto de pares (i, j) dado por las relaciones entre piezas. En resumen, el sistema polin´omico que define las soluciones del problema es (2)                    F(xi) = 0, i = 1,...,64, H(i, j) = 0,(i, j)∈S, G(i, j) = 0,(i, j)∈D, xi= 0, i = 1,5,9,13, xj= 1, j = 52,56,60,64, xi1= 0, i1∈L1, xi2= 1, i2∈L2 3. Bases de Gr¨ obner Para calcular el n´umero de soluciones del sistema 2 necesitamos unos conceptos de ´ Algebra Computacional. Vamos a denotar los monomios en C[x1,...,xn] por xα=xα1 1···xαn n, para α∈Zn +. El grado de xαes |α|=Pn i=1 αi. Dado un polinomio no nulo f(x) = Pαfαxα, sus t´erminos son las expresiones fαxαcon fα6= 0, y su grado deg(f) es el m´aximo de los grados de los t´erminos de f. Un orden monomial ′<′es un orden total en el conjunto de monomios que es un buen orden y satisface la condici´on xα< xβ⇒xα+γ< xβ+γ. Ejemplos de ´ordenes monomiales son el orden lexicogr´afico ′<′ lex, donde xα<lex xβ si α < β para un orden lexicogr´afico en Zn +, o el orden lexicogr´afico graduado ′<′ grlex, donde xα<grlex xβsi |α|<|β|, o |α|=|β|yxα<lex xβ. Fijemos un orden monomial en C[x1,...,xn]. Dado un polinomio no nulo f(x) = Pαfαxα, su t´ermino l´ıder LT(f) es fαxα, donde xαes el monomio m´aximo con respecto al orden dado, con fα6= 0. Sea Iun ideal en C[x1,...,xn]. Un subconjunto finito G⊂Ies una base de Gr¨obner de Isi el t´ermino l´ıder de cualquier polinomio de I es divisible por el t´ermino l´ıder de alg´un polinomio de G. Se conoce que una base de Gr¨obner siempre existe. Un monomio xαse denomina monomio est´andar si no es divisible por el t´ermino l´ıder de alg´un polinomio en I, o de forma equivalente, si xαno es divisible por el t´ermino l´ıder de un polinomio en la base de Gr¨obner. Una vez fijado un orden monomial, se puede aplicar el algoritmo de divisi´on. Sean h1,...,hmyfpolinomios no nulos. Si dividimos fpor los polinomios h1,...,hm, obtenemos polinomios u1,...,umyrque satisfacen f=Pm j=1 ujhj+r, ning´un t´ermino de res divisible por LT(hj), j = 1,...,m si r6= 0, y LT(f)≥LT(ujhj) si uj6= 0. Cuando los polinomios h1,...,hmforman una base de Gr¨obner de I, el resto rest´a un´ıvocamente determinado y es una combinaci´on lineal del conjunto B de los monomios est´andar; esto es r(x) = X xβ∈B rβxβ, donde rβ∈C. Adem´as, f∈Isi y solamente si r= 0. Por tanto, C[x1,...,xn]/I yC|B| son isomorfos como espacios vectoriales. Dado un ideal I, definimos V(I) como el conjunto de ceros complejos, es decir V(I) = {a∈Cn|h(a) = 0,para todo h∈I}. Como todo ideal en C[x1,...,xn] est´a finitamente generado, son los ceros comunes al conjunto de generadores. V(I) es una variedad algebraica, y el problema planteado 6 J. GAGO-VARGAS, M. HARTILLO, AND J.M. UCHA Figure 4. Configuraci´on de ejemplo en la secci´on anterior sobre el n´umero de soluciones del problema es equivalente a preguntar cu´antos puntos tiene dicha variedad. La respuesta la da el siguiente teorema. Theorem 3.1. [CLO, Thm. 2.2.10] Sea Iun ideal en C[x1,...,xn], y V=V(I) el conjunto de ceros definido por I. Entonces la variedad algebraica Ves finita si y solamente si el espacio vectorial C[x1,...,xn]/I tiene dimensi´on finita N. Adem´as, |V| ≤ N, y la igualdad se da si y solamente si el ideal Ies radical. 4. N´ umero de soluciones Consideremos el Iideal definido por los polinomios del sistema 2. El ideal Ies 0-dimensional, a causa de los polinomios F(xi). Adem´as, por la proposici´on [CLO, Prop. 2.7], el ideal Ies radical. Por tanto, el n´umero de soluciones del sistema es igual a la dimensi´on del C-espacio vectorial C[x1,...,x64]/I. Y c´omo calculamos este n´umero? Necesitamos para ello conseguir una base de Gr¨obner Gdel ideal Irespecto a cualquier orden monomial definido en C[x1,...,x64]. Estos c´alculos los hemos realizado con Singular [GPS05], y el comando vdim, que nos da precisamente la dimensi´on del espacio vectorial (o bien, el n´umero de monomios est´andar). Los c´alculos, adem´as, se pueden realizar en un cuerpo de caracter´ıstica 2, pues las soluciones son cero o uno. Este m´etodo acelera los c´alculos en gran medida. Hemos calculado todas las configuraciones posibles con respecto a las condiciones de los laterales. Hay 17 configuraciones esencialmente distintas por simetr´ıa. Codificamos los laterales con 1 para un entrante y 0 para un saliente, y las disponemos en columnas paralelas. Por ejemplo, la dada por la figura 4 se codifica como 0 1 0 1 0 0 1 1 THE CHEMIST’S CABINET PUZZLE: A POLYNOMIAL APPROACH 7 Figure 5. Configuraci´on dual Una simetr´ıa especular de eje vertical, paralelo a los laterales, nos da la configuraci´on 1 0 1 0 0 0 1 1 Una simetr´ıa especular de eje horizontal, paralelo a los lados superiores, produce 1 1 0 0 0 1 0 1 La combinaci´on de las dos simetr´ıas anteriores nos dan la simetr´ıa central, que es 1 1 0 0 1 0 1 0 Pero hay otras configuraciones asociadas. Si se intercambian entrantes y salientes como en la figura 5, marcadas en azul, se obtiene una soluci´on para la configuraci´on 1 0 1 0 1 1 0 0 que llamaremos configuraci´on complementaria. A esta nueva configuraci´on hay que aplicar los movimientos anteriores, con lo que el conjunto de configuraciones relacionadas ser´a 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 0 8 J. GAGO-VARGAS, M. HARTILLO, AND J.M. UCHA Si denominamos σ1a la simetr´ıa especular de eje vertical, σ2a la simetr´ıa especular de eje horizontal, y τa la operaci´on de obtener el complemento, lo que estamos haciendo es calcular el espacio cociente de todas las configuraciones posibles con el grupo Ggenerado por σ1, σ2, τ. Los generadores son de orden 2, por lo que Ges isomorfo a C2×C2×C2, y tiene 8 elementos: G={1, σ1, σ2, τ, σ1σ2, σ1τ, σ2τ, σ1σ2τ}. El resultado final de los c´alculos aparece en la tabla. Configuraci´on Soluciones Configuraci´on Soluciones 0 1 0 1 0 1 0 1 652 0 1 0 1 0 1 1 0 548 0 1 0 1 0 0 1 1 364 0 1 0 0 0 1 1 1 338 0 0 0 1 0 1 1 1 212 0 1 0 1 1 1 0 0 364 0 1 0 0 1 1 0 1 504 0 1 0 1 1 0 1 0 740 0 1 0 0 1 1 1 0 524 0 1 0 0 1 0 1 1 308 0 0 0 1 1 0 1 1 284 0 0 0 0 1 1 1 1 232 0 1 1 0 0 1 1 0 1052 0 1 1 0 0 0 1 1 360 0 1 1 0 0 1 1 0 352 0 0 1 1 1 1 0 0 160 0 1 1 0 1 0 0 1 476 THE CHEMIST’S CABINET PUZZLE: A POLYNOMIAL APPROACH 9 5. Variaciones del problema No es dif´ıcil considerar dos variaciones de este rompecabezas. En primer lugar, tomemos un cuadrado, y consideremos tres posibilidades en cada lado: entrante, saliente y plano. Hay 43= 64 posibilidades, por lo que el problema consiste en formar un cuadrado de orden 8 ×8 con esas piezas, dada una configuraci´on del marco exterior. El modelo es similar al anterior. Cada pieza viene definida por 4 variables, y cada una de ellas puede tomar los valores 0 (entrante), 1 (plano), y 2 (saliente). El encaje de las piezas queda determinado por una expresi´on de la forma xi+xj−2 = 0. La otra condici´on es que las piezas sean distintas, que se expresa a trav´es de una ecuaci´on de la forma (xi−xj−1)(xi−xj−2)(xi+1 −xj+1 −1)(xi+1 −xj+1 −2) (xi+2 −xj+2 −1)(xi+2 −xj+2 −2)(xi+3 −xj+3 −1)(xi+3 −xj+3 −2) = 0. La complejidad crece, pues ahora tenemos 4 ×64 = 256 variables, pero el modelo es f´acil. La otra extensi´on es pasar a un rompecabezas en tres dimensiones. Consideremos un cubo, y sobre cada una de las seis caras tomamos tres posibilidades, como en la variaci´on anterior: pir´amide entrante, pir´amide saliente, lado plano. Hay 63= 216 piezas, y se trata de formar un cubo de orden 6 ×6×6, de nuevo con una configuraci´on dada por el marco exterior. Cada pieza se define por seis variables (una por cada cara), por lo que el sistema polin´omico est´a definido sobre 64= 1296 variables. Esto ya es un reto computacional, aunque se trate de un ideal ideal radical, cero dimensional, y que los c´alculos se pueden hacer en caracter´ıstica 3. 6. Conclusiones Este rompecabezas es una buena excusa desde el punto de vista pedag´ogico para presentar modelos no lineales de problemas, as´ı como ciertos conceptos clave de ´ Algebra Conmutativa. No existen muchas introducciones a estos temas avanzados desde planteamientos sencillos como este problema, tal como ya hab´ıamos planteado en [GHMU]. Es m´as, ciertas cuestiones de optimizaci´on no lineal usan estas t´ecnicas [LLMO], por lo que estos modelos van m´as all´a de una simple curiosidad. References CLO. D. Cox, J. Little, D. O’Shea. Using Algebraic Geometry, volume 185 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1998. RBA. Varios. Juegos de Ingenio, fasc. 1. RBA Editores, Barcelona, 2006. Constantin. J.C. Constantin. J810-Apothekeschrank. http://www.constantin-jean-clau.de/. [Online; accessed 7-July-2007]. GHMU. J. Gago-Vargas, I. Hartillo-Hermoso, J. Mart´ın-Morales, J.M. Ucha-Enr´ıquez. Sudokus and Gr¨obner bases: not only a divertimento, in ’Computer Algebra in Scientific Computing (9th International Workshop, CASC 2006, Chisinau, Moldova)’, Ganzha, Victor G.; Mayr, Ernst W.; Vorozhtsov, Evgenii V. (Eds.) Lecture Notes in Computer Science, vol. 4194, pp. 155-165, 2006. CFF-61. D. Gebhardt. The Chemist Cabinet Puzzle. CFF Newsletter, 61, 2003. CFF-62. D. Gebhardt. Analysis of the Chemist Cabinet Puzzle. CFF Newsletter, 62, 2003. GPS05. G.-M. Greuel, G. Pfister, and H. Sch¨onemann. Singular 3.0. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern (2005). http://www.singular.uni-kl.de.