1. ## Trade reduction / compression

Hi,

I am new here. I usually stick to programming forums but my problem here is mathematical in nature and I just need a few pointers before I can go out and code a solution. By the looks of the forum, I wish I had come here when I was still at university... Anyway, the problem is below (somewhat simplified):

There are a large number of people that require a certain amount of apples. They can only trade apples with each other, and I want to figure out the quickest way (least number of trades) required for each to finish with the number of apples that they need. For example, for people named A-F:

Ending Requirement
A 250
B -130
C 300
D -100
E 20
F -340

To solve:

B gives A 250
D gives B 100
F gives C 300
F gives B 20
F gives E 20

Now if there was 50 people, or even 1000 people, this may get quite complicated. How would one go about finding the smallest number of trades possible to get the required result (and the size / direction of the trades)?

Thanks in advance for any ideas on where to start!

Peel

2. ## Re: Trade reduction / compression

I'm assuming each person starts with 0 apples.
A less creative solution for your above example with the same number of steps is:

B gives A 250 (A at 250, B at -250)
C gives B 120 (B at -130, C at -120)
D gives C 420 (C at 300, D at -420)
E gives D 320 (D at -100, E at -320)
F gives E 340 (E at 20, F at -340)

Proceeding inductively, it can be shown that given n people with 0 apples can be rearranged to have the above requirement which totals 0 (n-1) trades is a solution. To prove that it is the least amount of trades, suppose that any Ending Requirement can be yielded with (n-2) trades instead. Let n=2; it's obvious that end result A 1 B -1 cannot happen with 2-2=0 trades, so we have a contradiction. Hence the smallest number of trades possible to get the required result is (n-1)

EDIT: the quantity of each trade will be (projected value - current value) of the receiver after each trade.