8
$\begingroup$

There are people A,D,G,P

"A" needs $2.50 from D,G,P

"P" needs $2.50 from A,D,G

As far as who paid "A" what.
"D" paid "A" \$5 (So "A" owes D $2.50)
"G" hasn't paid "A" yet.
I don't know if "P" paid anything.

As far as who paid "P" what
"D" told "P" he can pay him $2.50
"G" hasn't paid "P" yet
I don't know if "A" paid anything.

"A" then works out that "G" should pay "P" $5 and then we are all even.

How does that work?

I am guessing that "A" did some calculations and worked out that him and P don't have to exchange any money, because they each owe each other the same amount ($2.50).

And "A" has been paid $2.50 more by "D" So "A" has the total amount of money he should have. So then G should pay P for himself and for D.

I sort of understand this, but I wouldn't have been able to calculate what "A" calculated. Can this be put into a simple mathematical form, where these kinds of things can be easily tracked (who owes who, what to do when one person pays more than they should)? How are these things are worked out?

Improve this question
$\endgroup$
3
  • $\begingroup$ Welcome @Barlop! What is the source for this question? $\endgroup$
    – user69943
    Jul 28, 2020 at 17:26
  • 2
    $\begingroup$ @DanielC a practical thing I ran into while in a group of people where a court or two were being booked in a sports hall $\endgroup$
    – barlop
    Jul 28, 2020 at 21:08
  • $\begingroup$ It doesn't matter who owes who, only the difference for each person between what they owe & are owed. $\endgroup$
    – philipxy
    Jul 29, 2020 at 18:40

8 Answers 8

Reset to default
11
$\begingroup$

At the beginning:

A needs 2.50 from D, G
P needs 2.50 from D, G
We can cancel out what A and P owe each other since it is the same amount

The only official payment that has happened is D paying 5.00 to A, so the updated transactions are:

A needs 2.50 from G
D needs 2.50 from A
P needs 2.50 from D, G

Now then:

The 2.50 G gives A, A will give to D, and D will give to P
To shorten this, G can give it straight to P
G already owes 2.50 to P so G gives 5.00 to P and everything is balanced

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks, are you ok with removing the spoiler code to make it easier to read, as this is a question about technique? thanks $\endgroup$
    – barlop
    Jul 29, 2020 at 13:13
  • 6
    $\begingroup$ If you click on the spoiler sections, they stay showing (in Firefox, at least) $\endgroup$
    – SeanC
    Jul 29, 2020 at 13:30
  • 4
    $\begingroup$ @SeanC, wow, I've been in this site for many years and I just knew you can click on the spoiler block to make it always visible! $\endgroup$
    – justhalf
    Jul 30, 2020 at 5:29
7
$\begingroup$

Assuming by "needs" at the start you mean "is owed", then:

A owes P and P owes A the same amount, so we can just forget about that.

Also:

D and G both owe $2.50 each to both A and P - so they both need to pay \$5 in total. And A and P should both be up \$5 at the end

So:

If D has already paid A $5, then the simplest way to get everyone to the correct end state is for G to pay P \$5

You could work out

That A owes D, D owes P and P owes A, so they all cancel. And after G gives P $5, then P owes G \$2.50, G still owes D, and D owes P, so they all cancel.

But it's easier to just work out

How much everyone should be up or down in total at the end, then find the least transactions to get there

In this case

From the first 2 sentences, A and P should each receive 7.50 and pay 2.50, so should each end up $5 better off. And D and G should each end up \$5 worse off. So the simplest for D to give \$5 to A and G to give \$5 to P (or vice versa - D to P and G to A).

Or another way of looking at it

For each person, add up all the amounts they're owed and subtract all the amounts they have to pay. A negative amount means they owe money, they throw that amount on the table. Everyone who should be up money picks up the net amount they should be up by.

Improve this answer
$\endgroup$
3
  • $\begingroup$ You write "it's easier to just work out How much everyone should be up or down in total at the end, then find the least transactions to get there" <-- can you include an example of that? thanks.. Also no need for spoiler format, as this is a question on techniques. $\endgroup$
    – barlop
    Jul 29, 2020 at 0:55
  • $\begingroup$ Added some extra detail. Stuck with the spoilers since I've come this far! $\endgroup$
    – Mohirl
    Jul 29, 2020 at 9:57
  • $\begingroup$ @barlop Sorry, I'd forgotten to save the changes! Updated now $\endgroup$
    – Mohirl
    Jul 29, 2020 at 14:33
7
$\begingroup$

Graphs are your friends!

1: Set Up: To make matters simple, let's just assume that at one point, A loaned the other three \$2.50 and P did the same. Let a directed edge represent \$2.50.

Our starting graph represents the cash flow state after both sets of loans are made. Note that the A-P Edges cancel.

2: D pays a \$5.00. Draw two edges (green, to represent two payments of \$2.50) Cancel accordingly.

3: Notice that A has one in and one out edge. A is at 0 balance, as is D. G has two in edges, meaning G has \$5 he shouldn't, and similarly, P has paid \$5 he shouldn't. In other words, G owes the collective \$5, and the collective owes P \$5. So G should pay P \$5.00

4: As an exercise, draw two lines representing G paying P, and cancel appropriately. The entire graph will become a loop.

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Think the dollar signs did something mathjaxy to the formatting. Code formatted the relevant bit to make it at least readable. $\endgroup$
    – Chris Cudmore
    Jul 28, 2020 at 19:34
  • $\begingroup$ You can prevent that by Escaping the $ symbol with a backslash (so, you type \$ in the post, and it will display as $, without risking any funny formatting) $\endgroup$
    – Chronocidal
    Jul 29, 2020 at 8:27
2
$\begingroup$

Hey there this is my first time so I don't know how to use the system exactly, pardon me.

Let's make some diagrams. To represent A needs 2.5 from D, use the text A<---2.5---D. Then we can represent the needed transactions as:

A<---2.5----D
A<---2.5----G
A<---2.5----P

P<---2.5----A
P<---2.5----D
P<---2.5----G

First observe that there need be no transaction between P and A.

Now we know P needs to net a total of 5$ = 7.5$(taken) - 2.5$(given). Also we know G must pay 5\$ and receives nothing. So since P only needs 5\$ which G needs to pay, we can have G give 5$ to P with no involvement from A or D.

Now the solution is like this:

D gave A 5$ so A---2.5--->D.

Now see G---2.5--->A---2.5--->D---2.5--->P
so this can be written G--2.5-->P equivalently.

This 2.5 is net flow indirect and G has to pay P 2.5 for direct debt 
so if G pays 5 to P it is all clear.
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Hello @AAkash Mathur. You need to put the critical part of your answer in SPOILER format. See answers below. Use the BLOCKQUOTE on those lines please $\endgroup$
    – DrD
    Jul 28, 2020 at 18:43
  • 3
    $\begingroup$ DEEM this wasn't posted as a puzzle, but as a "How do you figure it out." It's a question on techniques, so spoilers aren't really required. $\endgroup$
    – Chris Cudmore
    Jul 28, 2020 at 19:45
  • $\begingroup$ @ChrisCudmore. It still is an answer. Blockquotes help $\endgroup$
    – DrD
    Jul 28, 2020 at 22:33
  • $\begingroup$ @ChrisCudmore blockquotes are fine nobody disputes that! $\endgroup$
    – barlop
    Jul 29, 2020 at 0:53
2
$\begingroup$

The initial state of who owes whom what, before any payments are made, looks like this:

          Owes      
     ║ A │ D │ G │ P   Total
O   ═╬═══╪═══╪═══╪═══  ═════
w   A║ X │250│250│250   750 
e   ─╫───┼───┼───┼───  ─────
d   D║ 0 │ X │ 0 │ 0      0 
    ─╫───┼───┼───┼───  ─────
T   G║ 0 │ 0 │ X │ 0      0 
o   ─╫───┼───┼───┼───  ─────
    P║250│250│250│ X    750 

Total║250│500│500│250

This tells us we are looking to get to a final state of this:

A: +500 (+250[D] +250[G] +250[P] -250[P])
D: -500 (-250[A] -250[P])
G: -500 (-250[A] -250[P])
P: +500 (-250[A] +250[A] +250[D] +250[G])
(Notice how the +250 and -250 between A and P cancel out)

After D makes their payment, we are in this state:

A: +500 (Correct)
D: -500 (Correct)
G: ± 0 (Incorrect, reduce by 500)
P: ± 0 (Incorrect, increase by 500)

As such, the easiest way to get to the correct amounts is for G to pay P \$5.00, unless you need a proper accounting trail. In which case:

A pays D \$2.50 change (A -250 : D +250)
D pays P \$2.50 owed (D -250 : P +250)
G pays P \$2.50 owed (G -250 : P +250)
G pays A \$2.50 owed (G -250 : A +250)
Total difference: A ±0; D ±0; G -500; P -500
End results same as above

An alternate way to think about it:

A owes D \$2.50
D owes P \$2.50
G owes A \$2.50 and P \$2.50
P dunt owe nuffin' to no one

G pays P $2.50

A owes D \$2.50
D owes P \$2.50
G owes A \$2.50
P is getting fed up with these insinuations that they might owe money

G gives \$2.50 to A
A gives that \$2.50 to D
D gives that \$2.50 to P

So, G has just given another \$2.50 to P, but via A and D

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks that's great, and I like that you included different ways to look at it. Could you remove the spoiler code so it is easier to read? as my question is one of technique. $\endgroup$
    – barlop
    Jul 29, 2020 at 13:21
  • 1
    $\begingroup$ @barlop If you Click on a Spoiler, it toggles visibility $\endgroup$
    – Chronocidal
    Jul 29, 2020 at 13:39
2
$\begingroup$

Mathy

If you add a "hub" node to your graph, you can reduce the number of possible connections. If you allow 2 arrows to represent "owed" and "owes", it takes the number of possible relationships down from (n-1)n to 2n (so equal at 3 nodes and smaller thereafter).

Non-Mathy (the practical use of the above)

You invoke the money kitty!

You can consider your scenario as a $10 activity, where A paid for everyone the first time, and P paid for everyone the second. When you think of it like this, the sequence of events is:

The total kitty is \$20, and each person should pay $5.

The kitty owes A and P \$5 each (as they've both paid $10). D and G each owe the kitty \$5 as they have paid nothing.

Next, D pays \$5 to the kitty and therefore D is now square.

A takes \$5 from the kitty and is therefore all square.

We are left with G owing \$5 to the kitty, and P owed \$5 by the kitty, so it can be settled with that payments from G to P.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Let's say we "consider your scenario as a $10 activity, where A paid for everyone the first time, and P paid for everyone the second. " (which is actually what happened in the scenario I had in mind in the question!). The activity was at a leisure centre. What's the kitty? The leisure centre doesn't owe us money.. I see individual players, and the leisure centre, so what's this kitty that owes money and why does it owe money? I have some vague idea that it's some kind of total thing people put money in, some kind of intermediary, but I don't understand exactly what it is. $\endgroup$
    – barlop
    Jul 29, 2020 at 14:04
  • $\begingroup$ Like in a restaurant scenario there's a kitty, and people pay after the money is in the kitty.. But how does the kitty concept work if two people paid already before.. Then what is the definition of a kitty in that/this situation? I guess(if we take one kitty for the two bookings), I can see a kitty serving the purpose of making sure A gets 5 and P gets 5, and that G,D pay equal. So A,P are outputs of the kitty and G,D are inputs $\endgroup$
    – barlop
    Jul 29, 2020 at 14:08
  • $\begingroup$ I guess a kitty applies at a table in a restaurant.sorting money out on the spot. But if at home and with paypal. you're paying individuals rather than putting money in a pot for individuals to take. $\endgroup$
    – barlop
    Jul 29, 2020 at 14:14
  • 1
    $\begingroup$ I completely support the money kitty. Adding a virtual person to represent "the group" often makes these type of problems must simpler, especially when going on holidays with friends where some people pay for some expenses that might involve everyone or a subgroup. If k person take part in an activity, then every participant owes the group 1/k of the activity cost, and the group owes to any person who contributed money to the activity the amount that they paid. In the end, for every participant simply sum what they owe and subtract what they are owed. $\endgroup$
    – Stef
    Jul 29, 2020 at 14:46
  • $\begingroup$ To answer @barlop 's question "What's the kitty?": the kitty is a (virtual) intermediary who handles all transactions. Instead of saying "A gave some amount to D, G and P; D gave some amount to A; etc", which ends up in a relatively complex graph with lots of arrows all over the place, you say "A gave some amount to the kitty; the kitty gave some amount to D, G and P; D gave some amount to the kitty; the kitty gave some amount to A; etc". This results in a much simpler graph, because everyone is only dealing with the kitty, instead of everyone dealing with everyone. $\endgroup$
    – Stef
    Jul 29, 2020 at 14:52
0
$\begingroup$

Let's say

A pays £10 for court for four people including himself (So £2.50 each) P pays £10 for a court for four people including himself. (So £2.50 each)

That’s equivalent to A lending £2.50 to three people. And P lending £2.50 to three people.

So that leads to what is mentioned at the beginning of the question

"A" needs \$2.50 from D,G,P
"P" needs \$2.50 from A,D,G

If you’re not A or P, you owe £5 If you’re A or P, you owe £2.50 (and others owe you 3*£2.50)

Everybody ends up paying £5 . i.e. -£5

A  -£10
P  -£10
D 0
G 0

D pays £5 to A (which actually makes it easier, it could have been unintentional e.g. D thought "A" was going to book both courts, or it could have been intentional, just paying all that is owed and let the others figure it out, he's done his bit)

D only owes A £5 so it was too much , to A, but actually made it much easier

A  -£5
P  -£10
D -£5
G 0

Then if G pays P £5

A  -£5
P  -£5
D -£5
G -£5

Or to put it another way, a in table all in one go. and one can add a middle column showing how much needs to be added or subtracted..

A -10 | +5 | -5 
P -10 | +5 | -5
D  0  | -5 | -5
G  0  | -5 | -5

It shows that D pays 5 and G pays 5. It doesn't show who D paid (whether it was A or P), or who G paid (whether A or P), but that's fine, it doesn't matter. It works regardless

So that table does it in one.

The other route seems to be long.. and didn't make it obvious that D or G should pay £5 to one person to make things easier.

D-----2.50-------A  
G-----2.50-------A 
P-----2.50-------A 
A-----2.50------P  
G-----2.50-----P
D-----2.50----P

simplify it.. 
e.g. identify chains or ones that can cancel out.

D-----2.50-------A    A-----2.50------P   P-----2.50-------A
G-----2.50-------A   
G-----2.50-----P
D-----2.50----P

becomes

D-----2.50------A
G-----2.50-------A   
G-----2.50-----P
D-----2.50----P

suppose D pays £5 to A   

A----2.50-----D
G-----2.50-------A   
G-----2.50-----P
D-----2.50----P

simplify

A----2.50-----D      D-----2.50----P
G-----2.50-------A   
G-----2.50-----P

becomes 

A--2.50---P
G-----2.50-------A   
G-----2.50-----P

becomes 


G-----2.50-------A    A--2.50---P
G-----2.50-----P

becomes

G----2.50---P
G---2.50--P

becomes

G---£5---P

So G must pay P £5
Improve this answer
$\endgroup$
1
  • $\begingroup$ A needs £7.50(£2.50*3) from each of the three. P needs £7.50(£2.50*3) from each of the three. A<->P cancels. So A needs £5 from G,D. and P needs £5 from G,D. Between A and P, each of them needs £5. For a total of £10. So D can pay A and G can pay P, or vice versa.. i.e. D,G in total give £10 to the bookers(D gives £5, G gives £5) that split it between them.one booker takes £5 the other booker takes £5. To put it in pairs. The bookers paid £20 and need £10 back. 5 from D, 5 from G. Split between them. $\endgroup$
    – barlop
    Jul 29, 2020 at 22:27
0
$\begingroup$

Just keep a running total of what each is owed (positive) or owes (negative). It doesn't matter to whom:

There are people A,D,G,P

A = \$0.00
D = \$0.00
G = \$0.00
P = \$0.00

"A" needs $2.50 from D,G,P

A = \$7.50
D = -\$2.50
G = -\$2.50
P = -\$2.50

"P" needs $2.50 from A,D,G

A = \$5.00
D = -\$5.00
G = -\$5.00
P = \$5.00

As far as who paid "A" what. "D", paid "A" \$5 (So "A" owes D \$2.50)

A = \$0
D = \$0
G = -\$5.00
P = \$5.00

"G", hasn't paid "A" yet.

No change

"P", i don't know if he paid anything.

Well find out! Until then, no change!

As far as who paid "P" what "D" told "P" he can pay him $2.50

Not sure why. No change.

"G" hasn't paid "P" yet

No change

"A" I don't know if he paid anything.

No change

"A" then works out that "G" should pay "P" \$5 and then we are all even.

That adds up!

A = \$0
D = \$0
G = -\$5.00
P = \$5.00

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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