# Game of coins with two players

Two Players play a game as follow : Given total N coins where x coins are of red color and y coins of blue color. Now Player1 selects a coin from the heap of coin and put it in a line on table. Then, Player2 picks another coin from the remaining coins, and put it next to coin being put by player1 in earlier move. Both players then take alternate turns, until all the coins are used.

If the number of pairs of neighboring coins of the same color is GREATER than the number of pairs of neighboring coins of the opposite color, output "Player1 wins!" , otherwise, "Player2 wins!"

Note : Player2 will always try to put coin of opposite color.

I need to find who will win the game.

Example : If N=4 and we have 3 red coins and 1 blue coin then Player1 will win in this case.

• I suppose the line of coins must always be extended at the same end; in other words player do not have the option to place a coin before (and next to) the first coin? Commented Jun 28, 2014 at 16:20
• @MarcvanLeeuwen Yeah coin cant be placed before. Commented Jun 28, 2014 at 16:21
• In the example, can't player 1 win by picking the blue coin at the start? Commented Jun 28, 2014 at 16:24
• @Wonder player1 starts the game always Commented Jun 28, 2014 at 16:25
• @Wonder Sorry my mistake in this case obviously player1 will win Commented Jun 28, 2014 at 16:29

Suppose by symmetry that $x\geq y$. Since there will be $y$ opposite colour pairs played in the first $2y$ moves and the first player has the choice for the very first move, she can arrange that the coin played in move $2y$ is red (for this, start blue if $y$ is odd, or red if $y$ is even). After move $2y$ there will be $y$ opposite colour pairs and $y-1$ same-colour pairs, so the second player is one ahead, and also has the advantage that equal numbers lead to a victory of player 2. But the remaining $x-y$ coins will all be red and of the same colour as the coin before, so player 1 wins as soon as $x-y\geq2$. For symmetry, the general condition for a victory of player 1 should be stated as $|x-y|\geq2$.