0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ Jun 28 '14 at 16:20
  • $\begingroup$ @MarcvanLeeuwen Yeah coin cant be placed before. $\endgroup$
    – user157452
    Jun 28 '14 at 16:21
  • $\begingroup$ In the example, can't player 1 win by picking the blue coin at the start? $\endgroup$
    – Wonder
    Jun 28 '14 at 16:24
  • $\begingroup$ @Wonder player1 starts the game always $\endgroup$
    – user157452
    Jun 28 '14 at 16:25
  • 1
    $\begingroup$ @Wonder Sorry my mistake in this case obviously player1 will win $\endgroup$
    – user157452
    Jun 28 '14 at 16:29
0
$\begingroup$

It seems like the second player's best option is to always put a coin of the opposite colour if one is left, while the first player's best option is likewise to to always match the last. Then every pair of a move of the first player followed by a move of the second player uses a pair of opposite colours, until no more such pairs can be formed.

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

$\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.