24
$\begingroup$

3 people are blindfolded and placed in a circle. 9 coins are distributed between them in a way that each person has at least 1 coin. As they are blindfolded, each person only knows the number of coins that they hold, but not how many coins others hold. Each round every person must (simultaneously) pass 1 or more of their coins to the next person (clockwise). How can they all end up with 3 coins each? Before the game they can come up with a collective strategy, but there cannot be any communication during the game.

Improve this question
$\endgroup$
2
  • $\begingroup$ They do all know that there are 9 total coins, right? $\endgroup$
    – dan04
    Jul 20, 2022 at 20:36
  • $\begingroup$ yes they know there are 9 coins $\endgroup$
    – Dmitry Kamenetsky
    Jul 21, 2022 at 0:57

9 Answers 9

Reset to default
27
$\begingroup$

They can do the following:

If you have three or more coins, pass all but two coins.
If you have two or fewer coins, pass one coin.
Do this for two rounds and then stop.

This works because:

Everyone has to pass at least one coin every round, so ignore one coin each for now (that just get passed round the table) and solve the simpler problem of distributing the remaining six coins so that everyone gets two each.

And that can be achieved by having anyone with more than two coins passing all their excess coins. After at most two rounds everyone has two coins of those six.

Then adding back in the three we ignored earlier, everyone now has three coins.

We can also just list all the possible coin distributions and show that they end up with three coins each. With each player passing to the right:

 7,1,1 -> 3,5,1 -> 3,3,3
 6,2,1 -> 3,5,1 -> 3,3,3
 6,1,2 -> 3,4,2 -> 3,3,3
 5,3,1 -> 3,5,1 -> 3,3,3
 5,1,3 -> 3,3,3 -> 3,3,3
 5,2,2 -> 3,4,2 -> 3,3,3
 4,4,1 -> 3,4,2 -> 3,3,3
 4,3,2 -> 3,4,2 -> 3,3,3
 4,2,3 -> 3,3,3 -> 3,3,3
 3,3,3 -> 3,3,3 -> 3,3,3

Improve this answer
$\endgroup$
12
  • $\begingroup$ you got it, well done! I had a slightly different solution, but it worked with a similar principle. $\endgroup$
    – Dmitry Kamenetsky
    Jul 18, 2022 at 9:34
  • $\begingroup$ I believe something similar works for any number of people too. $\endgroup$
    – Dmitry Kamenetsky
    Jul 18, 2022 at 9:35
  • $\begingroup$ @DmitryKamenetsky There is a more general solution that allows any number of people to produce any distribution they want, but it's slower than this method. $\endgroup$
    – fljx
    Jul 18, 2022 at 10:51
  • 6
    $\begingroup$ For N players. Designate one player as the leader, and count positions starting with the player on their right as 2, up to N on their left. Everyone else just passes all the coins they have on every turn. For the first N-1 turns, the leader passes the minimum 1, so that they collect all the coins except the N-1 distributed to everyone else. For the next N-1 turns, the leader passes out the target number of coins for each player, starting with player N and working backward. $\endgroup$
    – fljx
    Jul 18, 2022 at 12:45
  • 1
    $\begingroup$ By the way here is my intended solution rot13(Vs lbh unir yrff guna 3 pbvaf gura cnff gurz nyy, bgurejvfr cnff 3 pbvaf.) $\endgroup$
    – Dmitry Kamenetsky
    Jul 18, 2022 at 13:06
12
$\begingroup$

Another strategy:

Each round each player tries to pass 3 coins to his neighbor. If one has less coins, he gives what he has.

And it works because...

Consider not the coins, but the difference in coins compared to 3. If there are too many, >3, consider the excess coins. If there are too few, consider the defects as holes.
As the rules are made, the coins in excess will remain in place while the holes will turn from player to player until they meet an excess coin and get annihilated.

Intuitively, but without proof, a hole will never need to do a whole round around all players and back to the originating player before meeting an excess coin, so the game should end in <N rounds (i.e. the number of players). It should end in 2 rounds in this specific case.

You might wonder: what if it is the excess coins that are turning and the holes that are held in place? Well, you get fljx's solution.

PS: And I realize Dmitry already gave that solution in a crypted comment.

Improve this answer
$\endgroup$
5
$\begingroup$

This can be solved in no more than 4 passes independent of the number of coins that everyone has. (I.E. Start with 201 coins with each person having 67 at the end, after 4 passes.)

Answer: First 2 rounds pass all coins, at that point you have seen all of the coins, add them up, and pass any you have over that, plus 1 on each round. 2 more rounds and they are all even

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ I think just 1 pass of all coins is enough to know how many coins everyone has. $\endgroup$
    – TTT
    Jul 19, 2022 at 3:22
  • 1
    $\begingroup$ @TTT only assuming you know in advance the total number of coins. $\endgroup$
    – Florian F
    Jul 21, 2022 at 9:12
  • $\begingroup$ @FlorianF Good Point! (I assumed that was the case, and I see others have assumed the opposite. I suppose it wasn't stated for sure either way in the question, so better not assume it.) Though, it appears the accepted answer assumes it too... $\endgroup$
    – TTT
    Jul 21, 2022 at 14:17
  • $\begingroup$ In the original question the target is to get 3 coins each. So I would assume the total is known. But this post tries to solve a more general case and you are right, it is not clear whether people still know what the total is. $\endgroup$
    – Florian F
    Jul 21, 2022 at 15:06
5
$\begingroup$

Another simple solution is this

Each round everyone passes half their coins rounded up. If you have held 3 coins at the end of the last two rounds then it is over.

Some worked examples are

7,1,1 -> 4,4,1 -> 3,4,2 -> 2,4,3 -> 3,3,3 -> 3,3,3
6,2,1 -> 4,4,1 -> 3,4,2 -> 2,4,3 -> 3,3,3 -> 3,3,3
6,1,2 -> 4,3,2 -> 3,3,3 -> 3,3,3
5,3,1 -> 3,4,2 -> 2,4,3 -> 3,3,3 -> 3,3,3
5,1,3 -> 4,3,2 -> 3,3,3 -> 3,3,3
5,2,2 -> 3,4,2 -> 2,4,3 -> 3,3,3 -> 3,3,3
4,4,1 -> 3,4,2 -> 2,4,3 -> 3,3,3 -> 3,3,3
4,3,2 -> 3,3,3 -> 3,3,3
4,2,3 -> 4,3,2 -> 3,3,3 -> 3,3,3
3,3,3 -> 3,3,3

Although this solution takes more rounds than some of the above, I like the simplicity of the algorithm. Its kind of like osmosis, with the fluctuations being smoothed out a little each round.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ The power of this solution, compared to all the others offered, is that you don't need to know how many people there are, or how many coins. All you really need to know is that the coins can be evenly divided. Having said that, OP's answer and the (currently) accepted answer need a number of turns approximately equal to the number of people. This algorithm needs closer to the number of coins. A very lopsided distribution of 10000 coins and 100 people took 6499 turns. $\endgroup$
    – David G.
    Jul 20, 2022 at 5:17
  • $\begingroup$ @DavidG. for more people, the stopping condition is when you hold the target number of coins for the last N-1 turns? $\endgroup$
    – justhalf
    Jul 20, 2022 at 10:33
  • $\begingroup$ @justhalf My point is that you should not have a "target number of coins". or know "N". And that this solution requires neither. $\endgroup$
    – David G.
    Jul 20, 2022 at 13:12
  • $\begingroup$ Then what is the stopping condition if you don't know N? $\endgroup$
    – justhalf
    Jul 20, 2022 at 14:05
  • $\begingroup$ I actually think there is no way to devise a stopping condition without knowing N. When passing coins each round you have no idea whether you are part of a loop of 3 or 3000. Even if you have had the same amount of coins for many rounds, if you are part of a long chain then there could be coins making their way around the loop to you. All you can do is keep passing and knowing that it will work eventually, assuming the loop is finite. $\endgroup$
    – James Fulton
    Jul 21, 2022 at 9:39
1
$\begingroup$

What about this simple way of working? Let's call A, B and C the 3 persons, in clockwise order.

A gives all his coins to B
B gives all his coins (own + received from A) to C. Now C knows the total number of coins
C keeps 1/3 of the coins and gives 2/3 to A
A keeps 1/2 of the received coins and gives the other half to B

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Sorry I should have made instructions more clear. They each must pass coins every round. $\endgroup$
    – Dmitry Kamenetsky
    Jul 18, 2022 at 8:08
1
$\begingroup$

I guess they know there are a total of 3 people and 9 coins, I was thinking they didn't know how many coins... If they don't know how many coins there are, but they do know there are n people...

Phase 0 (Planning) - Designate one person as leader

Phase 1 (Leader gets the most possible coins) - For 'n-1' rounds, leader passes 1 coin, everyone else passes all their coins. At the end, everyone but the leader has 1 coin, the leader has the rest.

Phase 2 (Keep what you need) - For 'n-1' rounds starting with the leader and moving on to the person that gets the extra coins each round, keep enough so that you will have the same as everyone else.

Phase 2 works because everyone will be passing 1 each round except for one person, and you know how many monks and how many turns it's been, so when you get more than one you will know how many people are left and the total coins they have. For an example, imagine 5 monks and 100 coins. After 4 rounds, everyone will have passed their coins to the leader, who will have 96 coins while the others have 1. The leader knows there are 4 people remaining, so there is a total of 100 to divide between him and the other 4, so each person must have 20 coins. He also knows he will be getting 1 coin each round, so he keeps 19 and gets passed one to get 20. Each following round he will pass one coin and be passed one coin so he will end up with 20.

The other four don't know who will get the extra coins the first round, but whoever does get the 77 from the leader will know there are 3 rounds left so the total will be 80 divided by 4 people. He will also know then that each should have 20 so keep 19 and pass the rest (58), knowing he will receive 1 that round from the leader to end up with 20. After passing those coins he will pass and receive 1 coin each round to end up with 20. The person that receives those 58 will know there are two left so it will be 60/3 and each should have 20 coins. He will keep 19 and pass the other 39, receiving 1 to have 20 at the end of the round. The next monk will receive 39, pass 20 to keep 19, and receive 1 to end up with 20. After those 4 rounds, everyone will have 20.

If there are n coins exactly, everyone just ends up passing 1 around for $2(n-1)$ rounds.

Improve this answer
$\endgroup$
1
$\begingroup$

Just because rules are made to be subverted:

Everyone passes all their coins to their neighbour until everyone knows where all the coins are. Then the people currently with the most coins pass 2 coins, and everyone else passes 1 coin, until they finish.

It works because

the maximum number of coins and the number of piles with that maximum size cannot increase. Moreover, each "extra" coin cannot return to its starting position, because someone else must have a "missing" coin where the "extra" coin is "trapped".

Improve this answer
$\endgroup$
0
$\begingroup$

They can follow this rule:

You pass the amount of coins you have divided by 2 rounded down. So if for example you have 3 coins you pass 1. Only exception is if you have only one you must pass it (as per the rules). After they do this for a maximum of 4 times they all end up with 3 coins.

this is every possible result
7,1,1 -> 5,3,1 -> 4,4,1 -> 3,4,2 -> 3,3,3
6,2,1 -> 4,4,1 -> 3,4,2 -> 3,3,3 -> 3,3,3
6,1,2 -> 4,3,2 -> 3,4,2 -> 3,3,3 -> 3,3,3
5,3,1 -> 4,4,1 -> 3,4,2 -> 3,3,3 -> 3,3,3
5,1,3 -> 4,2,3 -> 3,3,3 -> 3,3,3 -> 3,3,3
4,4,1 -> 3,4,2 -> 3,3,3 -> 3,3,3 -> 3,3,3
4,3,2 -> 3,4,2 -> 3,3,3 -> 3,3,3 -> 3,3,3
4,2,3 -> 3,3,3 -> 3,3,3 -> 3,3,3 -> 3,3,3
3,3,3 -> 3,3,3 -> 3,3,3 -> 3,3,3 -> 3,3,3

I'm almost sure this works without the need to know how many coins or people there are total (as long as the coins can be equally divided by the amount of people)

Improve this answer
$\endgroup$
-3
$\begingroup$

Pass Entire coins to next person until 9 coins collected by last person , when last person has 9 coins in his hand pass exactly 6 coins to first person , and first person should pass 3 coin to the next person , Problem solved ;)

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This answer does not work, because the last person can not collect all 9 coins. "Each round every person must (simultaneously) pass 1 or more of their coins to the next person (clockwise)." $\endgroup$
    – xyldke
    Jul 19, 2022 at 6:47
  • $\begingroup$ i am sorry i missed simultaneously part $\endgroup$
    – Shebin KP
    Jul 19, 2022 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.