Juego de cuerdas palindrómicas

Question

Hay dos jugadores $A$ , $B$ jugando una partida. Jugador $A$ tiene una cadena $s$ con él, y el jugador $B$ tiene una cadena $t$ con él. Ambos $s$ y $t$ están formados únicamente por letras inglesas minúsculas y tienen la misma longitud. $A$ hace el primer movimiento, entonces $B$ entonces $A$ y así sucesivamente. Antes de comenzar la partida, los jugadores conocen el contenido de las dos cadenas $s$ y $t$ .

Estos jugadores están construyendo otra cadena $w$ durante el juego. Inicialmente, la cadena $w$ está vacía. En cada movimiento, un jugador elimina un carácter cualquiera de su cadena respectiva y añade este carácter en cualquier lugar (en cualquier posición) de la cadena $w$ . Si en cualquier etapa del juego, la cadena $w$ tiene una longitud superior a $1$ y es un palíndromo, entonces gana el jugador que hizo la última jugada.

Si incluso después de que el juego termine (es decir, cuando ambos $s$ y $t$ se han convertido en cadenas vacías), nadie es capaz de hacer que la cadena w sea un palíndromo, entonces el jugador $B$ gana.

Mi estrategia
Si cualquier carácter ( $a-z$ ) tiene una frecuencia mayor que $1$ en cadena $s$ y no está presente en $t$ así que $A$ ganará de otra manera $B$ .

¿Es correcto mi planteamiento? ¿O hay alguna otra forma de $A$ ¿para ganar?

Answer 1

No estoy seguro de estar en lo cierto, pero esta es mi estrategia:
Si asumimos los caracteres de la cadena s como un conjunto A y los caracteres de la cadena t como un conjunto B.

1.Si B es un subconjunto de A, entonces A ganará
Por ejemplo: aabbe ab
A ={a,b,e} B={a,b}
El jugador A usará e al principio y luego B se ve obligado a usar uno de los personajes que tiene A para que éste pueda igualarlo y ganar.

2.Si A es un subconjunto de B, entonces B ganará
Ej:aabb aabbe
Esto es bastante obvio porque lo que A utiliza B lo iguala y gana el juego

3.Si A y B son iguales, entonces B ganará Ej: aabbcc aabbc
Cualquier cosa que use A es igualada por B y, por lo tanto, B gana.

4.Si A tiene 2 o más de los mismos personajes que B no tiene, entonces A ganará.
Por ejemplo: aabbc cbbe
A utilizará a al principio.
Como B no tiene a, intentará utilizar uno de los otros caracteres y A volverá a coincidir para formar un palíndromo.

5.Si A y B no son subconjuntos el uno del otro, entonces B gana: s=aabcdef t=abcdgh
A={a,b,c,d,e,f} t={a,b,c,d,g,h}
Obviamente A intentará usar un carácter que B no tiene(e o f),B también usará un carácter que A no tiene(g o h).Creo que al final B intentará que A no forme un palíndromo y así ganar.

Sin embargo, no estoy seguro de que sea correcto.

Answer 2

Crédito: Anantha propuso una solución sin una prueba completa. Yo sólo proporciono la prueba de que la solución es realmente correcta.

Dejamos que los caracteres de la cadena $s$ como un conjunto $S_A$ y los caracteres de la cadena $t$ como un conjunto $S_B$ .

Reclamación: Si $S_B \subsetneq S_A$ o si el jugador $A$ contiene al menos $2$ cartas que $B$ no tiene , entonces el jugador $A$ gana. En caso contrario, el jugador $B$ gana.

Prueba:

Caso $1$ : Si $S_B \subsetneq S_A$ . Jugador $A$ utilizaría primero la letra que el jugador $B$ no tiene. De ahí que el jugador $B$ no puede formar un palíndromo durante su turno. Jugador $A$ colocaría entonces lo que ese jugador $B$ colocado para terminar el juego.

Caso $2$ : Si el jugador $A$ contiene $2$ cartas que el jugador $B$ no tiene. Jugador $A$ utilizaría una de estas cartas en su primer movimiento y el jugador $B$ no puede formar un palíndromo ya que no tiene esta letra. Jugador $A$ y luego terminar el juego colocando la misma carta que usó en su primer movimiento.

Caso $3$ : Si $S_A \subseteq S_B$ . Lo que sea que ese jugador $A$ lugar, jugador $B$ sólo tiene que copiar eso para terminar el juego.

Caso $4$ : Si no ocurre nada de lo anterior, afirmamos que el jugador $B$ ganaría. Durante el jugador $A$ El primer movimiento del jugador, utilizará una carta que el jugador $B$ no tiene. Llamemos a esta carta $l_A$ . Durante el jugador $B$ El primer movimiento del jugador $B$ también utilizará una letra que el jugador $A$ no tiene, llámalo $l_B$ . Desde el caso $2$ no ocurrió, sólo hay una copia de $l_A$ . Si el jugador $A$ para ganar el juego, tiene que formar un palíndromo de longitud impar, por lo que tiene que colocar $l_A$ en medio del palíndromo. Sin embargo, no tiene $l_B$ que es necesario para formar un palíndromo. Por lo tanto, no hay manera de que $A$ para ganar el juego en este caso.

Observación: La estrategia de OP dejó fuera el caso $1$ .