Un fantasma invisible saltando sobre un hexágono regular

Question

Dado un hexágono regular y un fantasma invisible en uno de los vértices del hexágono (no sabemos cuál). Tenemos un arma especial, que puede matar a los fantasmas. En un paso que son capaces de disparar el arma de fuego dos veces (es decir, elegir dos vértices y ver si el fantasma está ahí). Después de cada paso, el gost se mueve a un lado de vértice. ¿Cuál es el mínimo número de movimientos necesarios para matar el fantasma?

Tengo un ejemplo con 6 pasos. Estoy seguro de que este no es el mínimo. Mi amigo tiene un ejemplo para 4 personas. Entonces, ¿cuál es el mínimo? Y se puede generalizar para regular $n$-gon? Gracias!

Answer 1

La fuerza bruta de agotamiento de las posibles estrategias da dos soluciones que requieren cuatro turnos:

• Disparar a $(1,3)$ $(4,6)$ $(2,4)$ $(1,5)$
• Disparar a $(1,3)$ $(4,6)$ $(4,6)$ $(1,3)$

junto con reflexiones y rotaciones de estas soluciones básicas. No hay ninguno que requieren de tres vueltas.

Para ver la segunda solución que funciona, podemos usar el siguiente método para analizar los lugares donde no podría ser un fantasma en vivo:

• El fantasma es uno de $1,2,3,4,5,6$. Después de disparar $(1,3)$, el fantasma se entre $2,4,5,6$.
• El fantasma es uno de $1,3,4,5,6$. Después de disparar $(4,6)$, el fantasma se entre $1,3,5$.
• El fantasma es uno de $2,4,6$. Después de disparar $(4,6)$, el fantasma es en $2$.
• El fantasma es uno de $1,3$. Después de disparar $(1,3)$, no puede ser en cualquier lugar.

Answer 2

Para un $n$-gon, la respuesta es $n-2$ si $n$ es incluso y $n-1$ si $n$ es impar (con las excepciones $n=0,1,2$).

Deje $S$ el conjunto de los posibles vértices de que el fantasma es.

Cuando se dispara, el número de posiciones posibles para el fantasma disminuye (en la mayoría) 2.

Cuando el espíritu se mueve, el número de posiciones posibles para que el fantasma se incrementa en al menos 1 a menos que todos los vértices de una a la derecha de uno de los elementos de $S$ son también uno a la izquierda de uno de los vértices de uno de los elementos de $S$. Este caso sólo puede suceder si $n$ es uniforme y cada otro vértice está en $S$ (otra posibilidad es que S se compone de todos los vértices, pero que no será el caso después de la toma).

Por lo tanto, después de disparar y el fantasma se mueve, el tamaño de $S$ disminuye en 1, excepto en el caso de que $n$ es regular y las posiciones posibles para el espíritu son todos los otros vértices. Esto sólo puede ocurrir si el tamaño de $S$$n/2$, por lo que si el tamaño es a disminuir después de cada sesión sólo se producirá una vez. Esto demuestra que $n-1$ es un límite inferior para el número de tomas requerido si $n$ es impar, y que $n-2$ es un límite inferior de la si $n$ es incluso.

Queda por demostrar que estos límites son alcanzables. Para ello, el número de vértices de $-k$ $k$si $n$ es un número impar (por lo $k=(n-1)/2$) y el número de ellos de $-k$ $k+1$si $n$ es incluso (por lo $k=(n-2)/2$). El algoritmo es como sigue:

La rama 1 y -1.

Disparar 2 y -2.

.

.

.

Disparar $i$$-i$.

.

.

.

Disparar $k-1$$-(k-1)$.

Disparar $k$$-k$.

Disparar $k$$-k$.

Disparar $k-1$$-(k-1)$.

.

.

.

Disparar 2 y -2.

La rama 1 y -1.

Hecho.

Esto se lleva a $2k$ pasos, como se desee.

Answer 3

Voy a probar que cinco movimientos son suficientes para un hexágono), y creo que necesitamos al menos cinco movimientos. Deje $ABCDEF$ ser el hexágono, dispuestos en el sentido contrario de la orden.

En cada uno de los dos primeros movimientos, dispare la pistola en los vértices $B$$F$. Si el fantasma no es asesinado por ahora, entonces debe de estar en algún lugar entre $C$, $D$, y $E$. Luego, en cada uno de los dos se mueve, dispare la pistola en los vértices $C$$E$. Ya que el espíritu no puede ser a $D$ consecutivamente, es finalmente asesinado, o su ubicación ya es $A$. A continuación, queremos apuntar el arma a $B$ $F$ nuevo. esta estrategia garantiza que el espíritu está muerto (bueno, dos veces muertos, porque siendo un fantasma que significa que ha muerto antes).

---

Desde Hurkyl proporcionado ya una $4$-solución paso, estoy demostrando que no existe un infalible estrategia de con $3$ se mueve. Cuando el primer movimiento es hecho, suponemos por ahora que al menos tres vértices consecutivos, dicen, $A$, $B$, y $C$, que no se vean perjudicados. Por lo tanto, si existe una $3$-paso de la estrategia para matar al fantasma, en los próximos dos movimientos matar al fantasma, incluso cuando el espíritu comienza en algún lugar entre $A$, $B$, y $C$.

El segundo movimiento tendrá que incluir al menos uno de los vértices $A$, $B$, y $C$; de lo contrario, el último movimiento va a dejar al menos un vértice de las tres vírgenes, y el espíritu puede sobrevivir. Sin pérdida de generalidad, el segundo movimiento golpea $A$ o $B$.

1. Tanto en $A$ $B$ son baleados en el segundo movimiento. Entonces, para sobrevivir, el espíritu debe ser de al $C$, o que ya ha salido de la zona $A$, $B$, y $C$ totalmente. En este caso, el tercer movimiento puede hacer ningún daño al espíritu. (Si el fantasma es en $C$, entonces tenemos que matar a $B$$D$; sin embargo, el fantasma también podría ser al $D$, a continuación, mueva a $C$, donde este último movimiento no va a tener éxito.)
2. El segundo movimiento golpea $A$ y algunos vértice $X\notin \{A,B,C\}$. Para sobrevivir, el fantasma puede ser en el vértice $B$, $C$, o $D$ justo antes de que el segundo movimiento está hecho. Entonces, de nuevo, hay demasiadas opciones para sobrevivir durante el fantasma, como antes de la tercera movimiento, puede ser en cualquier lugar de $A$, $B$, $C$, y $D$.
3. El segundo movimiento golpea $B$ y algunos vértice $X\notin \{A,B,C\}$. Si el espíritu sobrevive a la primera y la segunda intentos de asesinato, debe haber sido originalmente en $B$, y, a continuación, mueva a $A$ o $C$ antes de la segunda mover. Por lo tanto, el tercer movimiento, el fantasma puede estar en cualquier lugar entre $F$, $B$, y $D$, y golpear dos vértices no segura de la misión.

Ahora, vamos a tratar con el caso de que el primer movimiento que alcanza los dos vértices opuestos, dicen, $A$$D$. Entonces, antes de que el segundo movimiento, el fantasma puede estar en cualquier lugar en el hexágono. Por lo tanto, el segundo paso será dejar al menos dos vértices adyacentes virgen. Antes de que el tercer movimiento, el espíritu que ahora tienen al menos cuatro lugares.