I am trying to evenly distribute the total amount to each person involved.

For example I will use money.

Example 1

Person A has $20

Person B has $40

Person C has $60

So to make everything even the solution is Person C giving person A $20.

Example 2

Person A has $36

Person B has $15

Person C has $9

To make this situation even:

Person A gives Person B \$16 then Person B gives Person C $11,

or Person A gives Person B $5 and Person C \$11

Example 3

Person A has $53

Person B has $95

Person C has $24

Person D has $98

Person E has $30

Each person needs $60, How could I figure out the way to do this that involves the least amount of moving the money around?


closed as off-topic by Jack D'Aurizio Aug 10 '18 at 17:14

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jack D'Aurizio
If this question can be reworded to fit the rules in the help center, please edit the question.


If you have $n$ people, you can always do it in at most $n-1$ movements. You can do this by progressively increasing the number of people who currently have exactly $x$, where $x$ is the average. At each step, if they do not all have the same amount, someone (say A) has more than $x$ and someone else (say B) has less than $x$; move enough money from A to B to leave A with exactly $x$.

In your example 3, this is the best you can do. To see this, suppose you have a better strategy and consider a graph where two people are connected by an edge if at any point your strategy moves money between them. If your strategy uses fewer than $n-1$ moves, the graph is disconnected. No money moves between components, so the average amount of money held by people in the first component doesn't change. At the end, everyone in the first component has exactly $x$, so at the start they had $x$ on average. There is no proper subset of the people who have \$60 on average, so this is impossible.

In general, the best you can do is as follows. Divide the people into as many groups as possible so that every group has the same amount of money on average (often, as here, you have to put everyone in the same group to achieve this). Move money within each group separately; for a group of $k$ people this takes $k-1$ moves. Overall, you use $n-g$ moves, where $g$ is the number of groups.

For example 1 you can divide into two such groups - {A,C} and {B} - but for example 2 you can't.


Not the answer you're looking for? Browse other questions tagged or ask your own question.