Un rompecabezas sobre el gráfico para colorear.

Question

Deje $G$ un gráfico con tres distintos triángulos(es decir, la gráfica no es connectd y tiene tres componentes conectados cada uno de los cuales es un triángulo). Si cada vértice de G se le asigna un rojo o un color verde, entonces decimos que la de un borde es de color si sus extremos tienen diferentes colores. La persona a y la Persona B color de los vértices de G de la siguiente manera. Una propone un color (rojo o verde) y B elige el vértice para aplicar este color. Después de 9 vueltas, todos los vértices de G son de color y el número de bordes de color se cuenta. Supongamos que Una quisiera maximizar el número de colores de los bordes, mientras que B gustaría reducir el número de colores de los bordes. Suponiendo óptimo de juego de ambos jugadores, la cantidad de bordes serán de color?

Este es un juego de rompecabezas me gustaría saber la respuesta. Sospecho que, finalmente, los dos triángulos del mismo color para todos los vértices mientras que el tercero se tienen dos iguales y uno diferente color.

¿Cuál es la lógica correcta?

Answer 1

Su conjetura es correcta. B siempre gana por un marcador de $7$ a $2$.

Nos muestran que la primera B tendrá asegurada la victoria por el quinto movimiento.

Al final del juego, cualquier triángulo con un color que va para la persona B con una puntuación de $3$ a $0$ y cualquier triángulo con dos colores va a por Un resultado de $2$ a $1$. Por lo tanto, si B se puede llenar cualquiera de los triángulos con un color, gana por una puntuación de al menos $5$ a $4$.

Para evitar la pérdida dentro de los tres primeros se mueve, se debe elegir dos de un color y uno de los otros. B coloque los dos al igual que los colores en el mismo triángulo y el color diferente en otro triángulo. Digamos que el primer triángulo tiene dos de color verde vértices, el segundo triángulo, uno de color rojo vértice y el tercer triángulo está vacía. Si elige verde, B va a llenar en el primer triángulo y asegurar la victoria. Si elige rojo, triángulo 1 se tienen dos de color verde vértices y el triángulo 2 tendrá dos rojo los vértices. No importa el color que Una persona elige a, B será capaz de ganar un completo triángulo en el siguiente movimiento.

Continuar el juego, después de $5$ mueve triángulo 1 se todo de un solo color(verde) y el triángulo 2 wll tener dos de un color(rojo). Si elige verde, B colocará en el tercer triángulo. Si elige Un color rojo, B va a llenar en el segundo triángulo y se han ganado dos triángulos. Finalmente, Una elige otro rojo dando a B triángulo 2 o elige todos los greenes, que da B triángulo de 3 y Un triángulo de 2. Por lo tanto, B gana a $7$ a $2$.

Answer 2

Suponiendo juego óptimo, habrá 4 de color de los bordes.

En primer lugar, las únicas respuestas posibles son 0,2,4 o 6 colores de los bordes. (Si un triángulo tiene dos colores, contribuye de dos filos. De lo contrario, contribuye a cero bordes)

La próxima, a ver que B siempre puede llene completamente un triángulo con un solo color: Sin pérdida de generalidad, supongamos que Una da a la red de primera. Entonces, B pone rojo en el triángulo 1. Si elige verde, B pone en los otros triángulos. Cuando Un da rojo, va en triángulo 1. Si elige Un rojo de más de 3 veces, triángulo 1 se pone de color completamente rojo. Si no, triángulo 2 y 3 de color totalmente verde.

Por último, siempre se puede asegurar que hay al menos 4 de color de los bordes. Mira la secuencia de $r,r,r,g,g,g,g,g,g$. Sólo hay tres maneras posibles de que el color rojo puede ser distribuido, y en cada caso de conseguir al menos 4 de color de los bordes.

Por lo tanto, con un óptimo de juego, habrá 4 de color de los bordes.

Answer 3

Esto es una tentativa de respuesta, como no tengo una prueba de que esta es la mejor estrategia en cualquier parte, pero podría ser útil no es menos.

La selección de primera, por supuesto, no importa, así que dicen que es rojo ($r$), por lo que tenemos los triángulos: $$ (r,\cdot,\cdot), (\cdot, \cdot, \cdot), (\cdot, \cdot, \cdot) $$ Si $A$ picks $r$ nuevo, $B$ puede poner en el primer triángulo, que es una pérdida para $A$, después de aplicar la misma idea, $A$ puede escoger $$ (r,\cdot,\cdot), (g, \cdot, \cdot), (\cdot, \cdot, \cdot) $$

Entonces no importa si $A$ picks $r$ o $g$, $B$ puede colocar en $B$'s favor (por lo que dicen es $r$) $$ (r,r,\cdot), (g, \cdot, \cdot), (\cdot, \cdot, \cdot) $$

$(\ast)$Si $A$ mantiene picking $r$, $B$ puede forzar a dos monocromo triángulo antes de la coloración de vértices en el segundo triángulo: $$ (r,r,r), (g, r, \cdot), (r,r,r) $$ A continuación, $A$ acabados con 2 bordes.

Si en $(\ast)$ $A$ selecciones $g$, $B$ puede colocar en el segundo triángulo: $$ (r,r,\cdot), (g, g, \cdot), (\cdot, \cdot, \cdot) $$ $A$ no puede recoger $r$ o $g$ sin perder un triángulo y, a continuación, elegir el color para la recogida después de perder otro triángulo, por lo $A$'s mejor opción es escoger un color dos veces: $$ (r,r,r), (g, g, \cdot), (r, \cdot, \cdot) $$ Pero entonces estamos de vuelta a una posición similar como $(\ast)$ si $A$ en cualquier punto de la coge $g$, entonces el segundo triángulo se pierde a $B$, pero sólo recogiendo $r$ pierde el tercero, por lo que en cualquier caso la mejor $A$ puede obtener es de dos aristas de los triángulos (elegir el mismo color para los últimos tres movimientos): $$ (r,r,r), (g, g, r), (r, r, r) $$