Me and a number of friends occasionally met up and play some game (often pool or some card game) and play for small stakes to give the game a little extra spice. After each round we jot down the results of the round to keep tally of who owes who how much.
Round | A owes B | A owes C | A owes D | B owes C | B owes D | C owes D ----------------------------------------------------------------------- 1 | 4 | 2 | 3 | | | 2 | | -3 | | -6 | | 2 3 | -2 | | | 1 | 2 | 4 | | | -5 | | -4 | -6 ----------------------------------------------------------------------- Total | 2 | -1 | -2 | -5 | -2 | -4
At the end of the session we have a list of IOUs between each of the friends that can by common sense be simplified. In the above example A owes B 2 coins, but D owes A 2 coins, which can be simplified by transferring A's debt to B to D.
| A owes B | A owes C | A owes D | B owes C | B owes D | C owes D ----------------------------------------------------------------------- Total | 0 | -1 | 0 | -5 | -4 | -4
My question, should this be deemed appropriate for this site, is how a formula to perform this simplification would look like? Specifically a function to determine the amount X owes Y. The idea is to automate the above using an excel sheet or similar (and spend the conclusion of the evening in small talk instead of fiddling with pen and paper).
My current thoughts are around minimizing the amount of transactions. By adding a persons winnings you could easily come up with the following table that gives the total gain/loss of every person
A | B | C | D ---------------- 1 | 9 | -2 | -8
From the above table one can easily see that only 10 coins should transfer hands, whereas the "simplified" example above involve transactions of 14 coins. One can also notice that there are more than one solution (either of C or D could owe A a single coin).