17×17

No voy nada dado a este tipo de mates y además lo explican en un PDF ultra-esquematizado estilo diapositivas para una presentación.

Pero creo entender que el autor parte de rectangulos menores de los cuales sabe a ciencia cierta que son coloreables con X colores debido a propiedades matemáticas diversas. Luego a partir de ellos va expandiendo y comprobando si nuevos rectángulos mayores son posibles o no.

No es un método de fuerza bruta pero es casi lo más parecido. En reddit de hecho estan proponiendo cosas parecidas.

Pero por lo que puedo leer, creo que están demasiado ofuscados pensando en cuadrados en vez de en rectángulos. Hayq ue recordar que el enunciado habla de rectángulos.

no creo que sean tantos casos a probar usando fuerza bruta
seria cosa de tomar uno 16x16 y agregarle la fila y columna faltante
con eso se reducen bastante los casos posibles

Está claro Kotolo que puedes hacer eso, pero resulta que los de 16x16 posibles de dónde los sacas???

Seguro que ya han probado con uno de 16x16 que cumple lo de que no existan rectángulos y que todos los casos obtenidos no les ha valido. Pero claro, esto no quiere decir que no exista ninguno de 17x17 que cumpla lo mismo ya que el de 16x16 previo no tiene por qué estar contenido.

Pero vamos, que está claro que de forma sencilla se puede reducir los casos a estudiar, pero aún así con las formas sencillas que al menos a mi se me ocurre, dudo que sean computables.

Lo de coger uno de 16x16 fue también lo priemro que pensé; y en la anotación de reddit también hay otros que pensaron lo mismo.

Pero como bien dice 3#, no todos los de 16x16 serán a la vez válidos para ampliarlos a 17x17. Así que hay que ir cogiendo TODOS los cuadrados de 16x16 válidos y probar de ampliarlos (hasta probarlos TODOS o hasta encontrar uno válido).

El problema es ¿como consigo un "listado" de TODOS los cuadros de 16x16 4-coloreables? Como ya dije, por lo que se entiende del planteamiento del problema, el autor parte de bloques pequeños fácilmente comprobables; y luego los aplica a bloques mayores mediante propiedades matematicas diversas.

Por 17^2 dólares no pongo mis neuronas a trabajar.
Si fuesen 2^17, ya sería otra cosa.

Señores, esto no es nada más que un algoritmo de backtracking y diagramas de Euler, con una modificación para evitar casos redundantes y bajar la combinación de colores de forma sustancial, pero tal y como dice RedWar, por 17^2 no merece la pena las horas de trabajo de optimización del algoritmo =)

Supongo que mis años(15) no dan para algoritmos y otras parafernalias. Pero, seguro que con todos esos cálculos también te dicen los rectángulos que aparecen en diagonal?
Entonces me parece que quizá hay que revisar más de los 4^289 que se citan.
Creo yo vamos.

#5 RedWar y #6 alex fue lo primero que pensé. 17^2 es casi un insulto. No merece la pena ponerse a trabajar en ello. De todos modos se puede modelar como un grafo en el que las aristas esten dispuestas atendiendo a las restricciones que plantean y tratar de colorearlo. Pero insisto que por ese dinero no merece la pena.

No se demasiado de informàtica, pero... eso no se podria poner en un ordenador de esos potentes que se pasan el dia buscando decimales del número pi ;) y en un momento que lo resuelva, o diga si es imposible?
Eso sí, que de premio solo haya 17^2 dólares...
Si fueran 17^2 millones puede que si que trabajaria un poco. O alomejor intentaria que mi ordenador lo hiciese... ;)

A todos los que dicen que 17^2 es poco dinero... ¿cuántos problemas habéis resuelto gratis? Además aunque parezca una tontería resolver el problema podría suponer una publicación en una revista científica de prestigio lo que puede venir bien para el currículum dependiendo de para qué trabajos (a mi por ejemplo me vendría bien, ya tengo algunos artículos de matemáticas y trabajando por tener más).

Y eso de "uy, qué fácil, pero es mucho trabajo y dan poco dinero". Me da a mi que directamente no tenéis ni idea de informática, bueno, concretamente de tiempo de cálculo y de lo grandes que son las potencias. Que si tardas x en hacer por ejemplo 4^4 operaciones, no tardas 2x en hacer 4^8 sino que tardarías 256x.

J15, habla de números de casos, y sí, son los dichos (aunque se puede reducir), otra cosa es hablar del número de operaciones que hay que hacer para revisarlos.

P.d. A ver si alguno se pica con mi comentario y resuelve el problema. Yo personalmente no me veo capaz hacer un programa que pudiese resolverlo rápido.

Os dejo mi comentario en inglés "chapurrero" en su blog.
Lo suyo sería sacar una fórmula o algo, cosa que a estas horas no tengo ganas, pues ya me comeré la cabeza mañana.

Alguna aportación??? Qué opináis??

I believe it's easy.

1x1 -> 1 colour
from 2x2 to 4x4 -> 2 colours
from 5x5 to 8x8 -> 3 colours
from 9x9 to 16x16 -> 4 colours
17x17 -> 5 colours
18x18 -> 5 colours

How do I know? Easy. For example, an 8x8 square. 7 in binary is 111, there are three characters on '111'. So you can do it with 3 colours.

For 8x8, 8 is 1000, you'll say 4 characters, let me explain.

The theory is:
1 - 1
2 - 10
3 - 11
4 - 100 -> From 4 to above 3 colours and 4 is not included on that rule!!! 4 will be included on the rule of 2 colours.
5 - 101
6 - 110
7 - 111
8 - 1000 -> From 8 to above 4 colours and 8 is not included on that rule!!! 8 in 3 colours
9 - 1001
10 - 1010
11 - 1011
12 - 1100
13 - 1101
14 - 1110
15 - 1111
16 - 10000 -> From 16 to above 5 colours and 16 is not included on that rule!!! 16 in 4 colours

Sooooooooo...
17 - 10001 -> 5 colours
18 - 10010 -> 5 colours

Con un programilla en matlab sencillo al máximo he conseguido una 10x10 pero de ahi no subo.......

No confundir "no computable" con "tiempo de computación exponencial a la entrada"

Yo había pensado en ir haciendo estos pasos

- Calcular todos los cuadros 2x2 válidos.
- Combinarlos para conseguir todas las opciones de rectángulos de 2x3 válidos.
- Combinar éstos para conseguir los rectángulos 2x4 válidos.

Y así ir haciendo, eliminando en cada paso los rectángulos no válidos, lo cual es simple de detectar (2 columnas o más de igual color).

Al final se trataría de tener todos los rectángulos válidos de 2x17. Si existe algún cuadrado 4-coloreable de 17x17 por narices sus filas y columnas serán un subconjunto de todos los posibles rectángulos 2x17 4-coloreables.

Y aún así, elimin ando en cada paso los rectángulos no válidos o repetidos, el coste computacional de este procedimiento es inmenso. Sigue siendo (si no me equivoco) exponencial con respecto a la entrada aunque elimine algunos órdenes de magnitud.

Pues es muy fácil de demostrar que es imposible hacer un cuadrado de 17x17 con esas condiciones.
Pero fácil fácil.
No es raro que ofrezcan dinero al que consiga un imposible.

De solo verlo me he quedado en "shock" como para resolverlo, parece facil a simple visita... pero no. En mi opinion, es imposible.

#15 Ignition, creo que has hablado demasiado XD.

El premio es para el que consiga el coloreado o el que demuestre que no se puede. Si tan fácil es demostrarlo como tú dices... a qué esperas para reclamar tus 289 dólares!!!

Para Rubén (#11) No se si lo llegué a entender muy bien, pero creo que sólo se usan 4 colores en el grafo. Lo que yo si se es que todo grafo de X tamaño se puede pintar con 4 colores, el quid de la cuestión viene sobre los "rectangulos virtuales", el teorema sólo se basa en los puntos colindantes

http://es.wikipedia.org/wiki/Teorema_de_los_cuatro_colores

Tambien rectangulos diagonales cuentan?
Si es asi, encontre uno en el ejemplo de 15x15, lo que significaria que no esta correcto