Removing points from a triangular array without losing information

Question

I'm trying to find insights about the following puzzle, to see if I can find it on the OEIS (and add it if it's not already there):

Suppose I give you a triangular array of light bulbs with side length $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

I'm going to turn on three lightbulbs that form an "upright" equilateral triangle as in the following example:

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

Before I turn on the lights, your job is to remove as many lightbulbs as possible from the array—without losing the ability to deduce the triangle of bulbs that has been turned on. To be clear, if a lightbulb has been removed, it is not lit up when its position is turned on.

For example, if you removed the following bulbs (marked by .) you would only see the following two lights turn on (marked by x), which is enough uniquely deduce the third (unlit) position:

     .              .
    . 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

Let $a(n)$ be the maximum number of bulbs that can be removed without introducing any ambiguities.

With a naive algorithm, I have checked values up to a triangle with side length 7, as seen below:

                                                                      .
                                                      .              . 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

Searching for this sequence on the OEIS turns up dozens of results.

---

As an upper bound for this sequence, we need the different configurations of 3, 2, 1, or 0 lights to be able to represent all of the $\binom{n + 1}{3}$ possible triangles. That is:

$$\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

A stronger upper bound on $a(n)$ comes from the following observation: if we choose any two missing lights from the same row, then they are part of a triangle with at most one light still working. By pigeonhole, there can be at most $\binom{n+1}{2} + 1 - a(n) \le \binom{n+1}{2}$ such triangles, otherwise two of them would correspond to the same single light bulb being lit up.

Let $a_k$ be the number of lightbulbs missing from row $k$, so that $a_1 + a_2 + \dots + a_n = a(n)$. Then the number of ways to choose two missing lights from the same row is $$\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}.$$

So we get a bound on the order of $a(n) = O(n^{3/2})$. (In particular, for large $n$, almost all the lightbulbs have to remain in place.)

---

On the other hand, we can show that $a(n) = \Omega(n^{4/3})$ by a probabilistic construction. Let's pick some lightbulbs to remove by the following process:

1. First, for each lightbulb, independently decide whether to remove it at random, with a probability $p$ of removing it (to be determined later).
2. Second, every time there is a triangle in which all three lightbulbs are removed, put them all back.
3. Third, if a lightbulb is the vertex of $k \ge 2$ triangles in which the other two lightbulbs are removed, put back one lightbulb (chosen arbitrarily) in each of them.

This guarantees that there are no triangles with all three lightbulbs missing, for each triangle with two lightbulbs missing the third lightbulb is unique, and we don't care about triangles with at most one lightbulb missing because those are uniquely determined anyway.

Now we compute the expected number of lightbulbs we removed. In step 1, we removed an average of $\binom{n+1}{2} p$ of them. In step 2, we found an average of $\binom{n+1}{3}p^3$ triangles with all three vertices missing, and added three lightbulbs back for each one, for $\binom{n+1}{3}p^3 \le \binom{n+1}{2} (np^3)$ more lightbulbs.

Step 3 is the trickiest. We can think of it this way: if a lightbulb is the single remaining vertex of $\mathbf X$ triangles, we always remove $\mathbf X$ of them, except when $\mathbf X=1$, when we get to keep one. So we remove $\mathbb E[\mathbf X] - \Pr[\mathbf X=1]$ triangles. Every lightbulb is the vertex of $n-1$ triangles, and is the only remaining one with probability $p^2$, so \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} This is for each of $\binom{n+1}{2}$ lightbulbs in the array. So at the end of the day, the expected number of lightbulbs removed and not replaced is at least $$\binom{n+1}{2}\left(p - np^3 - n^2p^4\right)$$ and this is optimized when $p = (2n)^{-2/3}$ giving $\Omega(n^{4/3})$ lightbulbs removed.

(The exact constant on the leading term there is something like $\frac{3}{8\cdot 2^{2/3}} \approx 0.236$.)