5
$\begingroup$

Bob and Alice are playing a game. Initially they have balls of black and white color arranged together in a line.
Rules of the game are as follows:

1.They start the game by going from right to left till the last ball is reached. Whenever a black ball is found, Bob can either change its color to white or do nothing. Similarly whenever a white ball is found, Alice can either change its color to black or do nothing.

NOTE:Above step is repeated till we reach the goal.

2.Goal of the game is make all balls of white color and when this happens Bob wins.Now Alice's aim is to not let Bob win (by making it an indefinite play) or to delay Bob's win (if it’s sure).

3.So now assuming that they both play with their optimal strategy and from given configuration of balls, can we determine if Bob can win the game or not?

Note: There has to be AT LEAST 1 scan(step 1) before the game can end.

Example: Initial configuration: BW

During the first scan, Alice gets the first turn because the right most ball is of White color. She has to change it or the game will be over in a single scan. In the next turn, Bob chooses to keep his bit unchanged. So after first scan, the configuration is now “BB”. In the next scan, Alice has no turns. So Bob will change both Black balls and thus end the game.

Also if Bob wins can we also find in how many scans did he win assuming both players play optimally??(in above example we require 2 scans for winning the game.)

$\endgroup$
2
$\begingroup$

This has received too little attention; it's a very nice puzzle.

I'll solve a slightly different game (which may in fact be the game you intended to describe, since it has a much nicer solution). Instead of requiring that there be at least one scan, I'll assume that Bob wins only when the balls are all white between scans, not in the middle of a scan.

Denote the number of balls by $n$. Interpret the white balls as $1$s and the black balls as $0$s of the binary representation of a number $k$. Then the number of scans Bob needs to win is $k+1$ (where the addition is carried out in $n$ bits with overflow, so that if all balls are white, the result is $0$).

We can prove this by strong induction. The base cases, $k+1=0$ and $k+1=1$, are clear. So assume that Bob wins after $k+1$ scans for all $k\lt m$. Starting from the right, as long as Alice doesn't flip any balls, Bob can flip all black balls encountered. At some point, Alice has to flip a white ball, since otherwise Bob will win after this scan. But when she does, the bit value of the ball she flips will be greater than that of all the balls Bob flipped together. If Bob stops flipping balls at this point, the binary number will have decreased by at least one during this scan, so by the induction hypothesis Bob will win after at most $m+1$ scans. On the other hand, by using her very first opportunity to flip, Alice can make sure that the binary number decreases by at most one, so Bob will win after at least $m+1$ scans, and thus after exactly $m+1$ scans.

This doesn't quite work out if Bob can win in the middle of a scan, because Alice is then forced to flip higher bits earlier. You can probably use this as a basis for solving your problem, too, but I'm hoping that it was just an error in the presentation and you wanted to solve this nicer problem :-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.