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.
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.)