Thread Subject: Simple Optimization Problem

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

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?

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <84a25b13-1e98-4886-bfa2-f1454477e057@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 1--Tim pays Jon $82.5--
Bob : $50
Tim : $5 + $82.5 = $87.5
Sal : $95
Jon : $200 - $82.5 = $117.5

iteration 2--Bob pays Jon $30--
Bob : $50 + $30 = $80
Tim : $87.5
Sal : $95
Jon : $117.5 - $30 = $87.5

iteration 3--Bob 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.