Results 1 to 2 of 2

Thread: Trade reduction / compression

  1. #1
    Feb 2013

    Trade reduction / compression


    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!

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Jan 2009

    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.
    Last edited by MacstersUndead; Feb 28th 2013 at 08:36 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Trade-in Value of a Car
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Aug 2nd 2009, 05:06 PM
  2. trade discounts
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Feb 4th 2009, 01:21 PM
  3. Trade Discount help
    Posted in the Business Math Forum
    Replies: 2
    Last Post: Feb 2nd 2009, 02:24 PM
  4. Math Tricks of the Trade
    Posted in the Math Challenge Problems Forum
    Replies: 7
    Last Post: Aug 9th 2008, 10:37 AM

Search Tags

/mathhelpforum @mathhelpforum