Partida Rol por web

Enunciado:

18. Define a modern artwork to be a nonempty finite set of rectangles in the Cartesian coordinate plane with positive areas, pairwise disjoint interiors, and sides parallel to the coordinate axes. For a modern artwork S, define its price to be the minimum number of colors with which Sean could paint the interiors of rectangles in S such that every rectangle’s interior is painted in exactly one color and every two distinct touching rectangles have distinct colors, where two rectangles are touching if they share infinitely many points. For a positive integer n, let g(n) denote the maximum price of any modern artwork with exactly n rectangles. Compute g(1) + g(2) +···+ g(2019).

Interpretación: No creo que el problema sea complicado, pero veo extraña la interpretación. Según lo que yo he entendido es que tenemos que distribuir como queramos n rectángulos cuyos lados sean paralelos a los ejes de coordenadas y pintar los colores de manera que los vecinos inmediatos (rectángulo de arriba, abajo, izquierda y derecha, NO los diagonales) tengan un color distinto. Y ahora la duda es... el precio S es el correspondiente a la menor configuración posible? Pongo un ejemplo para que se entienda

Si tengo 3 rectángulos, podría colocarlos como una fila de 3 columnas donde el primero y el último podrían ser rojos y el segundo azul, valiendo S=2, ahora bien... si coloco los 3 rectángulos a modo de pirámide... cada rectángulo está en contacto con los otros dos, de manera que tendrían que tener 3 colores diferentes valiendo S=3. No sé si me he explicado adecuadamente.

Alguno me lo podría explicar? xD

De ser que siempre se requiere la mínima configuración sería muy simple puesto que siempre podrías crear una cuadrícula de n rectángulos y pintarlos con dos colores. Así que supongo que es la opción que colocas los rectángulos donde quieras y con los tamaños que quieras, lo cuál si que parece bastante más complicado de lo que pensaba xD...

He estado haciendo unos dibujos y veo configuraciones posibles para tener:

g(1)=1, g(2)=2, g(3)=3, g(4)=3, g(5)=3, g(6)=4, g(7)=3, g(8)=4...

Pero no veo un patrón que sigan los cuadraditos. Lo dejo por si fuera de utilidad.

Veo probable que este problema tenga relación con el teorema de los cuatro colores. Dicen que g(n) define el precio máximo, así que con n=3 debería ser 3, porque hay una configuración que exige 3 colores.

Creo que te equivocas en g(7). Si g(6) es 4, con añadir una rectángulo más a la configuración que hayas dibujado debería seguir siendo como mínimo 4, no bajar a 3.

Estoy de acuerdo en g(1), g(2), g(3), pero no he podido ponerme a dibujar para ver los siguientes.

Supongo también que habrá un n a partir del que g(n) siempre será 4, pero no he podido ponerme a dibujar para ver cuál es.

La verdad es que me extrañó el g(7) pero no encontré una configuración que diera 4. Pues viendo el enlace que me pasas la verdad que creo que tiene toda la pinta de tener que ver con ello, entonces considerando que una vez llegues a 4 se debería mantener constante, creo que el número de transición será el 6.

De ser así el resultado sería:1+2+3+3+3+4*(2019-5) = 8068