La elección de un amigo.

Question

Dado $2n$ personas en una habitación, donde cada pareja, ya sea de amigos o de desconocidos, dos de los jugadores se turnan para recoger a una persona tal que la persona elegida es un amigo de la persona que previamente fijadas. El jugador que no puede hacer un movimiento pierde. Determinar una estrategia ganadora para alguno de los jugadores.

Lo que yo creo,

Sea a y B en el primer y segundo jugador respectivamente.

Cada vértice del Grafo G representa a la persona y dos vértices están conectados si son amigos.

Una gana si la gráfica tiene dos bordes conectados, tres bordes conectados en triángulo.

B gana si el grafo tiene un borde, tres bordes conectados en una línea.

Answer 1

Sugerencia: si hay una perfecta coincidencia de la gráfica, B gana. De lo contrario gana.

---

Edit: en respuesta a una larga discusión a continuación, con el objetivo de resolver la indicación precisa del problema, voy a intentar dar una solución más robusta.

Caso 1: el Jugador a elige el vértice de partida, entonces B se elige un vértice adyacente y el juego continúa.

• Supongamos que hay un perfecto maridaje. Entonces no importa que el vértice de Una elige a, B puede ir a lo largo de un borde a un igualado vértice y continuar de esta manera, por lo que siempre será capaz de hacer un movimiento.

• Ahora supongamos que no hay perfecto maridaje. A continuación puede encontrar cualquier máxima coincidente, a continuación, elegir un inigualable vértice y el uso de la estrategia de B, es decir, escoger siempre el vértice coincide con el vértice elegido por B. Esta manera va a ganar, porque si B podría en un momento de recoger un inigualable de vértice, el camino recorrido a lo largo del juego podría formar un aumento de camino, pero un camino que nunca existe en un máximo de coincidencia.

Caso 2: El primer vértice $u \in G$ se fija arbitrariamente.

• Supongamos que hay un máximo de coincidencia omitiendo $u$. A continuación, la estrategia ganadora para Un es análoga a la del caso 1.

• Supongamos por el contrario que cada máxima coincidente involucra $u$. Entonces B puede escoger a cualquier máxima coincidente y jugar como antes, es decir, elegir siempre un vértice coincide con el elegido por A. siempre es posible: si pudieran elegir una inigualable vértice $v$, el camino recorrido sería un alternando camino comienza en $u$ y terminando en $v$. Por el desplazamiento de los bordes a lo largo de ese camino, nos producen un máximo de coincidencia omitiendo $u$, el cual fue asumido a ser imposible. Por lo tanto, B es el que gana.

Caso 3: Estamos en un vértice $u \in G$ en algún momento en un juego en progreso. Desde el ya utilizado vértices no son de utilidad para nosotros, podemos eliminarlos de $G$, reduciendo así el caso a la anterior.