La Real Sociedad Matemática Española y El País nos traen nuevos Desafíos Matemáticos, 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 Adolfo Quirós, profesor de la Universidad Autónoma de Madrid (UAM) y vicepresidente de la RSME que, aparte de ser uno de los principales responsables de estos desafíos, también colaboró con los Desafíos GaussianosyGuijarro planteando el sexto de ellos.
Como podéis ver en el título de este post, el problema se titula Números a la parrilla, 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:
Empezamos con una parrilla 4×4 que en cada casilla tiene un 1 o un -1. El juego consiste en cambiar los valores de algunas casillas, siguiendo las reglas que se darán, y se gana si se consigue que haya un 1 en todas las casillas.
Se puede jugar con dos reglamentos distintos:
– Reglamento ACB (el más estricto): se pueden cambiar simultáneamente los valores de todas las casillas de una fila, de una columna, o de una de las dos diagonales.
– Reglamento NBA (más laxo): además de los movimientos autorizados por las reglas ACB, son también válidos los movimientos que consisten en cambiar simultáneamente los valores de todas las casillas de una recta paralela a una de las dos diagonales, incluido cambiar sólo el valor de una esquina.
Consideramos dos situaciones iniciales que pueden verse en esta figura
Para cada una de ellas nos preguntamos si se puede ganar, y cómo, con cada una de los reglamentos. Así que el desafío es cuádruple: para cada una de las dos posiciones iniciales, y con cada uno de los dos reglamentos, dar la cadena de movimientos que permite ganar la partida o demostrar por qué no se puede.
Para considerar como válida una respuesta no basta con que la solución sea la correcta, hay que explicar cómo se ha llegado a ella.
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 desafiodeagosto1@gmail.com antes de que termine el lunes 4 de agosto.
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á 😉
¡Qué parida(d)! «:^)
Sí, este de la parrilla es facilito… sobre todo 3 de los casos, el cuarto un poco menos pero se consigue.
El caso b) de NBA es el que a mi me ha costado un poco más.
Para la solucion formal se puede recurrir la secuencia de Thue-Morse:
http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence
que da lugar a la constante de Prouhet–Thue–Morse = 0.412454033640…
que es trascendental y hasta aparece en el conjunto de Mandelbrot, muy interesante
la parrilada!!!
😉
Información Bitacoras.com
Valora en Bitacoras.com: La Real Sociedad Matemática Española y El País nos traen nuevos Desafíos Matemáticos, 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 A…
Fácil pero bonito, que es justo lo que deben ser estos desafios.
Los 3 primeros fáciles, el 4º …. estoy en ello
Bueno, ha costado, pero al final también ha salido el 4º. Fleices vacaciones a todos
Bueno, con mi comentario anterior no quería desmerecer el desafío … Era solo un intento, no demasiado afortunado, de hacer un juego de palabras con la idea clave en la resolución. Coincido plenamente con que es interesante y asequible, muy adecuado para estos desafíos en El País.
¿ Pista ?
Ya estaba en el primer mensaje: PARIDAD
No lo veo. Me esperaré a la solución
Alguien tiene que modular esto, jm.
😉
Juanjo Escribano:
Para mí, lo difícil no fue hallarlo, sino comprobarlo. Jejeje.
Os dejo una versión interactiva para poder juguetear:
http://cofres.site11.com/david/elpais/20140730.htm
(No destripa nada ni da ninguna pista. Sólo es el tablero con las reglas dadas).
¿Cuantas parrillas nba-distintas hay?
A mi me salen 4 distintas, creo.
una de ellas con 2 casillas -1, dos con una casilla -1, y la que no tiene ningun -1.
jesusc, ¿te refieres a parrillas distintas si consideramos iguales aquellas en las que se puede ir de una a la otra con movimientos legales (es decir, con esa relación de equivalencia)?
Si es eso, juraría que son dos solamente, en el caso de las reglas NBA.
Y en el caso de las reglas ACB es mucho más complicado. Con un 50% de intuición y otro 50% de razonamiento, diría que son 64 parrillas diferentes ACB… pero tendría que pensarlo más para estar seguro.
sive, sì me refería a eso.
el caso acb no me lo habia planteado porque como div
ces es mucho mas complicado.
A ver si me acuerdo las 4 que me salian:
(1)
++++
++++
++++
(2)
++++
++++
+-++
++++
(3)
(4)
++++
++++
+-++
+-++
Hola,
Inventé un algoritmo para resolver cualquier parrilla con las reglas NBA, siempre que se pueda, claro. Os animo a pensar un algoritmo de ese tipo. Con ese algoritmo es fácil ver que se puede pasar del 2 de jesusc al 1 de jesusc… Diagonal de 3 que contiene al -1… Fila4, Columna1, Diagonal de 2. Ya.
Coincido con Sive en el número 2.
david, muy chulo, si le pusieras colores se veria mucho mejor!
jesusc, supongo que la 1 son 16 signos +, solo veo 12.
Tambien se te ha pasado poner la (3). Creo que esta:
++++
++++
++++
+-++
y tambien creo que son 4.
sive, 64 me parecen muchas… voy a pensarlo.
sive y rtomas, a ver si ahora escribo bien las 4 que me salían
acido, tienes razón, se puede pasar de la (2) a (1); y también se puede pasar de la (3) a la (4). Así que serán sólo 2.
(1)
++++
++++
++++
++++
(2)
++++
++++
+-++
++++
(3)
++++
++++
++++
+-++
(4)
++++
++++
+-++
+-++
Si, teneis razon, me he puesto a pensarlo y sive tiene una gran intuicion. Yo tambien encuento 64 para el caso dificil con el siguiente calculo:
aqui la formula:

bueno, aunque el 64 es solo un límite superior. El numerador
es el total de tableros diferentes y el denominador es una cota mínima al número de derivados de un tablero con las 10 operaciones de ACB. Tal vez haya más derivados, lo que reduciría el 64…
Que opinas, sive?
Para acabar con el spam (perdon por usar tantos mensajes), los límites de la suma tenian que haber sido 0 y 10. Entonces el denominador es sencillamente
.
Buenas noches.
rtomas,
entiendo lo del numerador (número total de tableros diferentes), pero variantes de un tablero quizá sean menos de 2^10.
Por ejemplo cambiando las 4 filas se obtiene el mismo tablero que cambiando las 4 columnas.
Y otro ejemplo, cambiando las 4 filas más las 4 columnas se obtiene el tablero original.
rtomas lo pensé de forma diferente. Primero busqué subconjuntos de casillas en los que se conservara la paridad. Hay muchos, así que intenté eliminar aquellos en los que la paridad quedara fijada al establecer la paridad del resto. El objetivo, claro, era quedarme con unos subconjuntos cuya paridad fuera independiente de la de los demás, o que no lo fuera pero encontrar un criterio que me permitiera conocer cuantas veces estaba contando la misma parrilla. Y es en este proceso en el que me dejar llevar por la intuición, porque no se me ocurrió una forma fácil. Aunque aún no… Lee más »
jesusc, pues si, debe haber menos tableros derivados de
, de hecho solo me asegure que algunas formas triviales de repetir tableros no ocurrieran (como deshacer el camino hecho para volver a la original). En efecto combinaciones de operaciones totalmente diferentes te pueden llevar al mismo tablero. Asi que habra mas de 64, como sive concluye ahora.
Bueno, parece ser que el orden de magnitud esta bajo control! 😉
rtomas, si te fijas, tu enfoque permite obtener cotas máximas, mientras que el mío asegura cotas mínimas.
Si nos encontramos en el medio… ¡habremos demostrado cuantas parrillas hay!
Como me encanta apostar (sin dinero), yo diría que nos vamos a encontrar en
.
sive, una forma fácil de ver que como máximo hay 2^8:
partes de una parrilla cualquiera y siempre puedes dejar todo unos en la primera fila y en la primera columna y en otra casilla. Quedan 8 casillas que no sé asegurar dejar un 1 sin desmontar las 8 en las que ya tengo un uno. Así que 2^8 posibilidades.
++++
+xx+
+xxx
+xxx
Para las resolubles tengo el método de las NBA y solo hay dos tipos de clases: resolubles y no resolubles.
De las ACB no lo he pensado dado que la pregunta era bastante fácil en ese caso. Lo intento pensar un rato
Dejo para mañana las clases ACB pero creo que lo que indica Jesus es erróneo por falta de mas clases. No lo marco por no dar pistas antes de la fecha límite
juanjo, lo que yo decía es que desde cualquier parrilla aplicando reglas ACB podemos llegar a una de este tipo:
++++
+xx+
+xxx
+xxx
y de este tipo como máximo hay 2^8 (cada una de las 8 casillas «x» pueden ser «+» o «-«).
Así que el número de parrillas acb-distintas es menor o igual que 2^8 = 256.
Por otra parte, contándolas como hace rtomas, sabemos que es mayor que
2^16 / 2^10 = 2^6 = 64.
Mayor que 64 y menor o igual que 256.
Y se me acaba de ocurrir que quizá sea mas fácil pensar en cuantas soluciones distintas se pueden generar de la solución raiz de una clase teniendo en cuenta que solo hay 10 movimientos posibles (4h, 4v y 2d) y que el orden no importa.
Sin cambio 1 C(10,0)
Con 1 cambio 10 C(10,1)
Con 2 cambios C(10,2)
…
Con 9 cambios 10 C(10,9)
Con 10 cambios 1 C(10,10)
1+10+45+120+210+252+210+120+45+10+1 = 1024, pero ojo que al menos con 8 cambios hay una solución que vuelve a la incial cambiando 4h y 4v.
No jesusc, rtomas calcula bien que el máxino es 64 y yo indico la salvedad del caso cambiar todas las filas y columnas y vuelvo a la posición inicial.
Digo que no estoy de acuerdo en que sean 4 por que hay un error conceptual que lo diré mañana por ser pista de las soluciones y sin estar 100% seguro de cuantas salen pongo una no generable por tus 4 soluciones, luego sin verificar si las tuyas están bien o mal a tus casos hay al menos una mas
Buena, jesusc, tu idea deja el máximo en 256.
Hay dos juegos al menos de 6 movimientos que te llevan también a la posición inicial:
las 2 diagonales + 2 verticales extremas y dos horizontales del centro
las 2 diagonales + 2 horizontales extremas y dos verticales del centro
rtomas, ya tiene colorines.
Bueno, monocromo, que me gusta a mí más. 😛
En respuesta a Juanjo Escribano
«»»
Hay dos juegos al menos de 6 movimientos que te llevan también a la posición inicial:
las 2 diagonales + 2 verticales extremas y dos horizontales del centro
las 2 diagonales + 2 horizontales extremas y dos verticales del centro
«»»
Eso quiere decir que una de la seis operaciones se puede expresar usando las demás. Por ejemplo una diagonall sería el resultado de multiplicar dos filas extremas por dos columnas centrales por la otra diagonal.
Con la aportación de JoseLo, podemos considerar que tenemos 9 movimientos en lugar de 10, ya que la antidiagonal se puede hacer con otros 5 movimientos
D2 = F1 + F4 + C2 + C3 + D1
y entonces con el cálculo de rtomas, tenemos que el número de parrillas acb-distintas es mayor que 2^16 / 2^9 = 2^7 = 128.
Así que mayor que 128 y menor o igual que 256. (Ya está casi, sive).
David, estupendo, gracias, mucho mejor y muy práctico!!
Jesusc, JoseLo, muy interesante! Pero se os olvido que una fila también se puede suprimir
pues ya se dijo arriba que 4filas+4columnas es la identidad. Así que una fila se puede sustituir por las otras 3 filas mas las 4 columnas. En conclusión solo quedan 8 movimientos independientes:
2^16 / 2^8 = 2^8 = 256
Por lo que este problema ya está rematado, la solución es exactamente 256 clases de soluciones!
La parrillada esta ha dado para mucho!
sive, tu gran intuición no te fallo! Tal y como apostaste nos encontramos en el medio
.
Respuesta para rtomas
«Por lo que este problema ya está rematado, la solución es exactamente 256 clases de soluciones!»
Creo que también se puede llegar a esa conclusión considerando las simetrías de rotación y reflexión especular.
Y otra cosa: si hay 256 clases de equivalencia entonces una parrilla sólo tendría solución si pertenece a la misma clase de equivalencia que la identidad.
¡Buena rtomas!, has sido el primero en cruzar la meta. Y a los demás también por las aportaciones. Ahora que ha pasado el plazo para el desafío, puedo hablar de como obtuve mis cotas mínimas. No lo podía hacer antes porque habría sido una pista excesiva para el caso B con reglas NBA. Hay doce subconjuntos de 4 casillas, que conservan la paridad con cualquier movimiento ACB, que son: AABB EFFE IJIJ AABB GHHG KLKL CCDD GHHG IJIJ CCDD EFFE KLKL Empezando por los conjuntos A, B, C y D, se ve claramente que al menos hay 16 clases de… Lee más »
Ahi va mis razonamientos: Llamaré a,b,c,d a las columnas y 1,2,3 y 4 a las filas Divido la parrilla en 3 grupos: Las 4 casillas centrales “C” (b2,b3,c2,c3) Las 8 casillas centrales del perímetro “P” (a2,a3, b4,c4, d3,d2, c1,b1) Los 4 vértices “V” (a1,a4,d1,d4) Caso NBA. Lo resuelvo en 3 pasos 1.- Positivizar las casillas “C” Cada casilla “C” pertenece a una diagonal de longitud 3 por lo que las que estén en negativo las paso a positivo cambiando la diagonal de longitud 3. B2 con a3,c1 B3 con a2,c4 C2 con b1,d3 C3 con b4,d2 2.- Positivizar las casillas… Lee más »
Pues sí, rtomas, está rematado, para acb hay 256 clases, cada clase con 256 parrillas.
Si las parrillas A y B se eligen al azar, lo más probable es que ninguna de ellas se pueda resolver con reglas ACB (sólo una de cada 256 se puede), y lo más probable es que una de ellas se pueda resolver con reglas NBA (una de cada 2 se puede).
Perdon, el resultado no varia pero P es diferente segun el caso:
Resoluble “C” y “V” P=1,2,3 si «C»+»V» multiplo de 4 o P=1,3,4 si no lo es
Irresoluble “C” y “V” P = 1,2,3
Irresoluble “C” y resoluble “V” P=2,3,4
Resoluble “C” e irresoluble “V” P =2,3,4
y en cada caso en nº no mencionado (0,x)
En mi opinión que haya 2 soluciones de 6 y una de 8 que generan nulo no elimina elementos independientes sino que hace que un subconjunto de las soluciones de 6,7,8,9 y 10 sean repetición de la solucion y de clases de parrillas de 0,1,2,3 y 4 elementos independientes, es mas si no me he equivocado en mi desarrollo el Nº de clases es impar.
2 comentarios sobre mis escritos: Creo que en el tema de clases ACB aunque la idea es incompleta es válida. Las combinaciones de 6 y 8 que que vuelven a la posición inicial hacen que: la única combinación posible sea igual a una de 2 movimientos y a una de 4 movimientos, que tendrá que ser la misma lo que quiere decir que hay combinaciones de 4 y 2 que pasan a ser de la misma clase, lo que desmonta varios comentarios. Lo mismo con las de nueve que al menos hay una de 6 o una de 9 incliuda… Lee más »
rtomas, Sive, llegué a la misma conclusión: 256 clases de equivalencia de 256 elementos cada una.
Juanjo, tu algoritmo de resolver NBA es igual al mio: resolver centrales, resolver perímetro central y resolver esquinas.
En cuanto a ACB estás equivocado, quizá no veas todavía por qué están garantizadas las 256 clases con 256 elementos pero sí están garantizadas.