+ 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 😉

30th Apr 2017, 2:51 AM
Ace
Ace - avatar
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.
30th Apr 2017, 6:15 AM
Jeth
Jeth - avatar
+ 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
30th Apr 2017, 3:17 AM
Hatsy Rei
Hatsy Rei - avatar
+ 15
Finally! I was worried I might have put a too hard one in 😊
30th Apr 2017, 6:39 AM
Ace
Ace - avatar
+ 14
Ans updated.
30th Apr 2017, 3:28 AM
Hatsy Rei
Hatsy Rei - avatar
+ 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?
30th Apr 2017, 3:36 AM
Ace
Ace - avatar
+ 12
@Siddharth: I was just saying that it's a dangerous assumption to say that the coin values are all equal
30th Apr 2017, 3:38 AM
Ace
Ace - avatar
+ 12
@Jeth: Do you take​ into account that each player may only take a coin from the end each turn?
30th Apr 2017, 5:15 AM
Ace
Ace - avatar
+ 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. 👍
30th Apr 2017, 5:21 AM
Ace
Ace - avatar
+ 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
30th Apr 2017, 3:21 AM
Ace
Ace - avatar
+ 10
@Siddharth not quite: you left out one key step: (1+2+3+4) != (5+6+7+8)
30th Apr 2017, 3:26 AM
Ace
Ace - avatar
+ 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
30th Apr 2017, 5:16 AM
visph
visph - avatar
+ 6
if the value is unknown to the players then anyone can win this game
30th Apr 2017, 4:00 AM
Siddharth Saraf
+ 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
30th Apr 2017, 3:21 AM
Siddharth Saraf
+ 5
the numbers which I have mentioned are the coin numbers not the value of coins
30th Apr 2017, 3:35 AM
Siddharth Saraf
+ 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
30th Apr 2017, 5:43 AM
Aeedoom Aeedad
Aeedoom Aeedad - avatar
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
30th Apr 2017, 4:48 AM
Jeth
Jeth - avatar
0
@Ace. Sure. Look at code methods. There is only "pickLeft" and "pickRight", players can not pick other coins.
30th Apr 2017, 5:16 AM
Jeth
Jeth - avatar