Por @Alvy — 8 de Diciembre de 2009

Grid15-15

Interesante y complicado problema este que ha planteado William Gasarch y que vi en Bit-Player vía reddit. A quien lo resuelva le esperan 17² dólares de premio y la fama eterna.

El problema genérico consiste en colorear todos los puntos de un rectángulo en n por m con cierto número de colores, sin que en su interior aparezcan rectángulos virtuales con las cuatro esquinas del mismo color (de aspecto vertical y diagonal, sin contar los inclinados). En algunos casos concretos se sabe que por ejemplo hasta los cuadrados de 16×16 es posible hacero empleando tan solo cuatro colores (como el de arriba, que mide 15×15), pero tambíen se sabe que para los de 18×18 es imposible limitándose sólo a cuatro colores (como le sucede a este de abajo, de 16×16).

Grid16X16

El reto consiste en encontrar un cuadrado de 17×17 que pueda ser coloreado con cuatro colores sin que en su interior haya rectángulos con las cuatro esquinas del mismo color, o demostrar por qué es imposible que exista.

En la anotación de Bit-Player se explica por qué el problema dista de ser trivial: las pruebas por fuerza bruta no son suficientes porque habría que revisar 4289 casos, así que se necesita una combinación de ingenio para reducir muchos casos a un número más razonable, de forma matemáticamente demostrable, y luego probablemente comprobarlos todos uno por uno.

Compartir en Flipboard Compartir en Facebook Tuitear

PUBLICIDAD




PUBLICIDAD


Microsiervos Selección


5 Very Good Reasons to Punch a Dolphin in the Mouth

EUR 11,17 (Reseña en Microsiervos)

Comprar


The Human Face of Big Data

EUR 48,11

Comprar


Amazon Associates

Los productos aquí enlazados están a la venta en Amazon. Incluyen un código de Afiliado Amazon Associates que nos cede un pequeño porcentaje de las ventas. Los productos están seleccionados por los autores del blog, pero ni Amazon ni los editores de los libros o fabricantes de los productos participan en dicha selección.

Más libros y productos en:

Microsiervos Selección