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.
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
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.
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
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.
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
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
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.
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".
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)