Desafíos Matemáticos en El País Verano 2014 – Desafío 5: “Una carita feliz”

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.

Autor: gaussianos

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

77 Comentarios

  1. Muy bonito el problema pero todavía no me ha salido. Hay que pensar.

    Publica una respuesta
  2. 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. ¿?

    Publica una respuesta
  3. 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.

    Publica una respuesta
  4. 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)

    Publica una respuesta
  5. 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

    Publica una respuesta
  6. 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.

    Publica una respuesta
  7. 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 😉

    Publica una respuesta
  8. 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.

    Publica una respuesta
  9. 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

    Publica una respuesta
  10. Hola DIAMOND,

    El correo destino hace referencia al problema 4 ¿Es ok o hand error?

    Salud

    Publica una respuesta
  11. diamond, también has puesto UAM como siglas de la complutense

    Publica una respuesta
  12. Vaya tela… Es que copié el texto del desafío anterior y olvidé rectificar algunas cosas. Gracias por el aviso Wachino :-).

    Publica una respuesta
  13. 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).

    Publica una respuesta
  14. 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.

    Publica una respuesta
  15. 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.

    Publica una respuesta
  16. 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…

    Publica una respuesta
  17. 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?

    Publica una respuesta
  18. 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…

    Publica una respuesta
  19. 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.

    Publica una respuesta
  20. 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 el enunciado inicial, ¿que es grande?, ¿sirve para cuadrados NxN con N a partir de 4?

    Publica una respuesta
  21. 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.

    Publica una respuesta
  22. 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).

    Publica una respuesta
  23. 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 para el desafío, sólo es intriga mía personal)

    Lo que afirmo y quizá alguna cosa más está en la “Nota importante” que está al final del propio enunciado, la cual ya que está disponible para todos los lectores de dicho enunciado y no está aquí en Gaussianos, así que si alguien no lo vio quizá le resuelva dudas.

    Por último, también quería comentar que me parece un desafío muy interesante. Muy “digital”, relacionado con imágenes y a la vez con juegos. No se, pero siendo entretenido como otros desafíos además me dio la impresión de ser bastante práctico para el mundo digital en el que vivimos.

    Publica una respuesta
  24. 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.

    Publica una respuesta
  25. 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.

    Publica una respuesta
  26. 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.

    Publica una respuesta
  27. Lo habremos hecho diferente. Eso es bueno, lo mismo sacamos algo mas entre todos a partir del martes.

    Publica una respuesta
  28. 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

    Publica una respuesta
  29. 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?)

    Publica una respuesta
  30. 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 ponen la imagen de la cara y de las casillas al lado…

    Publica una respuesta
  31. 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.

    Publica una respuesta
  32. 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.

    Publica una respuesta
  33. 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.

    Publica una respuesta
  34. ¡Qué bueno, Migue! ¡Gracias! Lo malo es que no le encuentro ninguna lógica.

    Publica una respuesta
  35. Joselo, con la práctica que tengo ya, acabo de pasarme los 15 niveles del juego. 🙂

    Publica una respuesta
  36. 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 y a Gaussianos y a todos los que comentais!!!!

    Publica una respuesta
  37. – 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

    Publica una respuesta
  38. 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.

    Publica una respuesta
  39. Es fácimente demostrable que el nº de clases de cualquier tablero NxM está acotado por 2^N para N<=M

    Publica una respuesta
  40. 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

    Publica una respuesta
  41. Se puede acotar mas y para N>4 la cota la tengo en 2^(N-2) por ahora

    Publica una respuesta
  42. Y tras una nueva pensada, olalá, me sale que para cualquier tablero la cota máxima es 4 (o 2 si N es impar)

    Publica una respuesta
  43. Juanjo, en el de 4×4 hay 16 clases, contadas mediante fuerza bruta. Además coincide con la serie del OEIS.

    Publica una respuesta
  44. Perdón de nuevo, en todos los casos la cota es 4 y para N>3
    Para N=1 y 2 la cota es 1 pues todos los tableros son solucionables
    Para N=3 es 2 clases todo apagado y todo encendido

    Publica una respuesta
  45. Y por ser un método constructivo es lo mismo para cualquier tablero NxM con N>3 y N<M

    Publica una respuesta
  46. Juanjo, para N=3 solo hay una clase, todo apagado y todo encendido pertenecen a la misma. Lo puedes comprobar pulsando en un tablero de 3×3 todo apagado las cuatro esquinas y el centro, obteniendo un tablero todo iluminado.

    Publica una respuesta
  47. Mañana contaré como he llegado a esa conclusión. Si has jugado como dices lo verás muy claro. Como siempre puedo estar equivocado pero me gusta la solución.

    Me ha hecho recordar que tuve este juego con un tablero 5×5 y terminé todos los niveles y escribiendo esto he descubierto mi error, jaja, dejo la cota en 2^N

    Publica una respuesta
  48. Mmonchi,

    aunque no parece de fácil lectura, aquí está probado lo de que se puede pasar siempre de todoapagado a todoencendido (The All-Ones Problem) en cualquier NxN:

    http://www.dcc.fc.up.pt/~rvr/resources/Aulas-Babel/MAPI-AA/The-Mathematical-Intelligencer-1989-Sutner.pdf

    Sobre lo del número de clases de los tableros NxN, me conformo con saber que está entre 1 y 2^N, y que en [24,24] y muchos otros que también sabemos es mayor o igual que 2. Es posible que 2^N sólo se alcance en el 4×4.

    Publica una respuesta
  49. Pasado ya el tiempo, cuento como lo hice yo (la primera parte usando el dibujo como decía).

    Para probar que hay al menos una combinación de luces que no se puede obtener utilizaremos la imagen de la carita sonriente que se nos da en el desafío. Antes de nada introducimos notación: Llamamos “cuadro de pulsaciones” a una matriz 24×24 donde cada elemento puede indicar que dicha casilla ha sido pulsada o no lo ha sido (pulsar 2 veces la misma casilla es equivalente a no pulsarla, evidentemente) notemos que hay 2^{(24×24)}=2^576 posibles “cuadros de pulsaciones”. Llamamos “cuadro de luces” a un cuadrado análogo al de pulsaciones donde cada elemento indica si esa casilla está iluminada o no. Es también evidente que hay 2^(24×24)=2^576 posibles “cuadros de luces”. Hay una función evidente (pues es usar las reglas del juego) que lleva cada cuadro de pulsaciones en el cuadro de luces asociado.

    La primera parte nos pide ver que existe un cuadro de luces que no se obtiene mediante ningún cuadro de pulsaciones. Como hay tantos cuadros de luces posibles como cuadros de pulsaciones, el problema equivale ver que existen al menos dos cuadros de pulsaciones que dan lugar al mismo cuadro de luces. La carita sonriente de la imagen dada se puede obtener con el cuadro de pulsaciones (sea A) que aparece también en la imagen dada. No obstante, el cuadro de pulsaciones (sea B) que se obtiene de A haciéndole (en notación matricial) b_{i,j}=a_{i,24-j} genera evidentemente la misma carita sonriente. Pero B es distinta de A (pues no era cierto que a_{i,j}=a{i,24-j} para todo i,j de 1 a 24). Entonces como hay dos cuadros de pulsaciones (el dado y una especie de “simétrico o reflejado”) que dan lugar a un mismo cuadro de luces (carita sonriente) hay un cuadro de luces que no se obtiene mediante ningún cuadro de pulsaciones. Llamemos a ese cuadro de luces irrealizable C.

    Para la segunda parte definimos una operación entre cuadros de luces denotada por *. Dados dos cuadros de luces X,Y el cuadro de luces Z=X*Y es un cuadro en el que z_{i,j} está encendido si uno y solo uno de x_{i,j} y y_{i,j} estaban encendidos. z_{i,j} está apagado si o bien x_{i,j} y y{i,j} estaban ambos encendidos o bien x_{i,j} y y{i,j} estaban ambos apagados. Se puede ver que de hecho el conjunto de cuadro de luces es un grupo abeliano con esa operación donde cada elemento además es su propio inverso. La cuestión es que recordando quien era C sabemos que si X es un cuadro de luces constructible S=C*X no lo es, pues si S fuese constructible C=S*X (al ser X=X^-1) C sería constructible por ser operación entre constructibles (basta primero hacer las pulsaciones de X y luego las de S). Como eso no puede pasar, S necesariamente es no constructible. Además la asociación es inyectiva pues si C*X=C*Y se tiene evidentemente (por ejemplo, por ser un grupo) X=Y. Este resultado implica que al haber una no constructible por cada una sí constructible hay un número mayor o igual de no constructibles que de sí constructibles. Eso implica que a lo sumo la mitad son constructibles evidentemente y la mitad o más no lo son. Notemos que para esta segunda parte es imprescindible utilizar el cuadro no constructible C (que era el resultado de la primera). Si no se puede garantizar eso puede suceder que todos los cuadros de luces sean constructibles como pasa por ejemplo en 2×2.

    Publica una respuesta
  50. Mi solución para la segunda parte difiere ligeramente y la relaciona con el tema de las clases mencionado anteriormente. En primer lugar, la operación que has denotado como “*” es la suma en Z2, así que lo habitual es usar el símbolo “+”. Llamemos N a A – B, es decir, a un cuadro de pulsaciones tal que A + N = B (o B + N = A, da igual). Se demuestra fácilmente que N es un cuadro de pulsaciones que no enciende ni apaga ninguna casilla. Cada cuadro de pulsaciones (distinto del trivial que no pulsa nada) que cumpla esa propiedad multiplica por dos el número de maneras equivalentes de obtener un mismo cuadro de luces. Por ejemplo, si hay dos cuadros N_1 y N_2, tenemos 2² clases, pues para cada cuadro de pulsaciones X, serían equivalentes X + N_1, X + N_2 y X + N_1 + N_2. En tableros como el de 2×2 o el de 3×3, todas las configuraciones son alcanzables porque no hay cuadros de pulsaciones no triviales que dejen todas las luces sin modificar.

    Publica una respuesta
  51. Alguien preguntaba más arriba que cómo se había calculado la secuencia con el número de clases para tableros nxn. Es relativamente sencillo: se modela el problema de resolver un tablero como un sistema de ecuaciones lineales en nxn variables y se analiza si está sobredeterminado, y en qué medida. En otras palabras, el que haya generado la secuencia muy posiblemente se habrá ayudado de un programa para generar matrices a partir de las reglas del juego, más un software estándar de álgebra lineal.

    Publica una respuesta
  52. Otra cosa más: si sabemos que para un cierto tamaño n existen N_1…N_k cuadros de pulsaciones “inefectivos”, los cuadros de luces alcanzables son exactamente aquellos que tienen un número par de luces encendidas en las posiciones pulsadas de cada N_i. Por ejemplo:

    oXXo
    XooX
    XooX
    oXXo

    es uno de los cuadros de pulsaciones sin efecto para 2×2. Eso nos basta para saber que el cuadro de luces

    0010
    1000
    1000
    0000

    no es construible a partir del tablero apagado.

    Publica una respuesta
  53. Arriba, donde digo “multiplica por dos” debería decir “puede multiplicar por dos”. En los casos en los que hay cuadros nulos que son combinaciones de otros, la potencia de dos se reduce. Por ejemplo, los cuadros nulos para 5×5 son 4:

    ooooo
    ooooo
    ooooo
    ooooo
    ooooo

    ———-
    XXoXX
    ooooo
    XXoXX
    ooooo
    XXoXX

    ———-
    XoXoX
    XoXoX
    ooooo
    XoXoX
    XoXoX

    ———-
    oXXXo
    XoXoX
    XXoXX
    XoXoX
    oXXXo

    pero uno es el cuadro vacío, y de los otros tres uno es suma de los otros dos.

    Publica una respuesta
  54. Para el caso “general” [5n-1,5m-1].

    Como ha explicado Daniel, basta encontrar 2 “cuadros de pulsaciones” diferentes que den lugar al mismo “cuadro de luces” (es decir, al mismo dibujo).

    En particular sirve con encontrar uno que no encienda ninguna luz, porque ya tendremos 2, el encontrado y el trivial.

    Cogemos uno de los que cumple la propiedad para 4×4, por ejemplo

    oXXo
    XooX
    XooX
    oXXo

    lo rodeamos con fila y columna desactivada, y lo repetimos (volteándolo) hacia la derecha y/o hacia abajo las veces que queramos.

    oXXoooXXo…
    XooXoXooX…
    XooXoXooX…
    oXXoooXXo…
    ooooooooo…
    oXXoooXXo…
    XooXoXooX…
    XooXoXooX…
    oXXoooXXo…
    …………………

    Publica una respuesta
  55. y usando la misma idea, si tenemos uno (i-1)x(j-1) que cumple la propiedad, repitiéndolo lo tenemos para (in-1)x(jm-1).

    y así se ven por ejemplo los casos

    [2n-1, 3m-1]
    [4n-1, 3m-1]

    a partir del 1×2

    XX

    y a partir del 3×2

    Xo
    XX
    Xo

    Publica una respuesta
  56. jesusc, yo lo que buscaba eran soluciones de dibujo simétrico que no fueran simétricas, lo que me garantizaría que existían dos soluciones para ese dibujo. Esto es así para los demás dibujos, pero para el de todo apagado ya teníamos una, la trivial, como bien dices. Lo que he conseguido probar es que para (3m-1,2n-1) hay dos soluciones para un mismo dibujo, la que se muestra y la simétrica:

    OX, OXOOX, OXOOXOOX, …

    OX, OXOOX, OXOOXOOX,
    OO, OOOOO, OOOOOOOO,
    OX, OXOOX, OXOOXOOX, …

    OX, OXOOX, OXOOXOOX,
    OO, OOOOO, OOOOOOOO,
    OX, OXOOX, OXOOXOOX,
    OO, OOOOO, OOOOOOOO,
    OX, OXOOX, OXOOXOOX, …

    En otros casos existe simetría vertical y horizontal, lo que me permite afirmar que hay un mínimo de cuatro clases.

    Publica una respuesta
  57. jesusc, yo lo que buscaba eran soluciones de dibujo simétrico que no fueran simétricas, lo que me garantizaría que existían dos soluciones para ese dibujo. Esto es así para los demás dibujos, pero para el de todo apagado ya teníamos una, la trivial, como bien dices. Lo que he conseguido probar es que para (3m-1,2n-1) hay dos soluciones para un mismo dibujo, la que se muestra y la simétrica:

    OX, OXOOX, OXOOXOOX, …

    OX, OXOOX, OXOOXOOX,
    OO, OOOOO, OOOOOOOO,
    XO, XOOXO, XOOXOOXO, …

    OX, OXOOX, OXOOXOOX,
    OO, OOOOO, OOOOOOOO,
    XO, XOOXO, XOOXOOXO,
    OO, OOOOO, OOOOOOOO,
    OX, OXOOX, OXOOXOOX, …

    En otros casos existe simetría vertical y horizontal, lo que me permite afirmar que hay un mínimo de cuatro clases.

    Publica una respuesta
  58. Hola,

    Con este desafio he conocido este sitio que esta muy bien. A ver si algun dia tengo tiempo de concocerlo mas en profundidad.

    Es la primera vez que escribo aqui.

    Yo tenia una solucion completamente diferente para este problema. Lo tengo escrito en un PDF pero no sé si se pueden adjuntar ficheros.

    Igual es algo rebuscado pero alla va:

    Para la primra pregunta: si partimos de la cuadricula vacia y apretamos una celda al lado de una esquina tenemos 4 casillas que se encienden (la de la esquina es una de ellas). Si acto seguido apretamos la celda que esta al otro lado de la esquina tenemos 4 casillas que cambian de estado (la de la esquina es una de ellas y se apaga).

    Podemos identificar 6 casillas que han sufrido cambios al hacer estas dos pulsaciones.

    Ademas al hacer estas dos pulsaciones la casilla de la esquina esta apagada.

    Asi pues podemos decir que la esquina tiene que estar forzosamente apagada si queremos que las otras 5 casillas de ese grupo esten como lo estan ahora. En otras palabras, es imposible un grupo de 6 casillas identico al que acabamos de hallar pero con la casilla de la esquina encendida.

    Asi pues cualquier cuadricula que tuviera este grupo es una cuadricula prohibida. Y para cualquier dimension (bueno, al menos una 3×3).

    Para la 2a pregunta, he encontrado otras tres combinaciones de 6 casillas en las esquinas que son imposibles de hacer. Si tenemos en cuenta las combinaciones que se pueden hacer para las 570 casillas restantes en cada caso y que cada grupo imposible de 6 casillas lo puedo poner en cualquiera de las 4 esquinas, ya he encontrado las 2^(575) combinaciones imposibles.

    Nota 1: Repito lo tengo en PDF pero no sé como haceroslo llegar de una forma sencilla.
    Nota 2: Perdon por las faltas de ortografia pero escribo desde un teclado extranjero.

    Publica una respuesta
  59. Perdon,

    Creo que me he equivocado. Deberia encontrar 8 combinaciones imposibles de 6 casillas y ubicables en 4 lugares distintos para sacar las 2^(575) combinaciones imposibles pero si tan solo encuentro 4 acabo teniendo 4x4x2^(570) es decir, 2^(574) combinaciones imposibles.

    Ya hasta dudo de mis combinaciones imposibles 🙂

    Antonio

    Publica una respuesta
  60. Antonio,

    no sé si he entendido con claridad lo que dices pero pulsando b2,b3 y d1 como el juego de barcos creo que esas 6 casillas quedan como indicas, el resto no.

    Publica una respuesta
  61. Hola Juanjo,

    Con la combinacion que propones, la casilla de la esquina (a1) queda apagada y es imposible que esté encendida si queremos que las otras cinco sigan como estan (b1 encendida, c1 encendida, a2 encendida, b2 apagada y a3 encendida)

    Antonio

    Publica una respuesta
  62. No sé si entiendo bien lo que estás diciendo, pero eso implicaría que cualquier tablero mayor o igual que 3×3 tiene más de una clase. Yo creo que eso no es así.

    Publica una respuesta
  63. hola, revisando el blog de Terry Tao, aparecieron dos demostraciones independientes de la conjetera hecha por Erdos sobre large gaps en primos (c0 se puede tomar arbitrariamente largo) . Es espectacular!! para que hagan eco de la noticia 🙂

    Publica una respuesta
  64. Hola Golvano,

    Disculpa por la tardanza en responderte.

    Primero de todo, decirte que no estoy familiarizado con el concepto de ‘clase’ para matrices. Veo que lo abordais en este foro y cuando tenga un poco de tiempo lo estudiaré con calma 🙂 .

    Lo unico que quiero decir es que si queremos que b1 esté encendida, c1 encendida, a2 encendida, b2 apagada y a3 encendida forzosamente a1 tiene que estar apagada.

    A menos que me esté equivocando.

    Saludos.

    Antonio

    Publica una respuesta
  65. ¿No es esto un contraejemplo?

    XXX –> XXX
    X0X –> X00
    XX0 –> X00

    Lo que quería decir es que tu afirmación implica que cualquier tablero mayor o igual que 3×3 tiene posiciones que no se pueden conseguir. Si no estoy equivocado, para 3×3, se pueden conseguir todas las posiciones.

    Publica una respuesta
  66. Hola Golvano,

    Gracias por tu respuesta rapida.

    Ok, tienes razon, apretando las celdas que propones (izquierda) obtenemos la cuadricula de la derecha.

    Pensaba que no se podia.

    Saludos,

    Antonio

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - 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…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *