Paul has invited his friends Bob and Marry to his house for dinner. After having dinner Marry
Question:
Paul has invited his friends Bob and Marry to his house for dinner. After having dinner Marry proposed a game, Two color game.
In this game, Marry will take X blue stones and Y green stones and she will arrange them in any order. According to Marry, the game consists of iterating over the stones from left to right, the player to whom the current stone belongs has the right to remove one of the opponent's stones from the arrangement. The player that remains with no stones loses the game.
Now, she gave Paul the chance to decide the color of his stone (Blue or Green) and the other color stone will belong to Bob. Your task is to tell the color Paul should choose to win the game.
You are given X and Y denoting the number of blue stones and number of green stones respectively, and a string S, denoting the arrangement of stones..
Task
Determine the color of stone Paul should choose to win the game, "Blue" or "Green".
Notes
String S consists of only two characters 'b' and 'g' representing blue and green color stones respectively. The string will contain exactly X blue stones 'b' and exactly Y green stones 'g. Both the players will play optimally for victory. If some player is at the end of the string next iteration will start from the beginning of the string.
Example
Assumptions
X-2
Y=3
S-bbggg
Approach
Suppose Paul chooses Blue stone for himself.
? The first stone is 'b' so it's Paul's move as he has chosen the blue color stone, now he can remove any stone which belongs to Bob le stone 'g'. Let's say in the 1st move Paul removes 3rd stone then the arrangement becomes bbgg" the next stone is also 'b' so it's again Paul's move. Let's say in the 2nd move Pauls removes the 3rd stone from bbgg" then the arrangement becomes bbg "now the next Auto stone is 'g' so it's Bob's move.
Let's say in the 3rd move Bob removes 1st stone from "bbg then the arrangement becomes 'bg now the end of the string is reached so iteration will restart and the next move will belong to Paul. In the 4th move, Paul will remove 2nd stone from "bg" and the arrangement becomes "b
B
9
10
As there is no Green stone 'g' left and Paul had chosen
11
22
the Blue color b' so Paul wins.
23 14
Hence the answer will be "Blue".
T for
15
16
Note: There can be other possible choices for removal of opponent stones but the final winner in an optimal game will remain the same.
Microeconomics An Intuitive Approach with Calculus
ISBN: 978-0538453257
1st edition
Authors: Thomas Nechyba