Nueva entrega de los problemas matemáticos de la edición digital de El País. Ayer jueves apareció el décimo de los 30 que se van a proponer aprovechando la celebración del Centenario de la RSME.
Este décimo problema se titula Cómo rellenar con piezas un tablero y lo propone María López Valdés, licenciada en Matemáticas y promotora de la empresa Bit&Brain Technologies. Podéis ver dicho problema haciendo click en este enlace.
Recordamos que se sorteará la colección de libros «Las matemáticas nos rodean» entre todos los que acierten el problema de cada semana. Si encontráis la solución y queréis participar, sólo tenéis que enviarla a problemamatematicas@gmail.com antes de que termine el lunes 23 de mayo.
Respecto al tema de los comentarios, os recuerdo mi opinión. 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 si queréis comentar dierais pistas, que hablarais de la forma de resolverlo, en vez de limitaros a dar la solución tal cual. Muchas gracias a todos.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: Nueva entrega de los problemas matemáticos de la edición digital de El País. Ayer jueves apareció el décimo de los 30 que se van a proponer aprovechando la celebración del Centenario de la RSME. Este décimo problema se……
En la segunda parte no sé si se supone que además de rellenar el tablero con el número máximo de fichas, si se supone que hay que demostrar que es el mayor número o no (me da la sensación que no hace falta). Por mi parte no se me ocurre cómo demostrar que lo que consigo es lo óptimo, así que le he dicho a mi ordenador que lo intente (primero programando en mathematica, al comprobar que era muy lento he tirado de C++ mirando tutoriales) y ha llegado a la misma conclusión que yo. Vamos, que solo consigo demostrar… Lee más »
¡Otro de los que a mí me gustan! Solución no evidente pero sencilla y breve de explicar y sin necesidad de tener grandes conocimientos de matemáticas (en este caso realmente pocos).
Creo que este problema nos ha recordado a todos al típico de rellenar un tablero de ajedrez con piezas de dominó (o versiones afines). Yo diría que tiene cierto parecido pero éste es más, cómo lo diría, tiene más sustancia, «más color».
A mí la única forma trivial de demostrarlo que se me ocurre es formando un sistema lineal sobre 224 ( 4 x 7 x 8 ) variables enteras…
A ver, la primera parte es fácil de resolver. Meter el número máximo de piezas posibles también es fácil (sale a la primera mientras no hagas cosas demasiado estúpidas 😀 ), pero demostrar que es el máximo es lo que yo no consigo de forma sencilla, solo a lo bruto con el ordenador. No obstante creo que no hace falta demostrarlo.
@Sara F., ¿has demostrado también que las fichas que consigues meter son el máximo?
Martin Gardner 21 de octubre de 1914 – 22 de mayo de 2010
Comparto la opinión de Sara 100%, aunque para la primera parte la pintura no hace falta.
@Carlos: Hay una forma bonita (y bastante estándar, dicho sea de paso) de ver que cierta cantidad de fichas es el máximo.
Me podríais dar alguna pista sobre como demostrar que en un determinado tablero al añadir x filas (o columnas) el resultado siempre aumentará en y (excepto en unas cuantas excepciones ); o mejor, que un tablero con un determinado tipo de número como filas (o columnas) nunca tiene esas excepciones.
@Gerard, pues algo así como con pinturas andaba yo pensando. Que rabia me da no sacar este sin fuerza bruta 😀 , pero bueno, aún queda tiempo.
Sacado ya de la forma fácil. Se me estaba resistiendo, bueno, ya me he quedado tranquilo 😀 . @Sara F. lo de más color, pues la verdad es que con 2 se puede también 😀 .
@Félix, yo al menos no entiendo lo que dices.
@Carlos, digamos que he ido provando tableros de diferentes tamaños de filas y columnas, descubrí varios patrones diferentes, cada uno para casos distintos, pero uno de ellos tiene excepciones por una especie de jerarquía. La pregunta era como podía yo demostrar que un patrón se cumple; es decir, que al aumentar X filas, habrá Y espacios vacíos más. Mi idea era que como Y es el minimo espacios vacios para ese determinado tablero, se provaría solo, pero podría poder ponerse otra ficha, es más, hay excepciones que lo consiguen. Tambien he descubierto que en un tablero de 2*k filas y… Lee más »
Quiero decir que he encontrado un contraejemplo a lo que he puesto antes de 2k filas…
@Carlos, Pues me has dejado intrigada con eso de que con dos también se puede. Yo lo hice con más (cuántos más ya es algo que no voy a decir). La verdad es que tengo ahora mismo demasiadas cosas en la cabeza para ponerme a pensar otra vez en el problema. Aún así, no sé si será mucho preguntar aquí, en público: ¿Dos colores con la misma disposición que en el tablero de ajedrez o no?
@Sara F., bueno, yo al principio le puse más colores, pero luego me di cuenta que para deducir lo que había que deducir, solo usaba 2 de ellos así que las casillas en las que usaba el resto, las dejo sin colorear 😀 . Vamos, que uso 2 colores, pero no coloreo todo el tablero. No creo que te cueste pillar lo que digo.
@Carlos, @Sara F., en realidad solo hace falta un color (además del blanco).
@Félix, en el caso de 2*x filas y 2*y columnas el mínimo es 4*min(x,y).
@Carlos. ¡Ah, claro! Entendido. Gracias.
Pues como dice Mmonchi, en realidad basta con un color y las sin colorear. Basta con coger el «menor» 😀
Respecto al mínimo es fácil encontrar la fórmula para los rectángulos 2*x,2*y+1 y 2*x+1,2*y+1. Sin embargo la fórmula que he puesto para 2*x,2*y no es correcta. He resuelto los de 2×2, 2×4, 2xn, 4×4, 4×6 y 6×6 dejando solo 4 sin cubrir, pero el de 6×6 se me resiste, necesito 8, y no veo cómo generalizar.
@Mmonchi, yo también tengo problemas con los tableros de filas y columnas pares. A falta de demostración, creo que los siguientes patrones se repiten siempre. Sea g el minimo posible de espacios vacíos de un tablero con los lados pares. g:par,par→par #pares sin contar el 0 g(x,y)=g(y,x) g(x,y)=4+g(x-2,y-4) g(x,x)=g(x,x+2) #Esta era la formula que comentaba arriba y que ya he arreglado g(x,x)+4=g(x+2,x+2) para x>=4 Pero tienen siempre preferencia estos patrones siguientes: g(2,2*k)=4 g(2,2*k+1)=2 Y el caso 4,4→4 para poder aplicar la recursividad: g(4,4)=4 Estos patrones se repiten, pero no se como demostrarlos.Por eso preguntaba más arriba como se podría demostrar… Lee más »
@Félix, de momento tengo que:
g(2,2*k)=4
g(4,2*k)=4
g(x+4,y+2)≤g(x,y)+4
Eso lleva a:
g(6,2*k)≤8
g(8,2*k)≤8
g(10,2*k)≤12
g(12,2*k)≤12
g(14,2*k)≤16
g(16,2*k)≤16
…
No considero que sea un resultado definitivo porque he encontrado g(6,6)=4. No sé por qué ni cuántas excepciones más encontraré a la regla anterior, por eso pongo ≤ en lugar de =.
Ya tenemos solución:
Un tablero (casi) completo por piezas
No me ha gustado nada la solución «oficial». Los argumentos son sencillos e ingeniosos, pero echa completamente por tierra la demostración cuando dice «es sencillo encontrar ejemplos en los que se pueden colocar 16 piezas en total». Luego sólo ha demostrado una cota inferior y superior a la pregunta. Una forma «trivial» (pero bruta y aburrida de hacer a mano) de resolver el problema es asignar a cada posible posición de pieza (hay 224 posiciones diferentes) una variable (digamos x1, x2, …, x224). Si cada variable debe ser 0 ó 1 (indicando que en esa posición hay pieza o no),… Lee más »
Jose Juan. No entiendo. Si das una cota superior y una inferior, y ambas coinciden, ¿no has encontrado la solución? ¿Dónde ves la pega? ¿Por qué echa por tierra la demostración? Además la solución del vídeo (o la del texto, porque son la misma) resuelve de un golpe todos los tableros nxn con n impar. Es cierto que la que tú das sirve para n par, pero dudo mucho de que al menos yo sea capaz de resolverlo a mano en cuanto n sea medianamente grande.
josejuan, yo pienso igual que Prodem, me parece que la demostración está bastante bien, es muy visual y es perfectamente correcta. Vamos, que me ha gustado :D.
«Si das una cota superior y una inferior, y ambas coinciden» El problema es que no coinciden… (su prueba de que existe una solución con 16 piezas colocadas, es por exhaución, no por acotación), su única cota inferior es «mayor que uno» (celdas vacías). «Es cierto que la que tú das» No, mal que me pese no he dado una demostración, he utilizado una herramienta muy poderosa (programación lineal entera) para resolver el problema «a cañonazos». Insisto, no hay demostración (o yo no la veo y agradecería aclaración). NOTA: en problemas anteriores (y aun siendo formalmente demostraciones válidas) no se… Lee más »
josejuan, no se pueden colocar más de 16 piezas porque hay 16 casillas cuyas 2 coordenadas son pares y cada pieza tiene una (y solo una) casilla cuyas 2 coordenadas son pares.
Esta es la versión bicolor aludida en anteriores comentarios y la que pensé que iba a salir.
Jose Juan, sí que coinciden. Primero demuestra que no exista una solución con menos de 17 huecos. Lo hace dibujando 4 colores, pero sólo usa en realidad 2: naranja y no naranja (estoy de acuerdo con Fede en que habría sido preferible hacerlo directamente bicolor). Esto es una cota inferior para el número mínimo de huecos. A continuación muestra un ejemplo con exactamente 17 huecos, lo que da una cota superior para el número mínimo de huecos. Cota superior=Cota inferior –> número mínimo de huecos=17. Si lo quieres ver de otra manera, primero demuestra que se pueden poner como mucho… Lee más »
Esta semana no fui capaz de scar la solucion, y una vez vista, me parece magnifica.
fede y Prodem, para poder demostrar que el mínimo ES = 17 (y no, que el mínimo <= 17) no basta con probar que sólo caben 16 piezas (y no más), sino que además, hay que demostrar que caben 16 piezas. Pero, ¿cómo habéis demostrado que habéis metido 16 piezas en el tablero?. Dicen «únicamente podremos colocar 16 piezas como máximo y como es sencillo encontrar ejemplos en los que se pueden colocar 16 piezas en total, resulta que». A eso me refiero, si basas tu demostración en búsqueda de ejemplos, es por exhaución. Por ejemplo, se podría decir que,… Lee más »
Jose Juan. Se demuestra que caben 16 piezas dando un ejemplo, como se hace al final del vídeo. Eso NO es exhaución. El punto del desafío no es demostar que caben 16, lo que es trivial porque hay montañas de ejemplos. Lo difícil es demostrar que no caben 17 sin probar todas las posibilidades. Eso SÍ sería exhaución.
Además el apartado B, creo según el enunciado que no había que demostrarlo, sólo decir el número mínimo de huecos
JoseJuan, lo que es difícil es intentar meter piezas y no llegar a 16, cualquier intento que hagas, salvo que sea muy estúpido, mete justo 16 piezas. De hecho basta por ejemplo poner las piezas todas en la misma posición unas al lado de otras.
¿Y que sea fácil hace que no sea por exhaución?, la cuestión es que no se ha dado ningún argumento (más que un ejemplo por trivial que sea) de que caben 16.