Eliminación de puntos de una matriz triangular sin perder información

Question

Estoy tratando de encontrar pistas sobre el siguiente acertijo, a ver si me lo puede encontrar en la OEIS (y añadirlo si no está ya allí):

Supongamos que te doy un arreglo triangular de bombillas de luz con una longitud de $n$:

     o
    o o
   o o o
  o o o o
 o o o o o
o o o o o o
1 2  ...  n

Me voy a convertir en tres bombillas de luz que forman una "vertical" de un triángulo equilátero como en el siguiente ejemplo:

     o
    o x
   o o o
  o o o o
 o x o o x
o o o o o o

Antes de encender las luces, su trabajo es eliminar todas las bombillas de luz como sea posible a partir de la matriz-sin perder la capacidad de deducir el triángulo de las bombillas de que ha sido activado. Para ser claros, si una bombilla se ha eliminado, no se enciende cuando su posición se enciende.

Por ejemplo, si se ha eliminado el siguiente bombillas (marcado por .) que sólo ver las dos siguientes luces se encienden (marcado por x), lo cual es suficiente únicamente deducir la tercera (apagado) posición:

     .              .
    . o            . x
   . . o          . . o
  o o o .   =>   o o o .
 o o o o .      o x o o . <- the third unlit position
o . . . o o    o . . . o o

Deje $a(n)$ ser el máximo número de bombillas que se pueden quitar sin introducir ninguna ambigüedad.

Con ingenua de un algoritmo, he comprobado los valores de hasta un triángulo con un lado de longitud 7, como se ve a continuación:

                                                                      .
                                                      .              . o
                                        .            . o            o . o
                           .           . .          . . o          . o o .
              .           . .         . o o        o o o .        o o . o .
 .           . .         . o o       o o . o      o o o o .      o . o . o o
. .         . o o       . o o o     o . . o o    o . . . o o    o . o . o o o

a(2) = 3    a(3) = 4    a(4) = 5    a(5) = 7     a(6) = 9       a(7) = 11

La búsqueda de esta secuencia en la OEIS vueltas hasta cientos de resultados.

---

Como una cota superior para esta secuencia, tenemos las diferentes configuraciones de 3, 2, 1 o 0 luces para ser capaz de representar a todos los de la $\binom{n + 1}{3}$ posible triángulos. Que es:

$$\binom{n + 1}{3} \leq \binom{b(n) - a(n)}{3} + \binom{b(n) - a(n)}{2} + \binom{b(n) - a(n)}{1} + \binom{b(n) - a(n)}{0}$$ where $b(n) = \frac{1}{2}n(n+1)$.

Answer 1

Un fuerte límite superior en $a(n)$ procede de la siguiente observación: si se elige cualquiera de los dos que faltan las luces de la misma fila, a continuación, son parte de un triángulo con una luz que aún trabajan. Por encasillar, no puede haber más de $\binom{n+1}{2} + 1 - a(n) \le \binom{n+1}{2}$ triángulos, de lo contrario, dos de ellos corresponden a la misma luz de la bombilla se encendió.

Deje $a_k$ el número de bombillas que faltan de la fila $k$, por lo que el $a_1 + a_2 + \dots + a_n = a(n)$. Entonces el número de formas de elegir los dos que faltan las luces de la misma fila $$\binom{a_1}{2} + \binom{a_2}{2} + \dots + \binom{a_n}{2}$$ which is at least $n \cdot \binom{a(n)/n}{2}$ by convexity. This gives us the inequality $$n \cdot \binom{a(n)/n}{2} \le \binom{n+1}{2} \implies a(n) \le \frac{n + n\sqrt{4n+5}}{2}.$$

Así que tenemos un límite en el orden de $a(n) = O(n^{3/2})$. (En particular, para un gran $n$, casi todas las bombillas de luz tiene que permanecer en su lugar.)

---

Por otro lado, podemos ver que $a(n) = \Omega(n^{4/3})$ por probabilística de la construcción. Vamos a recoger algunas bombillas de eliminar mediante el siguiente proceso:

1. En primer lugar, para cada bombilla de luz, independientemente de decidir si se debe eliminar al azar, con una probabilidad de $p$ de extracción (a determinar).
2. Segundo, cada vez que hay un triángulo en el que los tres bombillas son eliminados, ponerlos a todos de vuelta.
3. En tercer lugar, si una bombilla es el vértice de $k \ge 2$ triángulos en los que los otros dos bombillas se quitan, se vuelve a poner una bombilla (elegido arbitrariamente) en cada uno de ellos.

Esto garantiza que no hay triángulos que tienen los tres bombillas que faltan, para cada triángulo con dos bombillas de luz, falta la tercera bombilla es único, y no nos preocupamos de triángulos con una bombilla falta porque esos son los únicos determinado de todos modos.

Ahora podemos calcular el número esperado de las bombillas que hemos eliminado. En el paso 1, hemos eliminado a un promedio de $\binom{n+1}{2} p$ de ellos. En el paso 2, se encontró un promedio de $\binom{n+1}{3}p^3$ triángulos con los tres vértices que faltan, y añadió tres bombillas de luz por cada uno, para $\binom{n+1}{3}p^3 \le \binom{n+1}{2} (np^3)$ más de bombillas.

El paso 3 es el más difícil. Podemos pensar de esta manera: si una bombilla es el único resto de vértices de $\mathbf X$ triángulos, siempre nos quite $\mathbf X$ de ellos, excepto cuando el $\mathbf X=1$, cuando tenemos que mantener uno. Así que nos quite $\mathbb E[\mathbf X] - \Pr[\mathbf X=1]$ triángulos. Cada bombilla es el vértice de $n-1$ triángulos, y es la única que queda uno con una probabilidad de $p^2$, por lo que \begin{align} \mathbb E[\mathbf X] - \Pr[\mathbf X=1] &= (n-1)p^2 - (n-1)p^2 (1-p^2)^{n-1} \\ &= (n-1)p^2[1-(1-p^2)^{n-1}] \\ &\le (n-1)p^2[1 - (1 - (n-1)p^2)] \\ &\le n^2p^4. \end{align} Esto es para cada uno de $\binom{n+1}{2}$ bombillas en la matriz. Así que al final del día, se espera que el número de bombillas eliminado y no es reemplazado, al menos, $$\binom{n+1}{2}\left(p - np^3 - n^2p^4\right)$$ y esto está optimizado al $p = (2n)^{-2/3}$ dar $\Omega(n^{4/3})$ bombillas eliminado.

(La exacta constante en el término hay algo como $\frac{3}{8\cdot 2^{2/3}} \approx 0.236$.)