[Guest]

Ten friends play poker. At the end of the night, each player counts his chips and calculates how much money he has won or lost.

They then pay or collect money using the following rules:

Either (1) One player pays an equal amount to every other player

Or (2) One player receives the same amount from every other player.

They continue this procedure in steps until each winner has received exactly what he has won and each loser has paid exactly what he has lost.

Q1. Is this procedure guaranteed to finish in a finite number of steps?

Q2. If so, what is the expected number of steps required?

[Guest]

yes, it can be done in a finite number of steps, you can solve it using vectors in 10 dimensions with each dimension representing what each person has, with the players taking and giving according to the rules, you can change the amounts using these vectors:

(9,-1,-1,-1,-1,-1,-1,-1,-1,-1)

(-9,1,1,1,1,1,1,1,1,1)

(-1,9,-1,-1,-1,-1,-1,-1,-1,-1)

(1,-9,1,1,1,1,1,1,1,1)

(-1,-1,9,-1,-1,-1,-1,-1,-1,-1)

(1,1,1-9,,1,1,1,1,1,1)

...

(-1,-1,-1,-1,-1,-1,-1,-1,-1,9)

(1,1,1,1,1,1,1,1,1,-9)

So you have 20 non-parallel vectors and you can multiply any vector by any number you want (unless you're limited by the amount of money they can give or get) and for 10 dimensions you only need 10 different vectors to be able to make out any point...

So it can be done and it would take 10 steps or less...

(though if fractions and negative sums aren't allowed then I don't think there's a general solution, it might have no solution)

[Guest]

as am example, let's say every player before the exchanges has 100 chips.

player 1 won 5 chips from everyone.

(45,-5,-5,-5,-5,-5,-5,-5,-5,-5)

player 2 loses 2 chips to everyone.

(2,-18,2,2,2,2,2,2,2,2)

player 3 wins 4 chips from everyone.

(-4,-4,36,-4,-4,-4,-4,-4,-4,-4)

player 4 loses 5 chips to everyone.

(5,5,5,-45,5,5,5,5,5,5)

and so on. so far we have....

(48,-22,38,-52,-2,-2,-2,-2,-2,-2)

note that the negatives equal the postives.

note we can also reverse the process. ie. by knowing what amounts each player should have at the end of the exchanges, we can dtermine what each player should give/get when his turn comes around.

[Guest]

I do not believe it is always possible to finish in a finite number of steps. All payouts would need be modulo 9. As payments are made with a tangible object, money, no negative amounts could be paid out or collected and all fractions would need be in valid currency. For the USA, this means no fraction smaller than 0.01 for the dollar would be permitted.

I do not see how a solution would always be possible. If, for example, one player won all the chips but for 1 with all other players but one losing all their chips, by following the rules of payouts and collections, how could each player end up with the correct balance?

[Guest]

I do not believe it is always possible to finish in a finite number of steps. All payouts would need be modulo 9. As payments are made with a tangible object, money, no negative amounts could be paid out or collected and all fractions would need be in valid currency. For the USA, this means no fraction smaller than 0.01 for the dollar would be permitted.

I do not see how a solution would always be possible. If, for example, one player won all the chips but for 1 with all other players but one losing all their chips, by following the rules of payouts and collections, how could each player end up with the correct balance?

Anza Power, I like your vector approach very much. Exactly correct. Good job.

Dej Mar. They are settling up with real dollars from their wallets, not playchips. Assume that everyone has more than enough dollars to pay off their debts, so negative dollars are not an issue.

Regarding fractions of cents, you are correct, but let's assume for the purpose of this question that dollars are infinitely divisible.

[Guest]

Let Xi be the amount owed to the ith player where Xi is positive for a winner and negative for a loser.

Let player 1 be the biggest loser.

Then, for i=2 to N the (i-1)th step consists of all players giving (Xi-X1)/N to player i.

After N-1 steps all debts are settled.

Edited September 11, 2010 by Hawkeye