¿Que los jugadores primero dibujará un triángulo?

Question

6 vértices están dados. No hay bordes son dictadas en primera. Dos jugadores jugar el siguiente juego: el primer jugador saca un borde negro. A continuación, el segundo jugador dibuja un borde verde. A continuación, el primer jugador saca un borde negro de nuevo, y así sucesivamente. El juego termina cuando uno de los jugadores ha dibujado un triángulo con todos los bordes del mismo color. El ganador es el de su adversario. Cual de los jugadores gana siempre utilizando la mejor estrategia? ¿Cuál es su estrategia ganadora?

Tal vez puedo usar algunos resultados de la teoría de grafos para encontrar la estrategia ganadora, pero no puedo ver nada útil.

Answer 1

El primer jugador pierde.

Esta es una forma particular de un juego llamado Sim, correspondiente al hecho de que el número de Ramsey $R(3,3)$$6$, se introdujo por primera vez por Gustavus Simmons en 1969.

Para mucho más, incluyendo variantes, la clasificación de algunas de estas variantes en términos de complejidad computacional, y muchas preguntas abiertas, ver

Wolfgang Slany. Gráfico Ramsey juegos. ArXiv:cs/9911004.

Un argumento pictórico que describe una ejecución del juego que termina en victoria para el segundo jugador en la Sim para 6 vértices se presenta en la página 3 de la preimpresión. Teorema 22 (en la página 32) es la afirmación de que esto es en general. La prueba que se describe como "más o menos una muy larga enumeración de casos" (análisis de 2309 posiciones). El resultado parece haber sido establecido por primera vez en

Ernest Mead, Alejandro Rosa, y Charlotte Huang. El juego de SIM: UNA estrategia ganadora para el segundo jugador, Mathematics Magazine, 47 (5), (1974), 243-247.

Ninguna estrategia distinta a muy largo análisis de casos parece que actualmente se conoce.