+ 16

# Challenge Question #3 - 2 Player and N Coin Puzzle

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Would you rather go first or second? Does it matter? Of course you need to support your answer with evidence 😉

17 Answers

+ 5

Ok, i got it. I go first, check sum of all odd and even values and pick that coin that belongs to bigger value side (left on odd, right on even). Opponent has no effective response and just pick coin of biggest value like earlier. I get winrate almost 100% with this (with about 0,05% of draws), opponent always have 0 wins. Is this a right answer? I updated my code, you can check algorithm in work.
Anyway, I think this is a good strategy only for a robot or for a man with math superabilities. Or if we play with a few coins. Otherwise it is hard to calculate that numbers in mind fast and if we bring some sort of timer in a game this strategy will not be useful for a human.

+ 16

I'm not sure if there's a catch somewhere for this...
We have scenario 1: All coins are of similar value to each other.
- Two players should get the same amount of money after all coins are collected. Hence, it doesn't matter which end you start with, or who goes first.
We have scenario 2: The coins have different, random values unknown to the players.
- It also doesn't matter who goes first or which end is chosen. Unless...
---------------------------------------------------------
We have scenario 3: The person who goes first gets to survey which coins has the larger values, and then he can choose the more beneficial end. :>
- Following this logic, I would choose to go first.
---------------------------------------------------------
// Extra: C++ simulation for scenario 2.
https://code.sololearn.com/crc6gkwFcL45/?ref=app

+ 15

Finally! I was worried I might have put a too hard one in 😊

+ 14

Ans updated.

+ 12

Last hint: Say this is an example game:
Example 18 20 15 30 10 14
Will it matter who starts? If so what strategy do you take?

+ 12

@Siddharth: I was just saying that it's a dangerous assumption to say that the coin values are all equal

+ 12

@Jeth: Do you take into account that each player may only take a coin from the end each turn?

+ 12

Also @Jeth, you have a win rate let's call it 50-51% of the time. The best route possible has a guaranteed win or draw for one player. That's what I am looking for, but you and Hatsy are both close to the idea. 👍

+ 10

@Hatsy: assume nothing about the value of each coin, only assume you have an even amount of coins.
Yes, each player may take one coin from either end until no more coins left
When game is over whoever has the most money is the winner

+ 10

@Siddharth not quite: you left out one key step:
(1+2+3+4) != (5+6+7+8)

+ 8

@Jeth:
Better strategy to look at biggest value for either end, AND at least look at the next value you will free for the opponent, and eventually choose the lowest value if the biggest free a too big value to be offered to opponent ;P

+ 6

if the value is unknown to the players then anyone can win this game

+ 5

eg, 1 2 3 4 5 6 7 8
I will take coins 1 2 3 and 4
2nd player will take 8 7 6 and 5
both are having 4 coins each so no one can win this game. It will always end with a tie. so either I go 1st or 2nd it will be a tie or draw game

+ 5

the numbers which I have mentioned are the coin numbers not the value of coins

+ 4

I think I would pick my coin depending on the following:
-If I pick right, what is the largest coin of the two that my opponent can pick and I will subtract that from the value of the right coin
-if I pick left, find the largest coin again that my opponent can pick and subtract that from the value of the left coin
-Compare the two values and pick right or left depending on which value is bigger
just a guess, I should run a loop to test it but I'm super tired haha

0

My strategy: go first and pick coin with biggest value. In a big number of games (10000 with a 1000 coins in each) i get a winrate slightly more than 51% (can not test such numbers in a playground because of server memory limit, tested locally). In less amount of games winrate is slightly higher. Explanation is in code below:
https://code.sololearn.com/cBDvek1AYIF3/?ref=app

0

@Ace. Sure. Look at code methods. There is only "pickLeft" and "pickRight", players can not pick other coins.

Hot today

Задача 58.2

1 Votes

What i do wrong ?

0 Votes

Please rearrange int array:

0 Votes

Sololearn bug

1 Votes

Locked out by Rocket Icon

2 Votes

Помогите с кодом автобуса

0 Votes

Starting learning Python

0 Votes