Quinto y último desafío de verano que nos traen la Real Sociedad Matemática Española y El País, del estilo a los que se propusieron celebrando el Centenario de la RSME y en las dos últimas navidades. En esta ocasión lo propone Vicente Muñoz, profesor de la Universidad Complutense de Madrid (UCM) que, por cierto, colaboró hace un tiempo en Gaussianos con el artículo Vicente Muñoz nos habla de Geometría y Topología con Planito y la forma del Universo.
Como podéis ver en el título de este post, el problema se titula Una carita feliz, y podéis ver el vídeo con el planteamiento del mismo haciendo click en este enlace. Dejo aquí de todas formas el planteamiento del problema por escrito:
Tenemos un juego electrónico que consiste en una cuadrícula de luces que pueden estar encendidas o apagadas. Cuando se pulsa una casilla, el estado de la misma y el de las cuatro adyacentes cambia (si estaba encendida se apaga, y si estaba apagada se enciende). Esta figura sirve como ejemplo de cómo funciona el juego:
Así, con un tablero grande, y partiendo de todas las luces apagadas, hemos conseguido una carita feliz como la que se ve en la imagen de abajo. A la derecha, hemos marcado con una x las casillas que hemos presionado, para acordarnos de cómo lo hemos hecho.
Y ahora el reto de esta semana:
El desafío tiene dos partes. La primera consiste en mostrar que hay al menos un dibujo de luces iluminadas que no se puede conseguir con ninguna forma de presionar casillas. La segunda, explicar por qué al menos la mitad de los posibles dibujos no se pueden conseguir.
Entre los que resuelvan correctamente el desafío se sorteará la colección de libros “Grandes Ideas de la Ciencia”. Si encontráis la solución y queréis participar sólo tenéis que enviarla a desafiodeagosto5@gmail.com antes de que termine el lunes 1 de septiembre.
Y respecto al tema de los comentarios, al igual que hemos hecho en todos los desafíos de El País y en los GaussianosyGuijarro, en principio no tengo pensado quitaros la oportunidad de comentar, pero me gustaría que si queréis comentar no dierais la solución directamente, preferiría que dierais pistas, que hablarais de la forma de resolverlo, en vez de limitaros a dar la solución tal cual. Muchas gracias a todos y a disfrutar con el desafío.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Muy bonito el problema pero todavía no me ha salido. Hay que pensar.
Conjetura: Quizás si un dibujo se puede hacer, su inverso no; y entonces al menos la mitad de los posibles dibujos (los que sí, y sus inversos que no) no se pueden conseguir. ¿?
J.M. Valverde: Contraejemplos para dibujos de 1×1, 2×2 y 3×3. En el de 3×3, cuatro puntos en las esquinas, es de fácil resolución.
Información Bitacoras.com
Valora en Bitacoras.com: Quinto y último desafío de verano que nos traen la Real Sociedad Matemática Española y El País, del estilo a los que se propusieron celebrando el Centenario de la RSME y en las dos últimas navidades. En esta ocasión lo…
Pista: Partiendo de una tablero grande con todas las luces apagadas, demostrar que no se puede llegar a un tablero con todas las luces encendidas. (Conjetura)
La parte1 está resuelta si se resulve la parte dos.
Entiendo que la solución es como la del primer problema del cuadrado de 4×4 sin mirar mas
Yo tras ver el vídeo creo que es en el 24×24. Si se encuentra una solución para la primera pregunta, la segunda es un corolario automático (si se piensa con calma). Además hay formulaciones equivalentes que pueden ayudar a resolver el problema.
Como respuesta a alguna de esas conjeturas decir que es equivalente que se pueda iluminar todo el tablero a que dada una iluminación cualquiera se pueda construir la opuesta, que también equivale a que exista una iluminación para la cual se pueda construir la opuesta.
Buenos días. Aunque el tamaño del tablero, una vez que es grande, no es demasiado importante (y por eso Vicente no lo especifica), hemos decidido aclarar que se puede pensar en el 24×24. Espero que publiquen en breve la aclaración.
Y, efectivamente, la prumera pregunta es un caso particular de la segunda, pero, como señala Daniel, también es cierto que la segunda es un corolario de la primera. Quizás eso explica que Vicente haya dividifo el desafío en dos 😉
Efectivamente en el texto es ambiguo pero en el vídeo está claro que se refiere al de 24×24. Tengo una demostración muy sencilla y corta para el de 24×24 que no se generaliza para otros tableros más grandes.
Si recordamos el debate de clases de soluciones del problema 1 en este problema de entrada el nºmáximo de clases es 2^24.
Cada clase tiene como máximo 2^24 elementos y el nº de tableros diferentes es 2^(24×24)
Todo tablerto pertenee a una clase, luego 2^24 clases de 2^24 elementos cada una
Hola DIAMOND,
El correo destino hace referencia al problema 4 ¿Es ok o hand error?
Salud
Ups, error mío, no lo cambié. Gracias por el aviso Juanjo :-).
diamond, también has puesto UAM como siglas de la complutense
Vaya tela… Es que copié el texto del desafío anterior y olvidé rectificar algunas cosas. Gracias por el aviso Wachino :-).
Yo después de mucho abrirme la cabeza también saqué la primera pregunta (y por tanto la segunda). También sólo me vale para 24 x 24 como a Javier (deduzco que debe de ser exactamente la misma idea). Para la primera la mejor pista que puedo dar es que conviene aprovechar todo lo que nos dan (de un modo similar al desafío de Dido).
Que de la segunda se deduce la primera lo veo evidente, pero no que de la primera se deduzca la segunda. De hecho la primera la demuestro en un par de líneas con un razonamiento que debe ser similar al de Daniel, por las pistas. Pensaré un poco más en la segunda, por separado o a partir de la primera.
La solución rápida no creo que sea la que buscaban cuando pusieron el desafío, pero mejor eso que nada.
Daniel, no destripes más, que luego algunos se molestan.
Juanjo, la cuenta que haces de las clases no está clara, revísatelo que no cuadra.
Creo que ya tengo la idea general del asunto, ahora me tocaría demostrar la primera parte del problema, porque si esa hipótesis es cierta, entonces la segunda cae por su propio peso. Veremos…
Para hacerlo más interesante (aunque este no era fácil) intento responder al desafío sin tener en cuenta el tamaño del tablero, pero no hay manera.
Lo he podido demotrar para tableros con una dimensión impar y otra de la forma 3k-1. También para tableros con dimensiones de la forma 5k-1. Y bueno, para algunos casos particulares más con pocas luces (¡como yo!).
Supongo que lo intentaré un poco más pero me estoy desanimando… ¿alguna idea?
Sive, para un cuadrado de lado 2 el enunciado no se cumple y 2=3×1-1, q es de la forma 3k-1 q dices…
rtomas, sive se refiere a los del tipo [2m+1,3n-1]. He encontrado una «excepción» generalizable a todos esos casos, (que supongo que es la misma de sive) por lo que estoy de acuerdo. La que no he encontrado es la del tipo 5k-1, que no sé si sirven para cualquier ancho o para cuadrados.
Los otros tableros son más dificiles y ahí solo encuentro casos particulares: [1,1], [1,3], [1,4], [1,6], [2,2], [2,4], [3,3] y [3,4]. En estos casos se puede conseguir cualquier dibujo.
Mmonchi, sive, visto para tableros de (4m-1) filas y (3n-1) columnas, (o al revés), y también para tableros [5m-1, 5n-1]. Sobre la conjetura de las 2 clases (lo de que sólo hay 2 clases, la de la todoapagado y la de la todoencendido), creo que es falsa. Me parecen pocas 2 clases, y además para 4×4 la todoapagado y la todoencendido están en la misma clase. Lo que creo sobre el número de clases es que es mayor o igual que 2 y menor o igual que 2^N, (para cuadrados de NxN, y N a partir de 4). Y sobre… Lee más »
Cierto, no lo leí bien
Jesusc, para [1,2] y [1,5] hay dos clases, para [2,3] hay cuatro, del resto de los casos resueltos solo puedo decir que hay más de una. Sería interesante llegar a una fórmula que nos diera el número de clases de [a,b] en función de a y b.
Pongo los casos que he resuelto por si a alguien le sirven:
C(1,1)=1, C(1,2)=2, C(1,3)=1, C(1,4)=1, C(1,5)=2, C(1,6)=1, C(1,7)=1, C(1,8)=2, C(1,9)=1, C(1,10)=1, C(1,11)=2.
C(2,2)=1, C(2,3)=4, C(2,4)=1, C(2,5)=2.
C(3,3)=1, C(3,4)=1.
C(a,b) es el número de clase de un tablero de axb y obviamente C(a,b)=C(b,a).
Hola, Con este pasé un buen tiempo hasta que encontré una forma de resolverlo. Y creo que la forma que encontré es válida pero sólo serviría para 24×24 … Digo esto por varias razones: * una de ellas es por si alguien se está «volviendo loco» buscando soluciones generales para «tableros grandes» … que según lo dicho no sería necesario resolverlo de una forma tan general. * otra razón es que si de verdad es cierto que vale para «cualquier tablero siempre que sea ‘grande'» pues estoy intrigado de cómo demostrar eso (pero vuelvo a repetir que no sería necesario… Lee más »
Corrijo las clases de (2,3) que son 2 y no 4. De momento no encuentro ningún tablero con más de dos clases, ni sé si lo puede haber.
C(1,1)=1, C(1,2)=2, C(1,3)=1, C(1,4)=1, C(1,5)=2, C(1,6)=1, C(1,7)=1, C(1,8)=2, C(1,9)=1, C(1,10)=1, C(1,11)=2.
C(2,2)=1, C(2,3)=2, C(2,4)=1, C(2,5)=2, C(2,6)=1, C(2,8)=1.
C(3,3)=1, C(3,4)=1.
Supongo que todos estaremos llegando a la misma solución, y después de la nota que han puesto (gracias, Acido) tengo más claro que lo que se pretende es que resolvamos ese caso aunque no supiéramos que es el 24×24.
Hola.
He hecho una página en la que se puede practicar con el jueguecito.
Quizás os sea útil:
http://cofres.site11.com/david/elpais/20140828.htm
(Aunque hay un montón de sitios donde podéis jugar al juego que mencionan
en el desafío).
Acido, gracias por la pista!!!
David!!! Te has currado hasta la carita!!! Muchas gracias!!!
Mmonchi, un tablero de 29×29 tiene más de dos clases (creo que 8 mínimo, aunque ahora sólo podría justificar 5 de ellas).
Como lo has demostrado para tableros de la forma (2k-1, 3k-1), si lo hemos hecho igual, podras ver rápido que un tablero de 5×5 tiene más de dos clases también. Sólo tienes que observar que 5 es a la vez impar y de la forma 3k-1.
sive, a partir de cómo he demostrado los de la forma (2k-1, 3k-1) solo llego a dos clases, pero a partir del (4,4) llego a que el (24,24) tiene como mínimo 4 clases, así que deben existir formas con más clases aún.
Esperaré al martes para explicar los pasos que doy, ya que de ellos se saca la solución del problema de forma inmediata.
Lo habremos hecho diferente. Eso es bueno, lo mismo sacamos algo mas entre todos a partir del martes.
Hola,
No me ha quedado claro lo de que la segunda es un corolario de la primera. ¿Es una conjetura? o está claro… Es para echarle tiempo pensándolo o no, jeje. La primera la he sacado rápido, así que supongo que tendré que buscar como justificar la 2ª a partir de la 1ª… ¿no? Saludos
Auditorcillo, ¿tu eres el listo que en la fiesta bailo con dos al mismo tiempo y entonces alguien se quedó desparejado? xD (y los ‘hijos’ del desparejado también lo eran?)
Buenas noches, Yo por fin lo he resuelto también. Me lié al principio pensando que si los lados no eran pares (en cuanto a numero de celdas) haría falta añadir unos cálculos, en mi opinión algo chapuzas para el caso de al menos uno de los lados impar. Pero después me di cuenta que no hace falta. Así que se puede demostrar el desafío en cualquier tipo de tablero, y sin cálculos. Sólo con algunos razonamientos, pero claro hay que caer…como siempre. Espero ver la demostración que ponen en elpais por curiosidad. PD: dudo haberlo resuelto de no ser porque… Lee más »
¿ El dibujo de 1 sola casilla serviría como dibujo imposible ?
rolo Vale cualquier dibujo, el de una sola casilla es perfectamente válido pero yo me centraría en buscar dibujos que se puedan hacer de dos formas diferentes.
sive, con un poco de fuerza bruta he calculado las clases del 4×4 y son 16. Me ha sorprendido un número tan alto, no me imagino los valores que pueda tomar en tableros como el 24×24.
Con respuesta a Auditorcillo. No es una conjetura que la segunda se deduzca de la primera. Es demostrable. A partir de que sabes que hay una que no es constructible intenta demostrar que para cada una constructible puedes asociarle una no constructible de modo inyectivo. El como hacer dicha asociación es cuestión de pensarlo un poco.
Una vez probado eso, el resto es inmediato.
Mmonchi, mira: http://oeis.org/A075462
¡Qué bueno, Migue! ¡Gracias! Lo malo es que no le encuentro ninguna lógica.
Mnonchi Quizá a esto si se la veas: http://www.millstone.demon.co.uk/games/lightsout/start.htm 😉
Joselo, con la práctica que tengo ya, acabo de pasarme los 15 niveles del juego. 🙂
Bueno, pues el que mas me costó de todos ya esta hecho! (por algo seria el ultimo) A ver, la pista de usar las imagen dada en el enunciado no me sirvio para nada, solo me ha distraido un monton. Lo que de verdad me ha servido ha sido el juego de David!! Muchas gracias! (tuve que jugar mucho hasta apagar el tablero!) Solo tras resolverlo ahora veo una manera de usar la imagen pero me parece como minimo igual de embrollada que partiendo de la nada (tal vez mas determinista, eso si). Enhorabuena y gracias a los del Pais… Lee más »
– Usando la imagen que nos dan, se ve para tableros [24,24]
– Sin usar la imagen que nos dan, se ve para algunos casos más generales
[5n-1, 5m-1] (que en particular sirve para [24,24])
[2n-1, 3m-1]
[4n-1, 3m-1]
– El caso general, [n, n] a partir de un cierto n, creo que no se puede probar, porque hay casos de n grande (>24) con sólo una clase de tableros.
– Parece ser que para cualquier N, el tablero NxN todoapagado y el todoencendido están en la misma clase
jesusc, he comprobado tu hipótesis de que todo apagado y todo encendido están en la misma clase para los tableros de 4×4(16 clases), 5×5 (4), 9×9 (256) y 19×19 (65536). Lo he hecho mediante un método constructivo, aprovechando en parte la solución anterior, aunque no puedo afirmar (de momento) que funcione siempre. Pero el hecho de que en el tablero de 19×19 con 65536 clases los dos tableros uniformes estén en la misma es difícil que sea casualidad.
Es fácimente demostrable que el nº de clases de cualquier tablero NxM está acotado por 2^N para N<=M
Sí, Juanjo, lo que no sé es cómo calcular el valor real. Y debe ser «relativamente fácil» si alguien ha calculado que para 991×991 hay 2^640 clases, pero me gustaría saber de qué forma se llega a esos resultados:
http://oeis.org/A075462/b075462.txt
Se puede acotar mas y para N>4 la cota la tengo en 2^(N-2) por ahora
Y tras una nueva pensada, olalá, me sale que para cualquier tablero la cota máxima es 4 (o 2 si N es impar)