Baldosas para el cuarto de baño

Question

Hace poco estuve mirando los azulejos del suelo de mi baño. Son pequeñas baldosas cuadradas de aproximadamente un centímetro cuadrado cada una, dispuestas en una cuadrícula. Están disponibles en dos colores, la mayoría de ellos son de color marrón claro, mientras que unos pocos son de color marrón más oscuro. Como la combinación de colores de mi cuarto de baño es bastante horrible, los llamaremos simplemente blanco y negro (siendo el blanco el color más abundante).

Mientras miraba las baldosas, buscaba cuatro baldosas que formaran las puntas de un paralelogramo. Para mi desgracia no había ninguna (pasé mucho más tiempo del que me gustaría admitir verificando este hecho). Así que empecé un nuevo juego, intentaría ver qué fichas podía hacer negras sin alterar esta propiedad. Pronto empecé a preguntarme cuántos azulejos podía ser negros en mi baño manteniendo esta propiedad. Me pareció una tarea bastante desalentadora porque hay bastantes azulejos en mi baño, así que reduje el tamaño. Primero lo resolví con baños de 1 por 1 y de 2 por 2. Estos fueron bastante fáciles, se puede colocar un azulejo en un 1 por 1 y 3 en un 2 por 2. 3 por 3 es un poco más difícil, pude determinar que 5 azulejos podrían caber.

Prueba:

Consideremos por un momento los siguientes paralelogramos:

(los paralelogramos con esquinas en la fila superior e inferior)

Esto requerirá al menos 2 fichas blancas en estas filas para romper todos estos paralelogramos, y a menos que haya más de 2 necesitamos una en la columna central. Podemos hacer un argumento idéntico para la primera y la última columnas , lo que significa que necesitamos al menos 3 fichas blancas en el anillo exterior (las esquinas se pueden compartir entre las columnas y la fila, pero los centros no).

Originalmente hice un argumento más complejo que involucra un montón de los paralelogramos aquí, pero creo que es un poco más apropiado a la fuerza bruta de aquí. Aquí están todas las formas en que podemos tener tres azulejos blancos que satisfagan las propiedades estipuladas anteriormente:

He sombreado en rojo los paralelogramos que se pueden hacer con fichas negras. Como podemos ver las 3 posibilidades fallan.

Como no pasa ninguna sabemos que hay al menos 4 fichas blancas. Por suerte para nosotros he encontrado algunas soluciones con 4 baldosas blancas que hacer trabajo para que podamos parar aquí:

---

Esta prueba no se amplía a 4 o más cuadrados muy bien o en absoluto. Apenas parece más elegante forzar el problema y me temo que me llevaría horas encontrar una prueba en un cuadrado de 4 por 4.

Como señaló Rahul y amplió Jaap Scherphuis, podemos crear un límite inferior para el número de baldosas negras que pueden caber en el suelo en $2n-1$ (o $m+n-1$ para suelos rectangulares) rellenando dos de los bordes. Jaap tuvo la amabilidad de hacer una búsqueda programática y descubrió que este límite inferior es óptimo hasta $7\times 7$ Sin embargo, nadie ha demostrado todavía que $2n-1$ es la mejor para todas las plazas.

¿Qué métodos podría utilizar para resolver casos más grandes o generales de este problema?
¿El límite inferior es siempre el mejor camino?

Answer 1

Escribí un programa simple para hacer una búsqueda por fuerza bruta de los patrones con el máximo número de fichas negras sin un paralelogramo. Sólo probé hasta $7 \times 7$ porque es bastante lento cuando llega a ese tamaño.

En un comentario anterior, Rahul señaló que el $3\times 3$ con la fila superior y la primera columna en negro es también una solución general para cualquier tamaño de rectángulo. Esto significa que para un $m\times n$ rectángulo, podemos tener al menos $m+n-1$ azulejos negros.

Mi programa no ha encontrado ninguna solución mejor (hasta $7 \times 7$ ). No tengo pruebas de que esto sea válido para rectángulos/cuadrados más grandes. Hay muchas soluciones, y la mayoría, pero no todas, tienen al menos una fila o columna negra. Es bastante fácil ver que una vez que se tiene una fila/columna completamente negra, sólo se puede añadir como máximo una ficha negra en cada otra fila/columna, porque si no se tienen 4 fichas negras en un rectángulo.

Hay una solución general que no tiene una fila/columna negra completa, y es la solución en la que la fila superior y la columna izquierda son negras excepto la esquina superior izquierda, y la esquina inferior derecha también es negra. No he examinado las soluciones muy de cerca para ver si hay alguna otra que se generalice.

Si también se desautorizan los paralelogramos degenerados (es decir, con las cuatro fichas en línea recta), las soluciones generales descritas anteriormente no funcionan cuando una de las dimensiones es $5$ o más. Parece que en ese caso no hay solución con $m+n-1$ azulejos negros. Sospecho que el número máximo de baldosas es entonces alrededor de $3(m+n+1)/4+1$ (es decir, si una dimensión se incrementa en 4, sólo se pueden añadir 3 fichas más) pero no tengo nada concreto en lo que basarme.

Aquí está mi código fuente, en C#.

  using System;
  using System.Collections.Generic;

  namespace test4
  {
     /*
      * Colour as many squares as possible of an HxW grid without producing a parallelogram
      * May or may not call 4 in a line a parallelogram.
      */
     internal class Parallelogram
     {
        // size of rectangle
        private const int W = 7;
        private const int H = 7;

        // set to false if also disallow degenerate parallelograms
        private const bool allowLineOf4 = true;

        private static readonly List<int[]>[] parallelograms = new List<int[]>[H * W];

        public static void Main()
        {
           CreateParas();
           bool[] board = new bool[H*W];
           int best = 0;
           Search(board, 0, 0, ref best);
        }

        private static void CreateParas()
        {
           for (int i = 0; i < H*W; i++)
           {
              parallelograms[i] = new List<int[]>();
           }
           for (int p1 = 0; p1 < H*W; p1++)
           {
              for (int p2 = p1+1; p2 < H * W; p2++)
              {
                 for (int p3 = p2 + 1; p3 < H * W; p3++)
                 {
                    int x1 = p1 % W;
                    int y1 = p1 / W;
                    int x2 = p2 % W;
                    int y2 = p2 / W;
                    int x3 = p3 % W;
                    int y3 = p3 / W;
                    int x4 = x2 + x3 - x1;
                    int y4 = y2 + y3 - y1;
                    if (x4 >= 0 && x4 < W && y4 >= 0 && y4 < H && (!allowLineOf4 || (x1 - x2) * (y2 - y3) != (y1 - y2)*(x2 - x3)))
                    {
                       int p4 = x4 + W*y4;
                       int[] para = { p1, p2, p3, p4 };
                       Array.Sort(para);
                       parallelograms[para[3]].Add(para);
                    }
                 }
              }
           }
        }

        private static void PrintBoard(bool[] brd)
        {
           for (int y = 0; y < H; y++)
           {
              for (int x = 0; x < W; x++)
              {
                 Console.Write(brd[x + y * W] ? "X" : ".");
              }
              Console.WriteLine();
           }
           Console.WriteLine();
        }

        private static void Search(bool[] brd, int ix, int count, ref int best)
        {

           if (ix >= brd.Length)
           {
              if (count >= best)
              {
                 if (count > best)
                 {
                    Console.WriteLine("---- " + count);
                    best = count;
                 }
                 PrintBoard(brd);
              }
              return;
           }
           if (brd.Length - ix + count < best) return;

           brd[ix] = true;
           if (IsOK(brd, parallelograms[ix]))
           {
              Search(brd, ix + 1, count + 1, ref best);
           }
           brd[ix] = false;
           Search(brd, ix + 1, count, ref best);
        }

        private static bool IsOK(bool[] brd, List<int[]> paras)
        {
           foreach (int[] para in paras)
           {
              if (brd[para[0]] && brd[para[1]] && brd[para[2]] && brd[para[3]]) return false;
           }
           return true;
        }
     }
  }