What is the optimal strategy for the generalized “Seven Candles” problem?

Question

I recently came across a puzzle from Popular Mechanics. Here’s a paraphrase:

There are seven candles arranged in a ring. They are all initially lit. Your goal is to extinguish them all by blowing on them. But these are magic candles: if you blow on a candle, it and the two candles adjacent to it will toggle from lit to extinguished or vice-versa. What is the minimum number of candles you need to blow on?

The solution is the following:

Blow on each candle. Each candle then toggles three times, one for itself and once for each of its neighbors, so it ends up extinguished.

Let’s imagine generalizing this puzzle. Suppose you have $n$ candles and each candle influences the $r$ candles to its left and right. (Let’s assume $2r \le c$ to avoid the case where this wraps around.) Let’s denote by $B(c, r)$ the minimum number of candles you need to blow on to extinguish all the candles.

My question is the following: is there a simple formula for $B(c, r)$?

For certain values of $r$ and $c$, this is easy: $B(c, r) = \frac{c}{2r+1}$ if $2r + 1$ divides $c$, for example, since you can blow out every ($2r + 1$)st candle. For others, such as the initial version of the problem, the value will be larger.

I suspect (?) that buried somewhere in here is something related to star polygons or the GCD of $c$ and $2r + 1$. However, I don’t even know a simple way to prove the solution to the initial problem is optimal (I verified it by listing smaller cases and ruling them out), and that’s blocking me from making more progress here.

Answer 1

Let's let $d=2r+1$ be an odd number, for a bit of notational convenience.

The formula you're looking for, as Greg Martin mentions, is

$$B(c,d) = \frac c{\gcd(c,d)}$$

First, we'll see that when $\gcd(c,d)=1$ (and $d$ is odd), we get $c$, as in the original problem with $7$ and $3$.

It's obvious that blowing out all the candles works, since every candle is flipped an odd number of times. But why can't something smaller work?

The space of realizable candle positions forms what's called a vector space, where we can add together any two candle setups by simply doing one and then the other (but where any candle that get blown on twice we can just skip instead, since blowing on them twice does nothing). Importantly here, we're using the fact that it doesn't matter in which order we blow on the candles.

We have $2^{c}$ possible ways to choose a subset of candles to blow on, and $2^c$ potential outcomes for which candles end up being lit. To see that the "all lit" configuration only has one solution, we'll show that every configuration is possible, proving that our $2^c$ candle possibilities must have been used exactly once to cover all possible outcomes we wanted to obtain.

Why can we obtain every configuration? Well, it suffices to be able to light a single individual candle: by rotating the candle choices, this lets us get any individual candle, and by adding up those solutions we get any arrangement we'd like.

So how can we get a single candle? By blowing two adjacent candles, we light up two candles separated by a distance of $d$ (say candles $0$ and $d$). The same procedure lets us toggle candles $d$ and $2d$, for a final result of turning on candles $0$ and $2d$. Doing it again gives us candles $0$ and $3d$, etc, and as we proceed around this star polygon we'll be able to turn on candle $0$ and any other candle we want (since $d$ is relatively prime to $c$). So by rotation, we can toggle any pair of candles we want.

Then, to get a single candle, we toggle one candle, giving us $d$ candles that are on, an odd number. Then we cancel pairs one at a time until there's a single candle left.

---

That's the $\gcd(c,d)=1$ case handled. What if $\gcd(c,d) = r > 1$?

Pick any candle, and consider the $c/r$ candles given by taking every $r^\textrm{th}$ candle from there. Of these candles, $d/r$ of them in a row get toggled every time you breathe on a candle. So we're playing a miniature version of the same game on these $c/r$ candles with our $d/r$-sized breaths. And since $\gcd(d/r, c/r) = 1$ (and $d/r$ is still odd), we know that it will take exactly $c/r$ breaths to light up all of our spaced-out candles. So that's a lower bound for lighting them all up.

But if we just take our solution in the miniature game and breathe on the corresponding evenly-spaced candles, then our toggles will treat each block of $r$ candles the same, so turning on one of our spaced-out sets will do the same to every other one.

As an example, the solution with $d=3, c=5$ looks like

11100
01110
00111
10011
11001

And the solution with $d=9, c = 15$ (so $r=3$) looks like

111 111 111 000 000
000 111 111 111 000
000 000 111 111 111
111 000 000 111 111
111 111 000 000 111

We space out our breaths every $3$ candles, and produce a mini version of the $d=3, c=5$ game within our five blocks of $3$ consecutive candles.