¿Cuál es la estrategia óptima para el problema generalizado de las "Siete Velas"?

Question

Hace poco me encontré con un rompecabezas de Popular Mechanics . He aquí una paráfrasis:

Hay siete velas dispuestas en un anillo. Todas están encendidas inicialmente. Tu objetivo es apagarlas todas soplando sobre ellas. Pero se trata de velas mágicas: si soplas sobre una vela, ésta y las dos velas adyacentes pasarán de encendidas a apagadas o viceversa. ¿Cuál es el número mínimo de velas que tienes que soplar?

La solución es la siguiente:

Sopla en cada vela. Cada vela se enciende tres veces, una por sí misma y otra por cada una de sus vecinas, de modo que acaba apagándose.

Imaginemos la generalización de este rompecabezas. Supongamos que tenemos $n$ velas y cada vela influye en el $r$ velas a su izquierda y derecha. (Supongamos que $2r \le c$ para evitar el caso en el que esto se envuelva). Denotemos por $B(c, r)$ el número mínimo de velas que hay que soplar para apagar todas las velas.

Mi pregunta es la siguiente: ¿existe una fórmula sencilla para $B(c, r)$ ?

Para determinados valores de $r$ y $c$ esto es fácil: $B(c, r) = \frac{c}{2r+1}$ si $2r + 1$ divide $c$ por ejemplo, ya que puede soplar cada ( $2r + 1$ )a vela. Para otras, como la versión inicial del problema, el valor será mayor.

Sospecho (?) que en algún lugar de aquí hay algo relacionado con los polígonos estrella o el GCD de $c$ y $2r + 1$ . Sin embargo, ni siquiera conozco una forma sencilla de demostrar que la solución del problema inicial es óptima (lo verifiqué enumerando casos menores y descartándolos), y eso me está impidiendo avanzar más.

Answer 1

Dejemos que $d=2r+1$ sea un número impar, por un poco de conveniencia notacional.

La fórmula que buscas, como menciona Greg Martin, es

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

En primer lugar, veremos que cuando $\gcd(c,d)=1$ (y $d$ es impar), obtenemos $c$ como en el problema original con $7$ y $3$ .

Es obvio que soplar todas las velas funciona, ya que cada vela se voltea un número impar de veces. ¿Pero por qué no puede funcionar algo más pequeño?

El espacio de posiciones de velas realizables forma lo que se llama un espacio vectorial En este caso, podemos sumar dos velas simplemente haciendo una y luego la otra (pero cualquier vela que se sople dos veces podemos omitirla, ya que soplar dos veces no hace nada). Lo más importante es que estamos utilizando el hecho de que no importa en qué orden soplamos las velas.

Tenemos $2^{c}$ posibles formas de elegir un subconjunto de velas para soplar, y $2^c$ resultados potenciales para los que se acaban encendiendo velas. Para ver que la configuración "todo encendido" sólo tiene una solución, mostraremos que todas las configuraciones son posibles, demostrando que nuestro $2^c$ Las posibilidades de las velas deben haberse utilizado exactamente una vez para cubrir todos los posibles resultados que queríamos obtener.

¿Por qué podemos obtener todas las configuraciones? Pues bien, basta con poder encender una sola vela individual: al girar las opciones de las velas, esto nos permite obtener tout vela individual, y sumando esas soluciones obtenemos cualquier arreglo que queramos.

Entonces, ¿cómo podemos conseguir una sola vela? Al soplar dos velas adyacentes, encendemos dos velas separadas por una distancia de $d$ (decir velas $0$ y $d$ ). El mismo procedimiento nos permite alternar las velas $d$ y $2d$ , para un resultado final de encendido de velas $0$ y $2d$ . Hacerlo de nuevo nos da velas $0$ y $3d$ etc, y a medida que avancemos alrededor de este polígono estelar podremos encender la vela $0$ y cualquier otra vela que queramos (ya que $d$ es relativamente primo de $c$ ). Así que por rotación, podemos alternar cualquier par de velas que queramos.

Luego, para obtener una sola vela, alternamos una vela, lo que nos da $d$ velas que están encendidas, un número impar. Luego cancelamos los pares de uno en uno hasta que quede una sola vela.

---

Esa es la $\gcd(c,d)=1$ caso tratado. ¿Qué pasa si $\gcd(c,d) = r > 1$ ?

Escoge cualquier vela, y considera la $c/r$ velas dadas tomando cada $r^\textrm{th}$ vela de allí. De estas velas, $d/r$ de ellos en una fila se conmutan cada vez que usted respira en una vela. Así que estamos jugando una versión en miniatura del mismo juego en estos $c/r$ velas con nuestro $d/r$ -suspiraciones. Y como $\gcd(d/r, c/r) = 1$ (y $d/r$ sigue siendo impar), sabemos que tomará exactamente $c/r$ respiraciones para encender todas nuestras velas espaciadas. Así que eso es un límite inferior para encenderlas todas.

Pero si simplemente tomamos nuestra solución en el juego de miniaturas y respiramos sobre las correspondientes velas espaciadas uniformemente, entonces nuestros toggles tratarán cada bloque de $r$ velas lo mismo, por lo que encender uno de nuestros conjuntos espaciados hará lo mismo con todos los demás.

Como ejemplo, la solución con $d=3, c=5$ parece

11100
01110
00111
10011
11001

Y la solución con $d=9, c = 15$ (así $r=3$ ) se parece a

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

Espaciamos nuestras respiraciones cada $3$ velas, y producir una mini versión de la $d=3, c=5$ juego dentro de nuestras cinco manzanas de $3$ velas consecutivas.