Problemas de Matemáticas en El País – Problema nº 10

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.

Autor: ^DiAmOnD^

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.

33 Comentarios

  1. 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 que es óptimo a lo bruto.

    Publica una respuesta
  2. ¡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”.

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

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

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

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

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

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

    Publica una respuesta
  9. @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 2*k columnas, tiene el mismo minimo de espacios que un tablero de 2*k filas y 2*k-2 columnas.Y otras cosas recursivas por el estilo.
    Todo esto me pasa por generalizar.

    Publica una respuesta
  10. Quiero decir que he encontrado un contraejemplo a lo que he puesto antes de 2k filas…

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

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

    Publica una respuesta
  13. @Carlos, @Sara F., en realidad solo hace falta un color (además del blanco).

    Publica una respuesta
  14. @Félix, en el caso de 2*x filas y 2*y columnas el mínimo es 4*min(x,y).

    Publica una respuesta
  15. Pues como dice Mmonchi, en realidad basta con un color y las sin colorear. Basta con coger el “menor” 😀

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

    Publica una respuesta
  17. @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 por inducción las propiedades de un tablero.

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

    Publica una respuesta
  19. 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), se forma un sistema de inecuaciones (una inecuación para cada casilla del tablero) en el que, la suma de las posiciones (las x1, x2, …) debe ser 0 ó 1 (forzando que sólo una pieza ocupa una celda simultáneamente).

    Basta ahora maximizar la suma de las variables x1, x2, …

    Lo bueno de este método, es que sirve para cualquier tamaño de tablero y cualquier forma de piezas (incluso tener diferentes conjuntos de piezas). Lo malo es que es un problema NP-completo (aunque en la práctica se pueden resolver tableros muy grandes rápidamente).

    ¿Alguna demostración directa?

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

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

    Publica una respuesta
  22. “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 admitían como válidas demostraciones por exhaución.

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

    Publica una respuesta
  24. 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 16 piezas (cota superior para el máximo número de piezas), y luego da un ejemplo en el que se pueden poner 16 piezas (cota inferior para el máximo número de piezas). De nuevo, Cota superior=Cota inferior –> número máximo de piezas=16.

    No sé si tu confusión viene de cosas como “cota inferior para un máximo”, pero espero haberte aclarado algo.

    Por cierto, esta demostración NO es por exhaución, pero me parece que en algunos problemas (piano, cubo) sí han admitido demostraciones de ese estilo, en particular usando ordenador. Por cómo lo explican parece claro que esas soluciones no son sus preferidas, pero las aceptan y entran en el sorteo.

    Publica una respuesta
  25. Esta semana no fui capaz de scar la solucion, y una vez vista, me parece magnifica.

    Publica una respuesta
  26. 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, en columna caben 4 ocupando 2 y sólo 2 columnas, por tanto ya caben las 16. ¿Lo he demostrado? sí, ¿ha sido por exhaución? ¡sí! porque si ese ejemplo no me hubiera funcionado (lo de las columnas) ¡tendría que buscar otro!, y otro, y otro, …

    Es diferente a la demostración que dan de las acotaciones, pues ahí dan un argumento independiente de una configuración particular.

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

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

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

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

    Publica una respuesta

Trackbacks/Pingbacks

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

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 *