Hi,
I'm solving the exact problem. Did you solve it eventually?
What I plan to do:
 use TORSCHE toolbox for Matlab, which has support for Integer Linear Programming
 define problem using ILP, where I introduce new binary variable which will say who did send money to who  will be used for counting transactions
 set criteria to minimizing number of transactions
Do you have some other suggestions?
David Vavra
"Neal Gordon" <gordon.363@osu.edu> wrote in message <gpfaj1$im7$1@fred.mathworks.com>...
> ImageAnalyst <imageanalyst@mailinator.com> wrote in message <84a25b131e984886bfa2f1454477e057@l39g2000yqn.googlegroups.com>...
> > On Mar 13, 11:33=A0pm, "Neal Gordon" <gordon....@osu.edu> wrote:
> > > OK, here is my question. A simple example: Say you have 4 people who each=
> > spend a certain amount.
> > > Bob  $50
> > > Tim  $5
> > > Sal  $95
> > > Jon  $200
> > > Together they spent $350, so thats an average of $87.5/person.
> > > Find a solution to minimize the number of transactions between the people=
> > so that everyone has spent the same amount.
> > >
> > > example solution
> > > Tim pays Jon $82.5
> > > Bob pays Jon $30
> > > Bob pays Sal $7.5
> > >
> > > Thanks.
> > > Neal
> > =
> > 
> > I don't understand. If Tim pays $5 total, or even $5 per transaction,
> > then how can he spend $82.5 which is not a multiple of $5? And in
> > your example solution, not everybody has paid the same amount. Tim
> > paid $82.50, Bob paid $37.50, and Jon and Sal didn't pay(spend)
> > anything. Are you sure you're explaining this correctly?
>
> Original amount spent:
> Bob  $50
> Tim  $5
> Sal  $95
> Jon  $200
> Together, as a group, they spent $350 = 50+5+95+200, so thats an average of $87.5/person.
>
> So, to clarify, we would like to find the quickest way for everyone in the group to have spent the same amount overall. Now, I will show the iterations with the current amount spent per person.
> iteration 0
> Bob : $50
> Tim : $5
> Sal : $95
> Jon : $200
>
> iteration 1Tim pays Jon $82.5
> Bob : $50
> Tim : $5 + $82.5 = $87.5
> Sal : $95
> Jon : $200  $82.5 = $117.5
>
> iteration 2Bob pays Jon $30
> Bob : $50 + $30 = $80
> Tim : $87.5
> Sal : $95
> Jon : $117.5  $30 = $87.5
>
> iteration 3Bob pays Sal $7.5
> Bob : $80 + $7.5 = $87.5
> Tim : $87.5
> Sal : $95  $7.5 = $87.5
> Jon : $87.5
>
> final spending with 3 iterations(transactions):
> Bob : $87.5
> Tim : $87.5
> Sal : $87.5
> Jon : $87.5
>
> I hope this helps. This solution is trivial, but I am interested in the solution of 15+ people while trying to achieve less iterations than the "Number of people minus 1", which in this case is 3 obvious iterations.
