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 Abs ac . Realizamos un an´alisis del juego conocido po el he bola io. Se modeliza su soluci´on median e un sis ema polin´omico, y deducimos el n´ume o de soluciones a pa i de he amien as de ´ Algeb a Conmu a i a. 1. In oducci´ on El he bola io es un ompecabezas bidimensional de 16 piezas. En 2005, la edi o- ial RBA ([RBA]) lo public´o en una boni a e si´on de made a ( igu a 1), al como lo dise˜n´o su c eado Jean-Claude Cons an in ([Cons an in]). El nomb e p ocede del pa ecido con los bo es donde se almacenaban las hie bas y o as sus ancias en las a macias. El obje i o es dispone las 16 piezas m´o iles en una caja, dispues as en 4 ilas y 4 columnas. Las piezas se di e encian en e s´ı po los salien es la - e ales y las bandas ma ones ho izon ales. Sin emba go, es posible conside a el ompecabezas o mado po las 16 piezas que se ob ienen al oma un cuad ado, Da e: July 2007. 1991 Ma hema ics Subjec Classi ica ion. P ima y XXAYY5; Seconda y XXA55, XXD55. Key wo ds and ph ases. Non-linea sys ems, G ¨obne bases. This wo k was comple ed wi h he suppo o FQM-333, BFM2001-3164. Figu e 1. Modelo en made a 1 2 J. GAGO-VARGAS, M. HARTILLO, AND J.M. UCHA Figu e 2. Relaciones en e piezas y escoge en cada lado un en an e o un salien e ( igu a 2). El ma co p esen a ambi´en salien es y muescas, y una ba a ho izon al en la pa e supe io . La dis- posici´on de ambos elemen os esul a cla e pa a de e mina el n´ume o posible de soluciones. Desde el pun o de is a de la ep esen aci´on, exigimos que las piezas de la ila supe io engan en an es a iba, y las piezas de la ila in e io salien es abajo. Un ejemplo de soluci´on apa ece en la igu a (3). Es e juego ha sido analizado en [CFF-61, CFF-62], en donde apa ecen los esul ados de Jacques Haub ich so- b e el n´ume o de soluciones del ompecabezas. Nues o p op´osi o es calcula dicho n´ume o a pa i de un modelo del p oblema como sis ema de ecuaciones polin´omico. El ideal que de inen dichas ecuaciones es ce o dimensional y adical, po lo que el n´ume o de soluciones del p oblema iene dado po la dimensi´on como C-espacio ec o ial dimCC[x1,...,xn]/I, THE CHEMIST’S CABINET PUZZLE: A POLYNOMIAL APPROACH 3 Figu e 3. Soluci´on inicial donde nes el n´ume o de a iables que usa emos en el modelo. Es e n´ume o es posible calcula lo median e bases de G ¨obne . 2. Modelo Conside emos una pieza del ompecabezas. Viene de inida po los en an es/salien es en los lados del cuad ado. Iden i icamos en onces cada pieza po un conjun o de 4 a iables xi, xi+1, xi+2, xi+3, donde cada una de ellas puede oma los alo es 0,1. xi xi+1 xi+2 xi+3 Po ejemplo, el 0 indica que es un en an e, y el 1 que es un salien e. Como son 16 piezas, ob enemos 64 a iables. El modelo isual del p oblema 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 on e a se imponen sob e las a iables x1, x5, x9, x13, x2, x15, x18, x31, x34, x47, x50, x63, x52, x56, x60, x64. El ma co supe io de la caja nos dice que x1= 0, x5= 0, x9= 0, x13 = 0, y el ma co in e io x52 = 1, x56 = 1, x60 = 1, x64 = 1. En los la e ales izquie do y de echo, de inidos po las a iables x2, x18, x34, x50 yx15, x31, x47, x63 espec i amen e, end emos que coloca cua o ce os y cua o unos. Sea L1el subconjun o de cua o alo es de {2,18,34,50,15,31,47,63}donde end emos un en an e, y L2el conjun o complemen a io, donde coloca emos un salien e. En onces xi1= 1, i1∈L1, xi2= 0, i2∈L2. La p ime a condici´on que se aplica a odas las a iables es que alen ce o o uno. Es o se exp esa con las elaciones F(xi) = xi(xi−1) = 0, i = 1,...,64. Cu´ales son las elaciones en e las piezas? En p ime luga , si dos piezas es ´an conec adas, en una de ellas iene que habe un en an e y en la o a un salien e. Po ejemplo, conside emos la elaci´on en e x3yx6. La condici´on, desde el pun o de is a de la l´ogica p oposicional es x3= 0 ⇔x6= 1. En onces, con el da o de que cada una de ellas es ce o o uno, lo podemos exp esa con la condici´on polin´omica x3+x6−1 = 0. Po cla idad en la no aci´on, sea H(i, j) = xi+xj−1. Las elaciones de encaje en e las piezas se de inen po el ca ´ac e 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 conjun o de pa es (i, j) dado po los encajes an e io es. Po o o lado, debemos indica que odas las piezas son di e en es. Po ejemplo, conside emos las piezas de inidas po las a iables x1, x2, x3, x4yx5, x6, x7, x8. La condici´on, en p incipio, queda como (1) x16=x5o x26=x6o x36=x7o x46=x8. Como an es, la condici´on x16=x5se puede educi a que H(1,5) = x1+x5−1 = 0. En onces la condici´on 1 da luga 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 dis in as son de inidas po el ca ´ac e 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 conjun o de pa es (i, j) dado po las elaciones en e piezas. En esumen, el sis ema polin´omico que de ine las soluciones del p oblema 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 G ¨ obne Pa a calcula el n´ume o de soluciones del sis ema 2 necesi amos unos concep os de ´ Algeb a Compu acional. Vamos a deno a los monomios en C[x1,...,xn] po xα=xα1 1···xαn n, pa a α∈Zn +. El g ado de xαes |α|=Pn i=1 αi. Dado un polinomio no nulo (x) = Pα αxα, sus ´e minos son las exp esiones αxαcon α6= 0, y su g ado deg( ) es el m´aximo de los g ados de los ´e minos de . Un o den monomial ′<′es un o den o al en el conjun o de monomios que es un buen o den y sa is ace la condici´on xα< xβ⇒xα+γ< xβ+γ. Ejemplos de ´o denes monomiales son el o den lexicog ´a ico ′<′ lex, donde xα<lex xβ si α < β pa a un o den lexicog ´a ico en Zn +, o el o den lexicog ´a ico g aduado ′<′ g lex, donde xα<g lex xβsi |α|<|β|, o |α|=|β|yxα<lex xβ. Fijemos un o den monomial en C[x1,...,xn]. Dado un polinomio no nulo (x) = Pα αxα, su ´e mino l´ıde LT( ) es αxα, donde xαes el monomio m´aximo con espec o al o den dado, con α6= 0. Sea Iun ideal en C[x1,...,xn]. Un subconjun o ini o G⊂Ies una base de G ¨obne de Isi el ´e mino l´ıde de cualquie polinomio de I es di isible po el ´e mino l´ıde de alg´un polinomio de G. Se conoce que una base de G ¨obne siemp e exis e. Un monomio xαse denomina monomio es ´anda si no es di isible po el ´e mino l´ıde de alg´un polinomio en I, o de o ma equi alen e, si xαno es di isible po el ´e mino l´ıde de un polinomio en la base de G ¨obne . Una ez ijado un o den monomial, se puede aplica el algo i mo de di isi´on. Sean h1,...,hmy polinomios no nulos. Si di idimos po los polinomios h1,...,hm, ob enemos polinomios u1,...,umy que sa is acen =Pm j=1 ujhj+ , ning´un ´e mino de es di isible po LT(hj), j = 1,...,m si 6= 0, y LT( )≥LT(ujhj) si uj6= 0. Cuando los polinomios h1,...,hm o man una base de G ¨obne de I, el es o es ´a un´ı ocamen e de e minado y es una combinaci´on lineal del conjun o B de los monomios es ´anda ; es o es (x) = X xβ∈B βxβ, donde β∈C. Adem´as, ∈Isi y solamen e si = 0. Po an o, C[x1,...,xn]/I yC|B| son isomo os como espacios ec o iales. Dado un ideal I, de inimos V(I) como el conjun o de ce os complejos, es deci V(I) = {a∈Cn|h(a) = 0,pa a odo h∈I}. Como odo ideal en C[x1,...,xn] es ´a ini amen e gene ado, son los ce os comunes al conjun o de gene ado es. V(I) es una a iedad algeb aica, y el p oblema plan eado 6 J. GAGO-VARGAS, M. HARTILLO, AND J.M. UCHA Figu e 4. Con igu aci´on de ejemplo en la secci´on an e io sob e el n´ume o de soluciones del p oblema es equi alen e a p egun a cu´an os pun os iene dicha a iedad. La espues a la da el siguien e eo ema. Theo em 3.1. [CLO, Thm. 2.2.10] Sea Iun ideal en C[x1,...,xn], y V=V(I) el conjun o de ce os de inido po I. En onces la a iedad algeb aica Ves ini a si y solamen e si el espacio ec o ial C[x1,...,xn]/I iene dimensi´on ini a N. Adem´as, |V| ≤ N, y la igualdad se da si y solamen e si el ideal Ies adical. 4. N´ ume o de soluciones Conside emos el Iideal de inido po los polinomios del sis ema 2. El ideal Ies 0-dimensional, a causa de los polinomios F(xi). Adem´as, po la p oposici´on [CLO, P op. 2.7], el ideal Ies adical. Po an o, el n´ume o de soluciones del sis ema es igual a la dimensi´on del C-espacio ec o ial C[x1,...,x64]/I. Y c´omo calculamos es e n´ume o? Necesi amos pa a ello consegui una base de G ¨obne Gdel ideal I espec o a cualquie o den monomial de inido en C[x1,...,x64]. Es os c´alculos los hemos ealizado con Singula [GPS05], y el comando dim, que nos da p ecisamen e la dimensi´on del espacio ec o ial (o bien, el n´ume o de monomios es ´anda ). Los c´alculos, adem´as, se pueden ealiza en un cue po de ca - ac e ´ıs ica 2, pues las soluciones son ce o o uno. Es e m´e odo acele a los c´alculos en g an medida. Hemos calculado odas las con igu aciones posibles con espec o a las condiciones de los la e ales. Hay 17 con igu aciones esencialmen e dis in as po sime ´ıa. Codi icamos los la e ales con 1 pa a un en an e y 0 pa a un salien e, y las disponemos en columnas pa alelas. Po ejemplo, la dada po la igu a 4 se codi ica como 0 1 0 1 0 0 1 1 THE CHEMIST’S CABINET PUZZLE: A POLYNOMIAL APPROACH 7 Figu e 5. Con igu aci´on dual Una sime ´ıa especula de eje e ical, pa alelo a los la e ales, nos da la con igu- aci´on 1 0 1 0 0 0 1 1 Una sime ´ıa especula de eje ho izon al, pa alelo a los lados supe io es, p oduce 1 1 0 0 0 1 0 1 La combinaci´on de las dos sime ´ıas an e io es nos dan la sime ´ıa cen al, que es 1 1 0 0 1 0 1 0 Pe o hay o as con igu aciones asociadas. Si se in e cambian en an es y salien es como en la igu a 5, ma cadas en azul, se ob iene una soluci´on pa a la con igu aci´on 1 0 1 0 1 1 0 0 que llama emos con igu aci´on complemen a ia. A es a nue a con igu aci´on hay que aplica los mo imien os an e io es, con lo que el conjun o de con igu aciones elacionadas se ´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 sime ´ıa especula de eje e ical, σ2a la sime ´ıa especula de eje ho izon al, y τa la ope aci´on de ob ene el complemen o, lo que es amos haciendo es calcula el espacio cocien e de odas las con igu aciones posibles con el g upo Ggene ado po σ1, σ2, τ. Los gene ado es son de o den 2, po lo que Ges isomo o a C2×C2×C2, y iene 8 elemen os: G={1, σ1, σ2, τ, σ1σ2, σ1τ, σ2τ, σ1σ2τ}. El esul ado inal de los c´alculos apa ece en la abla. Con igu aci´on Soluciones Con igu aci´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. Va iaciones del p oblema No es di ´ıcil conside a dos a iaciones de es e ompecabezas. En p ime luga , omemos un cuad ado, y conside emos es posibilidades en cada lado: en an e, salien e y plano. Hay 43= 64 posibilidades, po lo que el p oblema consis e en o ma un cuad ado de o den 8 ×8 con esas piezas, dada una con igu aci´on del ma co ex e io . El modelo es simila al an e io . Cada pieza iene de inida po 4 a iables, y cada una de ellas puede oma los alo es 0 (en an e), 1 (plano), y 2 (salien e). El encaje de las piezas queda de e minado po una exp esi´on de la o ma xi+xj−2 = 0. La o a condici´on es que las piezas sean dis in as, que se exp esa a a ´es de una ecuaci´on de la o ma (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 c ece, pues aho a enemos 4 ×64 = 256 a iables, pe o el modelo es ´acil. La o a ex ensi´on es pasa a un ompecabezas en es dimensiones. Conside emos un cubo, y sob e cada una de las seis ca as omamos es posibilidades, como en la a iaci´on an e io : pi ´amide en an e, pi ´amide salien e, lado plano. Hay 63= 216 piezas, y se a a de o ma un cubo de o den 6 ×6×6, de nue o con una con igu aci´on dada po el ma co ex e io . Cada pieza se de ine po seis a iables (una po cada ca a), po lo que el sis ema polin´omico es ´a de inido sob e 64= 1296 a iables. Es o ya es un e o compu acional, aunque se a e de un ideal ideal adical, ce o dimensional, y que los c´alculos se pueden hace en ca ac e ´ıs ica 3. 6. Conclusiones Es e ompecabezas es una buena excusa desde el pun o de is a pedag´ogico pa a p esen a modelos no lineales de p oblemas, as´ı como cie os concep os cla e de ´ Algeb a Conmu a i a. No exis en muchas in oducciones a es os emas a anzados desde plan eamien os sencillos como es e p oblema, al como ya hab´ıamos plan eado en [GHMU]. Es m´as, cie as cues iones de op imizaci´on no lineal usan es as ´ecnicas [LLMO], po lo que es os modelos an m´as all´a de una simple cu iosidad. Re e ences CLO. D. Cox, J. Li le, D. O’Shea. Using Algeb aic Geome y, olume 185 o G adua e Tex s in Ma hema ics. Sp inge -Ve lag, New Yo k, 1998. RBA. Va ios. Juegos de Ingenio, asc. 1. RBA Edi o es, Ba celona, 2006. Cons an in. J.C. Cons an in. J810-Apo hekesch ank. h p://www.cons an in-jean-clau.de/. [Online; accessed 7-July-2007]. GHMU. J. Gago-Va gas, I. Ha illo-He moso, J. Ma ´ın-Mo ales, J.M. Ucha-En ´ıquez. Sudokus and G ¨obne bases: no only a di e imen o, in ’Compu e Algeb a in Scien i ic Compu ing (9 h In e na ional Wo kshop, CASC 2006, Chisinau, Moldo a)’, Ganzha, Vic o G.; May , E ns W.; Vo ozh so , E genii V. (Eds.) Lec u e No es in Compu e Science, ol. 4194, pp. 155-165, 2006. CFF-61. D. Gebha d . The Chemis Cabine Puzzle. CFF Newsle e , 61, 2003. CFF-62. D. Gebha d . Analysis o he Chemis Cabine Puzzle. CFF Newsle e , 62, 2003. GPS05. G.-M. G euel, G. P is e , and H. Sch¨onemann. Singula 3.0. A Compu e Algeb a Sys- em o Polynomial Compu a ions. Cen e o Compu e Algeb a, Uni e si y o Kaise slau e n (2005). h p://www.singula .uni-kl.de.