5 votos

Coloreando las bolas

Bob y Alice están jugando un juego. Inicialmente se tienen las bolas de color en blanco y negro colocados juntos en una línea.
Las reglas del juego son como sigue:

1.Que inicie el juego va de derecha a izquierda hasta la última bola que se alcanza. Cada vez que una bola negra se encuentra, Bob puede cambiar su color a blanco o no hacer nada. Del mismo modo cada vez que una bola blanca se encuentra, Alice puede cambiar su color a negro o de no hacer nada.

NOTA:el paso Anterior se repite hasta llegar a la meta.

2.Objetivo del juego es hacer que todas las bolas de color blanco y cuando esto sucede Bob gana.Ahora Alice objetivo es no dejar que Bob ganar (por lo que es indefinido play) o a la demora de Bob ganar (si es cierta).

3.Así que ahora suponiendo que ambos juegan con su estrategia óptima y de configuración de bolas, podemos determinar si Bob puede ganar el juego o no?

Nota: No tiene que ser de AL MENOS 1 scan(paso 1) antes de que el juego puede terminar.

Ejemplo: Configuración inicial: BW

Durante el primer análisis, Alice recibe la primera vuelta debido a que el derecho de la mayoría de la bola es de color Blanco. Ella tiene que cambiar o el juego habrá terminado en una sola exploración. En el turno siguiente, Bob decide mantener su bits sin cambios. Así que después de la primera exploración, la configuración es ahora "BB". En el siguiente análisis, Alice no tiene vueltas. Así que Bob va a cambiar las dos bolas Negras y así terminar el juego.

También si Bob gana podemos encontrar también en cuántos análisis hizo ganar si ambos jugadores juegan de manera óptima??(en el ejemplo anterior requerimos 2 exploraciones para ganar el juego.)

2voto

JiminyCricket Puntos 143

Este ha recibido muy poca atención; es un muy buen rompecabezas.

Voy a resolver un juego ligeramente diferente (que puede ser en realidad el juego que pretende describir, ya que tiene una mucho mejor solución). En lugar de exigir que haya al menos un scan, voy a asumir que Bob gana sólo cuando las bolas son blancas entre exploraciones, no en el medio de la exploración.

Indicar el número de bolas por $n$. Interpretar las bolas blancas como $1$s y las bolas negras como $0$s de la representación binaria de un número $k$. A continuación, el número de exploraciones Bob necesita para ganar es $k+1$ (cuando la adición se lleva a cabo en $n$ bits con rebosadero, de modo que si todas las bolas son de color blanco, el resultado es $0$).

Podemos probar esto por una fuerte inducción. La base de los casos, $k+1=0$$k+1=1$, son claras. Así que supongamos que Bob gana después de la $k+1$ busca todas las $k\lt m$. A partir de la derecha, mientras Alice no voltear los pelotas, Bob puede voltear todas las bolas negras encontrado. En algún momento, Alice tiene que girar la bola blanca, ya que de lo contrario Bob va a ganar después de esta exploración. Pero cuando ella lo hace, el valor de bits de la pelota que ella voltea será mayor que el de todas las bolas de Bob volteado juntos. Si Bob deja de voltear las bolas en este punto, el número binario se han disminuido en por lo menos uno durante esta exploración, así que por la hipótesis de inducción Bob va a ganar después de que en la mayoría de las $m+1$ análisis. Por otro lado, mediante el uso de su primera oportunidad para voltear, Alice puede asegurarse de que el número binario disminuye en más de uno, así que Bob va a ganar después de al menos $m+1$ exploraciones, y por lo tanto después de exactamente $m+1$ análisis.

Esto no funciona si Bob puede ganar en el medio de la exploración, ya que Alice se ve obligado a voltear mayor bits anteriores. Usted probablemente puede utilizar esto como una base para la solución de su problema, demasiado, pero tengo la esperanza de que fue sólo un error en la presentación y que quería resolver este problema más agradable :-)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X