Suppose n people live in a house and wish to share their expenses equally. Their respective expenses (before settling) are x1, ..., xn. They agree to write checks to each other so as to make all their net expenses equal. Naturally, they want to use as few checks as possible.

SETTLEMENT denotes the decision version of this problem: Given nonnegative integers x1, . . . , xn (written in binary) and an integer k, can the net expenses be balanced using k or fewer checks?

I am not sure if I am understanding this problem correctly.. So, given the information, k is a balanced net expense, right? We should find the average net expense of {x1,...,xn}, where x1,...,xn represent the respective expenses. So, SETTLEMENT is as follows:

SETTLEMENT = {(x1,…,xn; k) : there exists some k such that (x1+x2+...+xn) / n = k}.


Your interpretation is incorrect. The value of $k$ is not an expense, $k$ is the minimum number of checks needed to make sure that the net amount of money paid by each person is $\overline{x} = \frac{1}{n} =\sum_{i=1}^n x_i$.

For example if $n=2$, $x_1=1$, $x_2=5$ then $\overline{x}=3$ and $k=1$. In particular it suffices from the 1st person to write a check to the 2nd person for an amount of $2$.

  • $\begingroup$ Thank you for your help. That quite makes sense. $\endgroup$ – Matthew Apr 9 at 17:46
  • $\begingroup$ I constructed the algorithm to compute this: For each expense xi, if it is less or more than X, then that person writes a check to the next person for an amount of the difference. By this algorithm that is in polynomial time, we intuitively know there will be k or fewer checks necessary to make the net expenses balanced. What do you think about this? $\endgroup$ – Matthew Apr 9 at 17:47
  • $\begingroup$ I think that your algorithm doesn't work. Counterexample: $x_1 = 3$, $x_2=2$, $x_3=1$. Your algorithm uses $2$ checks but only one check is needed. $\endgroup$ – Steven Apr 9 at 17:55
  • $\begingroup$ What about this: For each expense xi, if it is less or more than X, then that person writes a check for an amount of the difference to the next person whose expense is not equal to X. $\endgroup$ – Matthew Apr 9 at 17:59
  • $\begingroup$ That algorithm could prescribe to write checks of negative amounts. Besides, even when this doesn't happen, the algorithm doesn't work. Counterexample: $x_1 = 4$, $x_2 =1$, $x_3=3$, $x_4=0$. Your algorithm writes at least $3$ checks yet the optimal solution uses $2$ checks. In general, I don't think that it is useful for you to guess an algorithm and use me as an oracle to provide you with counterexamples. Try to prove yourself that your algorithm doesn't work. If you consistently fail to do so, then try to write down a formal proof of correctness. Repeat until a solution is found :) $\endgroup$ – Steven Apr 9 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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