One hundred pirates played cards. When the game was over, each pirate calculated the amount he won or lost. The pirates have a gold sand as a currency; each has enough to pay his debt. Gold could only change hands in the following way. Either one pirate pays an equal amount to every other pirate, or one pirate receives the same amount from every other pirate. Prove that after several such steps, it is possible for each winner to receive exactly what he has won and for each loser to pay exactly what he has lost. (4 points)
Problem
Source:
Tags: induction
math_explorer
04.09.2010 09:51
Essentially, consider this operation:
Pirate A gives $x$ gold to all other pirates, and then Pirate B takes $x$ gold from all other pirates. After these operations, the net effect is that Pirate A has given $(n+1)x$ gold to Pirate B ($n$ is the number of pirates), leaving all other pirates' gold amounts unchanged. By changing $x$ you can easily make $(n+1)x$ any positive real you want, so now you can make one pirate give an amount of gold to another.
The remaining part is clear. To prove it simply, pick out a pirate M whose win or loss is smallest in magnitude, pick any other pirate N who won if M lost or lost if M won. Transfer gold between M and N so that M has the right amount of gold. Use induction on the pirates minus M.
AnonymousBunny
09.01.2015 21:11
Let the pirates who have won have won a total of money $x$. This is also equal to the total amount lost by the pirates who have lost. Consider a pirate who has lost a total of money $a$. At some stage, let this pirate donate $\dfrac{99}{100}a$ money to all other pirates. Now, consider a pirate who has won a total of money $b$. At some stage, let this pirate get $\dfrac{b}{100}$ money from all the other pirates. At the end of the party, the first pirate has donated a total of $\dfrac{99}{100}a + \dfrac{1}{100} x + \dfrac{1}{100}a - \dfrac{1}{100}x = a$, and the second pirate has gained a total of $\dfrac{99}{100}b -\dfrac{1}{100} x + \dfrac{1}{100}b + \dfrac{1}{100} x = b,$ so the job is possible.