Answer to the coin puzzle
Answer to the puzzle
Let’s say the folks are 1,2,3,4,5
Let’s start with the situation – what happens when only 4 and 5 are left? 4 is going to say he will keep all 100 and give nothing to 5. 5 will disagree but it does not matter. 4 wins with a 1-1 vote. So, 5 realizes in the beginning that if the process does not stop before it gets to this situation, he will get nothing. His best hope is to get at least 1.
What if 3,4,5 is there? 3 knows that 5 will vote yes if he is given 1. 3 will say that he will keep 99 for himself, give nothing to 4 and 1 to 5. 4 will disagree but 5 1ill agree. The vote carries by 2-1.
What is 2,3,4,5 is there? Now, realize that 5 is hoping to get 1. 4 is also hoping to get 1. Because if it comes down to 3,4 and 5, as we saw before, 4 will get nothing. 2 needs only 1 more vote (other than himself). He will keep 99 for himself and offer 1 to wither 5 or 4. 3 will disagree and whoever got 1 (between 4 and 5) will agree. That is enough to pass the vote 2-2.
Now, what is 1,2,3,4,5 is there? Again, 5 is hoping he will 1. 4 is hoping he will get 1. 3 is hoping he will get 1. (3 realizes that if it becomes just four of them, he will get nothing).1 needs only 2 more votes. So, he will keep 98 for himself and offer one coin to two out of 3,4,5. The vote will carry 3-2.
In general, the algorithm should be for n people, 1 will give out one coin each to (n-1)/2 (for n odd) or (n/2)-1 (for n even) people and keep the rest for himself. He can give those coins to anybody but 2.
In this case, therefore, 98,0,1,1,0 or 98,0,0,1,1 or 98,0,0,1,1 should be answers.