This is a question in the Algorithem design textbook chapter 7 question 25, I am kind of lost as to how to go about to solve the problem, could you please show the steps?

Suppose you live in a big apartment with a lot of friends. Over the course of a year, there are many occasions when one of you pays for an expense shared by some subset of the apartment, with the expectation that everything will get balanced out fairly at the end of the year. For example, one of you may pay the whole phone bill in a given month, another will occasionally make communal grocery runs to the nearby organic food emporium, and a third might sometimes use a credit card to cover the whole bill at the local Italian-Indian restaurant, Little Idli.

In any case, its now the end of the year and time to settle up. There are n people in the apartment; and for each ordered pair (i, j) theres an amount aij ? 0 that i owes j, accumulated over the course of the year. We will require that for any two people i and j, at least one of the quantitiesaij or aji is equal to 0. This can be easily made to happen as follows: If it turns out that i owes j a positive amount x, and j owes i a positive amounty < x, then we will subtract off y from both sides and declare aij = x ? ywhile aji = 0. In terms of all these quantities, we now define the imbalanceof a person i to be the sum of the amounts that i is owed by everyone else, minus the sum of the amounts that i owes everyone else. (Note that an imbalance can be positive, negative, or zero.)

In order to restore all imbalances to 0, so that everyone departs on good terms, certain people will write checks to others; in other words, for certain ordered pairs (i, j), i will write a check to j for an amount bij > 0.

Exercises

429

430

Chapter 7 Network Flow

We will say that a set of checks constitutes a reconciliation if, for each person i, the total value of the checks received by i, minus the total value of the checks written by i, is equal to the imbalance of i. Finally, you and your friends feel it is bad form for i to write j a check if i did not actually owe j money, so we say that a reconciliation is consistent if, whenever iwrites a check to j, it is the case that aij > 0.

Show that, for any set of amounts aij, there is always a consistent reconciliation in which at most n ? 1 checks get written, by giving a polynomial-time algorithm to compute such a reconciliation.